Binaire zoekboom

In deze tutorial leert u hoe Binary Search Tree werkt. Ook vindt u werkende voorbeelden van Binary Search Tree in C, C ++, Java en Python.

Binaire zoekboom is een datastructuur waarmee we snel een gesorteerde lijst met getallen kunnen bijhouden.

• Het wordt een binaire boom genoemd omdat elk boomknooppunt maximaal twee kinderen heeft.
• Het wordt een zoekboom genoemd omdat het kan worden gebruikt om in de O(log(n))tijd naar de aanwezigheid van een nummer te zoeken .

De eigenschappen die een binaire zoekboom scheiden van een gewone binaire boom zijn

1. Alle knooppunten van de linker substructuur zijn kleiner dan het hoofdknooppunt
2. Alle knooppunten van de rechter substructuur zijn meer dan het hoofdknooppunt
3. Beide substructuren van elk knooppunt zijn ook BST's, dwz ze hebben de bovenstaande twee eigenschappen

Een boom met een juiste substructuur met één waarde kleiner dan de wortel wordt getoond om aan te tonen dat het geen geldige binaire zoekboom is

De binaire boom aan de rechterkant is geen binaire zoekboom omdat de rechter substructuur van knooppunt "3" een kleinere waarde bevat.

Er zijn twee basisbewerkingen die u kunt uitvoeren op een binaire zoekboom:

Zoekoperatie

Het algoritme hangt af van de eigenschap van BST dat als elke linker substructuur waarden onder de wortel heeft en elke rechtersubboom waarden boven de wortel heeft.

Als de waarde onder de wortel ligt, kunnen we zeker zeggen dat de waarde niet in de juiste substructuur staat; we hoeven alleen in de linker substructuur te zoeken en als de waarde boven de wortel is, kunnen we zeker zeggen dat de waarde niet in de linker substructuur staat; we hoeven alleen in de juiste substructuur te zoeken.

Algoritme:

 If root == NULL return NULL; If number == root->data return root->data; If number data return search(root->left) If number> root->data return search(root->right)

Laten we dit proberen te visualiseren met een diagram.

4 is niet gevonden dus, doorlopen door de linker subboom van 8 4 wordt niet gevonden dus, doorlopen door de rechter subboom van 3 4 is niet gevonden dus, doorlopen door de linker subboom van 6 4 wordt gevonden

Als de waarde is gevonden, retourneren we de waarde zodat deze wordt gepropageerd in elke recursiestap, zoals weergegeven in de onderstaande afbeelding.

Als je het misschien gemerkt hebt, hebben we de return search (struct node *) vier keer aangeroepen. Wanneer we het nieuwe knooppunt of NULL retourneren, wordt de waarde keer op keer geretourneerd totdat search (root) het eindresultaat retourneert.

Als de waarde in een van de substructuren wordt gevonden, wordt deze naar boven gepropageerd zodat deze uiteindelijk wordt geretourneerd, anders wordt null geretourneerd

Als de waarde niet wordt gevonden, bereiken we uiteindelijk het linker- of rechterkind van een bladknooppunt dat NULL is en het wordt gepropageerd en geretourneerd.

Plaats operatie

Het invoegen van een waarde op de juiste positie is vergelijkbaar met zoeken, omdat we proberen de regel te handhaven dat de linker substructuur kleiner is dan de wortel en de rechter substructuur groter dan de wortel.

We blijven naar de rechter substructuur of de linker substructuur gaan, afhankelijk van de waarde en wanneer we een punt bereiken dat de linker of rechter substructuur nul is, plaatsen we het nieuwe knooppunt daar.

Algoritme:

 If node == NULL return createNode(data) if (data data) node->left = insert(node->left, data); else if (data> node->data) node->right = insert(node->right, data); return node;

Het algoritme is niet zo eenvoudig als het lijkt. Laten we proberen te visualiseren hoe we een nummer toevoegen aan een bestaande BST.

4 <8 dus, dwars door het linkerkind van 8 4> 3 dus, dwars door het rechterkind van 8 4 <6 dus, dwars door het linkerkind van 6 Insert 4 als een linkerkind van 6

We hebben het knooppunt vastgemaakt, maar we moeten nog steeds de functie verlaten zonder de rest van de boom te beschadigen. Dit is waar het return node;einde van pas komt. In het geval van NULLwordt het nieuw gemaakte knooppunt geretourneerd en gekoppeld aan het bovenliggende knooppunt, anders wordt hetzelfde knooppunt zonder enige verandering geretourneerd totdat we terugkeren naar de root.

Dit zorgt ervoor dat als we teruggaan in de boom, de andere knooppuntverbindingen niet worden gewijzigd.

Afbeelding die het belang toont van het terugkeren van het wortelelement aan het einde, zodat de elementen hun positie niet verliezen tijdens de opwaartse recursiestap.

Verwijderen

Er zijn drie gevallen voor het verwijderen van een knooppunt uit een binaire zoekboom.

Geval I

In het eerste geval is het te verwijderen knooppunt het bladknooppunt. In dat geval verwijdert u eenvoudig het knooppunt uit de boomstructuur.

4 moet worden verwijderd. Verwijder de knoop

Geval II

In het tweede geval heeft het te verwijderen knooppunt één enkel kindknooppunt. Volg in dat geval de onderstaande stappen:

1. Vervang dat knooppunt door het onderliggende knooppunt.
2. Verwijder het onderliggende knooppunt uit zijn oorspronkelijke positie.

6 moet worden verwijderd, kopieer de waarde van zijn kind naar het knooppunt en verwijder de onderliggende definitieve boom

Geval III

In het derde geval heeft het te verwijderen knooppunt twee kinderen. Volg in dat geval de onderstaande stappen:

1. Haal de volgende opvolger van dat knooppunt op.
2. Vervang het knooppunt door de opvolger in volgorde.
3. Verwijder de volgende opvolger uit zijn oorspronkelijke positie.

3 moet worden verwijderd Kopieer de waarde van de in volgorde opvolger (4) naar het knooppunt Verwijder de in volgorde opvolger

Python, Java en C / C ++ voorbeelden

Python Java C C ++

 # Binary Search Tree operations in Python # Create a node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Inorder traversal def inorder(root): if root is not None: # Traverse left inorder(root.left) # Traverse root print(str(root.key) + "->", end=' ') # Traverse right inorder(root.right) # Insert a node def insert(node, key): # Return a new node if the tree is empty if node is None: return Node(key) # Traverse to the right place and insert the node if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node # Find the inorder successor def minValueNode(node): current = node # Find the leftmost leaf while(current.left is not None): current = current.left return current # Deleting a node def deleteNode(root, key): # Return if the tree is empty if root is None: return root # Find the node to be deleted if key root.key): root.right = deleteNode(root.right, key) else: # If the node is with only one child or no child if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # If the node has two children, # place the inorder successor in position of the node to be deleted temp = minValueNode(root.right) root.key = temp.key # Delete the inorder successor root.right = deleteNode(root.right, temp.key) return root root = None root = insert(root, 8) root = insert(root, 3) root = insert(root, 1) root = insert(root, 6) root = insert(root, 7) root = insert(root, 10) root = insert(root, 14) root = insert(root, 4) print("Inorder traversal: ", end=' ') inorder(root) print("Delete 10") root = deleteNode(root, 10) print("Inorder traversal: ", end=' ') inorder(root)

 // Binary Search Tree operations in Java class BinarySearchTree ( class Node ( int key; Node left, right; public Node(int item) ( key = item; left = right = null; ) ) Node root; BinarySearchTree() ( root = null; ) void insert(int key) ( root = insertKey(root, key); ) // Insert key in the tree Node insertKey(Node root, int key) ( // Return a new node if the tree is empty if (root == null) ( root = new Node(key); return root; ) // Traverse to the right place and insert the node if (key root.key) root.right = insertKey(root.right, key); return root; ) void inorder() ( inorderRec(root); ) // Inorder Traversal void inorderRec(Node root) ( if (root != null) ( inorderRec(root.left); System.out.print(root.key + " -> "); inorderRec(root.right); ) ) void deleteKey(int key) ( root = deleteRec(root, key); ) Node deleteRec(Node root, int key) ( // Return if the tree is empty if (root == null) return root; // Find the node to be deleted if (key root.key) root.right = deleteRec(root.right, key); else ( // If the node is with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // If the node has two children // Place the inorder successor in position of the node to be deleted root.key = minValue(root.right); // Delete the inorder successor root.right = deleteRec(root.right, root.key); ) return root; ) // Find the inorder successor int minValue(Node root) ( int minv = root.key; while (root.left != null) ( minv = root.left.key; root = root.left; ) return minv; ) // Driver Program to test above functions public static void main(String() args) ( BinarySearchTree tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(4); System.out.print("Inorder traversal: "); tree.inorder(); System.out.println("After deleting 10"); tree.deleteKey(10); System.out.print("Inorder traversal: "); tree.inorder(); ) )

 // Binary Search Tree operations in C #include #include struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root printf("%d -> ", root->key); // Traverse right inorder(root->right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); printf("Inorder traversal: "); inorder(root); printf("After deleting 10"); root = deleteNode(root, 10); printf("Inorder traversal: "); inorder(root); )

 // Binary Search Tree operations in C++ #include using namespace std; struct node ( int key; struct node *left, *right; ); // Create a node struct node *newNode(int item) ( struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; ) // Inorder Traversal void inorder(struct node *root) ( if (root != NULL) ( // Traverse left inorder(root->left); // Traverse root cout  right); ) ) // Insert a node struct node *insert(struct node *node, int key) ( // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; ) // Find the inorder successor struct node *minValueNode(struct node *node) ( struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; ) // Deleting a node struct node *deleteNode(struct node *root, int key) ( // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key key) root->left = deleteNode(root->left, key); else if (key> root->key) root->right = deleteNode(root->right, key); else ( // If the node is with only one child or no child if (root->left == NULL) ( struct node *temp = root->right; free(root); return temp; ) else if (root->right == NULL) ( struct node *temp = root->left; free(root); return temp; ) // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); ) return root; ) // Driver code int main() ( struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); cout << "Inorder traversal: "; inorder(root); cout << "After deleting 10"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorder(root); ) 

Complexiteit van binaire zoekboom

Tijdscomplexiteit

Operatie	Complexiteit in het beste geval	Gemiddelde casuscomplexiteit	Complexiteit in het ergste geval
Zoeken	O (logboek n)	O (logboek n)	Aan)
Invoeging	O (logboek n)	O (logboek n)	Aan)
Verwijdering	O (logboek n)	O (logboek n)	Aan)

Hier is n het aantal knooppunten in de boomstructuur.

Complexiteit van de ruimte

De ruimtecomplexiteit voor alle bewerkingen is O (n).

Binaire zoekboomtoepassingen

1. Bij indexering op meerdere niveaus in de database
2. Voor dynamisch sorteren
3. Voor het beheren van virtuele geheugengebieden in de Unix-kernel