In diesem Tutorial werden wir die Datenstruktur des binären Suchbaums diskutieren. Wir werden die Funktionen zur Suche, zum Einfügen und zum Entfernen von Werten aus einem binären Suchbaum implementieren. Wir werden diese Operationen sowohl rekursiv als auch iterativ umsetzen.
Binärer Suchbaum
A Binary Search tree has the following property:
- Alle Knoten sollten so sein, dass das linke Kind immer kleiner als der Elternknoten ist.
- Das rechte Kind ist immer größer als der Elternknoten.
In den folgenden Abschnitten werden wir sehen, wie man rekursiv und iterativ in einem BST sucht, einfügt und löscht. Lassen Sie uns zuerst unsere Datenstruktur für den binären Baum erstellen:
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;
}
}
}
Beachten Sie, dass die obige Implementierung kein binärer Suchbaum ist, da keine Einschränkung für das Einfügen von Elementen in den Baum besteht.
Rekursive BST-Suche
Das folgende Java-Programm enthält die Funktion zur rekursiven Suche nach einem Wert in einem BST.
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;
}
}
Die Ausgabe ist: 
BST-Suche iterativ
Um iterativ zu suchen, verwenden Sie stattdessen die folgende Methode:
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;
}
Schauen wir uns an, wie man einen neuen Knoten in einem Binären Suchbaum einfügt.
BST-Einfügung rekursiv
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);
}
}
Rufen Sie die oben genannte Methode in der Hauptmethode auf:
tree.root = insertionRecursive(tree.root, 24);
tree.root = insertionRecursive(tree.root, 2);
printInorderTraversal(tree.root);
Der Baum wird in Form einer Inorder-Traversierung gedruckt. 
BST-Einfügung iterativ
Um einen Knoten iterativ in einem BST-Baum einzufügen, müssen wir den Baum mit zwei Zeigern durchlaufen.
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-Element rekursiv entfernen
Das Entfernen eines Elements aus einem BST ist etwas komplexer als die Suche und das Einfügen, da wir sicherstellen müssen, dass die BST-Eigenschaft erhalten bleibt. Um einen Knoten zu löschen, müssen wir ihn zuerst suchen. Dann müssen wir feststellen, ob dieser Knoten Kinder hat oder nicht.
- Wenn keine Kinder vorhanden sind – Einfach löschen.
- Wenn nur ein Kind vorhanden ist – Kopiere dieses Kind zum Knoten.
- Wenn zwei Kinder vorhanden sind – Bestimmen Sie das nächsthöhere Element (Inorder-Nachfolger) im rechten Teilbaum. Ersetzen Sie den zu entfernenden Knoten durch den Inorder-Nachfolger. Löschen Sie die Duplikate des Inorder-Nachfolgers.
Der Inorder-Nachfolger kann gefunden werden, indem man den minimalen Wert im rechten Kind des Knotens sucht.
Das folgende Java-Programm entfernt Elemente aus einem 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;
}
Rufen Sie die oben genannte Löschmethode in der main-Methode auf:
tree.root = deleteRecursively(tree.root, 4);
tree.root = deleteRecursively(tree.root, 20);
printInorderTraversal(tree.root);
Die Ausgabe ist: 2 5 8 10 15 24 25 Lassen Sie uns dasselbe iterativ tun.
BST Entfernen von Elementen Iterativ
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;
}
Die Zeitkomplexität der BST-Operationen beträgt O(h). h ist die Höhe des Baumes.
Damit endet dieses Tutorial.
Sie können den vollständigen Code und weitere DS & Algorithmus-Beispiele aus unserem GitHub-Repository überprüfen.
Source:
https://www.digitalocean.com/community/tutorials/binary-search-tree-bst-search-insert-remove