Binärer Suchbaum

In diesem Tutorial erfahren Sie, wie der binäre Suchbaum funktioniert. Außerdem finden Sie Arbeitsbeispiele für den binären Suchbaum in C, C ++, Java und Python.

Der binäre Suchbaum ist eine Datenstruktur, mit der wir schnell eine sortierte Liste von Zahlen verwalten können.

Es wird als Binärbaum bezeichnet, da jeder Baumknoten maximal zwei untergeordnete Elemente hat.
Es wird als Suchbaum bezeichnet, da damit nach dem Vorhandensein einer Zahl in der O(log(n))Zeit gesucht werden kann .

Die Eigenschaften, die einen binären Suchbaum von einem regulären binären Baum trennen, sind

Alle Knoten des linken Teilbaums sind kleiner als der Wurzelknoten
Alle Knoten des rechten Teilbaums sind mehr als der Wurzelknoten
Beide Teilbäume jedes Knotens sind auch BSTs, dh sie haben die beiden oben genannten Eigenschaften

Ein Baum mit einem rechten Teilbaum mit einem Wert, der kleiner als die Wurzel ist, zeigt, dass es sich nicht um einen gültigen binären Suchbaum handelt

Der Binärbaum rechts ist kein binärer Suchbaum, da der rechte Teilbaum des Knotens "3" einen kleineren Wert enthält.

Es gibt zwei grundlegende Operationen, die Sie für einen binären Suchbaum ausführen können:

Suchvorgang

Der Algorithmus hängt von der Eigenschaft von BST ab, dass jeder linke Teilbaum Werte unter der Wurzel und jeder rechte Teilbaum Werte über der Wurzel hat.

Wenn der Wert unter der Wurzel liegt, können wir sicher sagen, dass sich der Wert nicht im richtigen Teilbaum befindet. Wir müssen nur im linken Teilbaum suchen. Wenn der Wert über der Wurzel liegt, können wir mit Sicherheit sagen, dass sich der Wert nicht im linken Teilbaum befindet. Wir müssen nur im richtigen Teilbaum suchen.

Algorithmus:

 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)

Versuchen wir dies mit einem Diagramm zu visualisieren.

4 wird nicht so gefunden, Durchqueren des linken Teilbaums von 8

4 wird nicht gefunden, Durchqueren des rechten Teilbaums von 3

4 wird nicht gefunden, Traverse durch den linken Teilbaum von 6

4 wird gefunden

Wenn der Wert gefunden wird, geben wir den Wert zurück, damit er in jedem Rekursionsschritt weitergegeben wird (siehe Abbildung unten).

Wenn Sie es bemerkt haben, haben wir viermal die Rückgabesuche (Strukturknoten *) aufgerufen. Wenn wir entweder den neuen Knoten oder NULL zurückgeben, wird der Wert immer wieder zurückgegeben, bis search (root) das Endergebnis zurückgibt.

Wenn der Wert in einem der Teilbäume gefunden wird, wird er weitergegeben, sodass er am Ende zurückgegeben wird, andernfalls wird null zurückgegeben

Wenn der Wert nicht gefunden wird, erreichen wir schließlich das linke oder rechte untergeordnete Element eines Blattknotens, der NULL ist, und es wird weitergegeben und zurückgegeben.

Operation einfügen

Das Einfügen eines Werts an der richtigen Position ähnelt dem Suchen, da wir versuchen, die Regel beizubehalten, dass der linke Teilbaum kleiner als root und der rechte Teilbaum größer als root ist.

Je nach Wert wechseln wir entweder zum rechten oder zum linken Teilbaum. Wenn wir einen Punkt erreichen, an dem der linke oder rechte Teilbaum null ist, setzen wir den neuen Knoten dort ab.

Algorithmus:

 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;

Der Algorithmus ist nicht so einfach wie er aussieht. Versuchen wir zu visualisieren, wie wir einer vorhandenen BST eine Nummer hinzufügen.

4 <8 also quer durch das linke Kind von 8

4> 3 also quer durch das rechte Kind von 8

4 <6 also quer durch das linke Kind von 6

4 als linkes Kind von 6 einfügen

Wir haben den Knoten angehängt, müssen die Funktion jedoch noch verlassen, ohne den Rest des Baums zu beschädigen. Hier kommt das return node;am Ende zum Einsatz. Im Fall von NULLwird der neu erstellte Knoten zurückgegeben und an den übergeordneten Knoten angehängt, andernfalls wird derselbe Knoten unverändert zurückgegeben, wenn wir nach oben gehen, bis wir zum Stamm zurückkehren.

Dies stellt sicher, dass die anderen Knotenverbindungen beim Ändern des Baums nicht geändert werden.

Das Bild zeigt, wie wichtig es ist, das Wurzelelement am Ende zurückzugeben, damit die Elemente während des Aufwärtsrekursionsschritts nicht ihre Position verlieren.

Löschvorgang

Es gibt drei Fälle zum Löschen eines Knotens aus einem binären Suchbaum.

Fall I.

Im ersten Fall ist der zu löschende Knoten der Blattknoten. Löschen Sie in diesem Fall einfach den Knoten aus dem Baum.

4 ist zu löschen

Löschen Sie den Knoten

Fall II

Im zweiten Fall hat der zu löschende Knoten einen einzelnen untergeordneten Knoten. Führen Sie in einem solchen Fall die folgenden Schritte aus:

Ersetzen Sie diesen Knoten durch seinen untergeordneten Knoten.
Entfernen Sie den untergeordneten Knoten von seiner ursprünglichen Position.

6 soll gelöscht werden,

kopiere den Wert seines Kindes auf den Knoten und lösche den Kind-

Endbaum

Fall III

Im dritten Fall hat der zu löschende Knoten zwei untergeordnete Knoten. Führen Sie in diesem Fall die folgenden Schritte aus:

Holen Sie sich den Inorder-Nachfolger dieses Knotens.
Ersetzen Sie den Knoten durch den Inorder-Nachfolger.
Entfernen Sie den Inorder-Nachfolger aus seiner ursprünglichen Position.

3 ist zu löschen

Kopieren Sie den Wert des Inorder-Nachfolgers (4) in den Knoten.

Löschen Sie den Inorder-Nachfolger

Beispiele für Python, Java und C / C ++

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); )

Komplexität des binären Suchbaums

Zeitliche Komplexität

Operation	Best-Case-Komplexität	Durchschnittliche Fallkomplexität	Worst-Case-Komplexität
Suche	O (log n)	O (log n)	Auf)
Einfügen	O (log n)	O (log n)	Auf)
Streichung	O (log n)	O (log n)	Auf)