עץ חיפוש בינארי (BST) – חיפוש, הוספה והסרה

במדריך זה, נדבר על מבנה הנתונים "עץ חיפוש בינארי". נכניס לפעולה את הפונקציות לחיפוש, להכניס, ולהסיר ערכים מעץ חיפוש בינארי. נכניס את הפעולות אלו באופן רקורסיבי וגם בצורה תיקנית.

עץ חיפוש בינארי

A Binary Search tree has the following property:

• כל הצמתים צריכים להיות כך שהילד השמאלי תמיד קטן מהצומת ההורה.
• הילד הימני תמיד גדול מהצומת ההורה.

במקטעים הבאים, נראה איך לחפש, להכניס ולמחוק באופן רקורסיבי וגם בצורה תיקנית בעץ חיפוש בינארי. בואו ניצור תחילה את מבנה הנתונים "עץ הבינארי שלנו":

public class BinaryTree {

	public TreeNode root;

	public static class TreeNode {

		public TreeNode left;
		public TreeNode right;
		public Object data;

		public TreeNode(Object data) {
			this.data = data;
			left = right = null;
		}
	}
}

שימו לב שהמימוש לעיל אינו עץ חיפוש בינארי מאחר ואין הגבלה בהכנסת האיברים לעץ.

חיפוש בעץ באופן רקורסיבי

התוכנית ב-Java שלמטה מכילה את הפונקציה לחיפוש ערך בעץ באופן רקורסיבי.

public class SearchInsertRemoveFromTree {

    public static void main(String[] args) {

	/**
	 *   Our Example Binary Search Tree
	 *       10
	 *     5    20
	 *   4  8  15 25
	 */

        BinaryTree tree = new BinaryTree();
        tree.root = new TreeNode(10);
        tree.root.left = new TreeNode(5);
        tree.root.right = new TreeNode(20);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(8);
        tree.root.right.left = new TreeNode(15);
        tree.root.right.right = new TreeNode(25);

        System.out.println("Search Value 2 is in tree? " + searchRecursively(tree.root, 2));
        System.out.println("Search Value 10 in tree? " + searchRecursively(tree.root, 10));
    }

    public static boolean searchRecursively(TreeNode root, int value) {


        if (root == null)
            return false;


        if ((int) root.data == value)
            return true;

        if (value < (int) root.data)
            return searchRecursively(root.left, value);

        else if (value > (int) root.data)
            return searchRecursively(root.right, value);


        return false;
    }
}

הפלט הוא:

חיפוש BST באופן איטרטיבי

כדי לחפש באופן איטרטיבי, השתמש בשיטה הבאה במקום:

public static boolean searchIteratively(TreeNode root, int value) {

        while (root != null) {
            if ((int) root.data == value)
                return true;

            if (value < (int) root.data)
                root = root.left;

            else
                root = root.right;
        }

        return false;
    }

בואו נסתכל על איך להכניס צומת חדש בעץ חיפוש דו מקומי.

הכנסת BST באופן רקורסיבי

public static TreeNode insertionRecursive(TreeNode root, int value) {

        if (root == null)
            return new TreeNode(value);

        if (value < (int) root.data) {
            root.left = insertionRecursive(root.left, value);
        } else if (value > (int) root.data) {
            root.right = insertionRecursive(root.right, value);
        }

        return root;

    }

public static void printInorderTraversal(TreeNode root) {
        if (root != null) {
            printInorderTraversal(root.left);
            System.out.print(root.data + " ");
            printInorderTraversal(root.right);
        }
    }

קרא לשיטה הנ"ל בשיטת הראשית:

tree.root = insertionRecursive(tree.root, 24);
tree.root = insertionRecursive(tree.root, 2);
printInorderTraversal(tree.root);

העץ מודפס בצורת סיור באמצעות inorder.

הכנסת BST באופן איטרטיבי

כדי להכניס צומת באופן איטרטיבי בעץ BST, נצטרך לעבור על העץ באמצעות שני מצביעים.

public static TreeNode insertionIterative(TreeNode root, int value) {

        TreeNode current, parent;

        TreeNode tempNode = new TreeNode(value);

        if (root == null) {
            root = tempNode;
            return root;
        } else {
            current = root;
        }

        while (true) {
            parent = current;

            if (value < (int) current.data) {
                current = current.left;
                if (current == null) {
                    parent.left = tempNode;
                    return root;
                }

            } else if (value > (int) current.data) {
                current = current.right;

                if (current == null) {
                    parent.right = tempNode;
                    return root;
                }
            }

        }
    }

הסרת איבר BST באופן רקורסיבי

הסרת אלמנט מ- BST דורשת קצת יותר מורכבת מחיפוש והכנסה מאחר ועלינו לוודא שתכונת ה-BST נשמרת. כדי למחוק צומת עלינו תחילה לחפש אותו. אז עלינו לקבוע אם לצומת יש ילדים או לא.

• אם אין ילדים – פשוט למחוק.
• אם יש ילד יחיד – להעתיק את הילד הזה לצומת.
• אם יש שני ילדים – לקבוע את האיבר הבא בגובה (המחליף הבא בסדר) בעץ המשנה הימני. להחליף את הצומת שיש למחוק עם המחליף הבא בסדר. למחוק את השכפול של המחליף הבא בסדר.

המחליף הבא בסדר ניתן להשיג על ידי מציאת הערך המינימלי בילד הימני של הצומת.

התוכנית ב-Java הבאה מסירה אלמנטים מ-BST:

public static TreeNode deleteRecursively(TreeNode root, int value) {

        if (root == null)
            return root;

        if (value < (int) root.data) {
            root.left = deleteRecursively(root.left, value);
        } else if (value > (int) root.data) {
            root.right = deleteRecursively(root.right, value);
        } else {

            if (root.left == null) {
                return root.right;
            } else if (root.right == null)
                return root.left;

            root.data = inOrderSuccessor(root.right);
            root.right = deleteRecursively(root.right, (int) root.data);
        }

        return root;

    }

    public static int inOrderSuccessor(TreeNode root) {
        int minimum = (int) root.data;
        while (root.left != null) {
            minimum = (int) root.left.data;
            root = root.left;
        }
        return minimum;
    }

קרא לשיטת המחיקה הנ"ל בשיטת main:

tree.root = deleteRecursively(tree.root, 4);
tree.root = deleteRecursively(tree.root, 20);
printInorderTraversal(tree.root);

הפלט הוא: 2 5 8 10 15 24 25 בואו נעשה אותו דבר באופן עקבי.

הסרת BST אלמנטים באופן עקבי

public static TreeNode deleteNodeIteratively(TreeNode root, int value) {
        TreeNode parent = null, current = root;
        boolean hasLeft = false;

        if (root == null)
            return root;

        while (current != null) {
            if ((int) current.data == value) {
                break;
            }

            parent = current;
            if (value < (int) current.data) {
                hasLeft = true;
                current = current.left;
            } else {
                hasLeft = false;
                current = current.right;
            }
        }


        if (parent == null) {
            return deleteNodeIteratively(current);
        }

        if (hasLeft) {
            parent.left = deleteNodeIteratively(current);
        } else {
            parent.right = deleteNodeIteratively(current);
        }

        return root;
    }

    private static TreeNode deleteNodeIteratively(TreeNode node) {

        if (node != null) {
            if (node.left == null && node.right == null) {
                return null;
            }

            if (node.left != null && node.right != null) {
                TreeNode inOrderSuccessor = deleteInOrderSuccessorDuplicate(node);
                node.data = inOrderSuccessor.data;
            } else if (node.left != null) {
                node = node.left;
            } else {
                node = node.right;
            }
        }

        return node;
    }

    private static TreeNode deleteInOrderSuccessorDuplicate(TreeNode node) {
        TreeNode parent = node;
        node = node.right;
        boolean rightChild = node.left == null;

        while (node.left != null) {
            parent = node;
            node = node.left;
        }

        if (rightChild) {
            parent.right = node.right;
        } else {
            parent.left = node.right;
        }

        node.right = null;
        return node;
    }

זמניות המורכבות של פעולות BST היא O(h). h הוא גובה העץ.

זה מסיים את המדריך הזה.

ניתן לבדוק את הקוד המלא ועוד דוגמאות DS & Algorithm ממאגר ה-GitHub שלנו .