In deze tutorial zullen we de gegevensstructuur van de binaire zoekboom bespreken. We zullen de functies implementeren om waarden te zoeken, in te voegen en te verwijderen uit een binaire zoekboom. We zullen deze bewerkingen zowel recursief als iteratief implementeren.
Binaire Zoekboom
A Binary Search tree has the following property:
- Alle knooppunten moeten zo zijn dat het linkerkind altijd kleiner is dan het ouderknooppunt.
- Het rechterkind is altijd groter dan het ouderknooppunt.
In de volgende secties zullen we zien hoe we recursief en iteratief kunnen zoeken, invoegen en verwijderen in een binaire zoekboom. Laten we eerst onze gegevensstructuur van de binaire boom maken:
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;
}
}
}
Merk op dat de bovenstaande implementatie geen binaire zoekboom is omdat er geen beperking is bij het invoegen van elementen in de boom.
BST Zoeken Recursief
Het volgende Java-programma bevat de functie om recursief een waarde in een BST te zoeken.
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;
}
}
De output is: 
Zoekfunctie voor BST Iteratief
Om iteratief te zoeken, gebruik in plaats daarvan de volgende 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;
}
Laten we eens kijken hoe we een nieuwe knoop moeten invoegen in een binair zoekboom.
BST Invoeging Recursief
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);
}
}
Roep de bovenstaande methode aan in de hoofdmethode:
tree.root = insertionRecursive(tree.root, 24);
tree.root = insertionRecursive(tree.root, 2);
printInorderTraversal(tree.root);
De boom wordt afgedrukt in de vorm van in-order traversal. 
BST Invoeging Iteratief
Om een knoop iteratief in te voegen in een BST-boom, moeten we de boom doorkruisen met behulp van twee pointers.
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 Verwijderen Recursief
Het verwijderen van een element uit een BST is iets complexer dan het zoeken en invoegen, aangezien we ervoor moeten zorgen dat de BST-eigenschap behouden blijft. Om een knoop te verwijderen moeten we deze eerst zoeken. Vervolgens moeten we bepalen of die knoop kinderen heeft of niet.
- Als er geen kinderen zijn – Gewoon verwijderen.
- Als er één kind is – Kopieer dat kind naar de knoop.
- Als er twee kinderen zijn – Bepaal het volgende hoogste element (inorder-opvolger) in de rechterdeelboom. Vervang de te verwijderen knoop door de inorder-opvolger. Verwijder de dubbele inorder-opvolger.
De inorder-opvolger kan worden verkregen door de minimumwaarde te vinden in het rechterkind van de knoop.
Het volgende Java-programma verwijdert elementen uit een 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;
}
Roep de bovenstaande verwijderingsmethode aan in de main-methode:
tree.root = deleteRecursively(tree.root, 4);
tree.root = deleteRecursively(tree.root, 20);
printInorderTraversal(tree.root);
De output is: 2 5 8 10 15 24 25 Laten we hetzelfde iteratief doen.
BST Element Verwijderen Iteratief
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;
}
De tijdscomplexiteit van BST-operaties is O(h). h is de hoogte van de boom.
Dat brengt een einde aan deze tutorial.
Je kunt de volledige code en meer DS & algoritmevoorbeelden bekijken op onze GitHub Repository.
Source:
https://www.digitalocean.com/community/tutorials/binary-search-tree-bst-search-insert-remove