I denne veiledningen vil du lære hvordan Binary Search Tree fungerer. Du finner også arbeidseksempler på Binary Search Tree i C, C ++, Java og Python.
Binært søketre er en datastruktur som raskt lar oss opprettholde en sortert nummerliste.
- Det kalles et binært tre fordi hvert treknutepunkt har maksimalt to barn.
- Det kalles et søketre fordi det kan brukes til å søke etter et tall i
O(log(n))tiden.
Egenskapene som skiller et binært søketre fra et vanlig binært tre er
- Alle noder i venstre undertre er mindre enn rotnoden
- Alle noder med høyre undertre er mer enn rotnoden
- Begge undertrærne til hver node er også BST, dvs. de har de to ovennevnte egenskapene
Et tre som har riktig undertre med en verdi mindre enn roten, vises for å demonstrere at det ikke er et gyldig binært søketre
Det binære treet til høyre er ikke et binært søketre fordi det høyre undertreet til noden "3" inneholder en verdi som er mindre enn det.
Det er to grunnleggende operasjoner du kan utføre på et binært søketre:
Søkeoperasjon
Algoritmen avhenger av egenskapen til BST at hvis hvert venstre undertre har verdier under roten og hvert høyre undertre har verdier over roten.
Hvis verdien er under roten, kan vi si med sikkerhet at verdien ikke er i riktig undertre; vi trenger bare å søke i venstre undertre, og hvis verdien er over roten, kan vi med sikkerhet si at verdien ikke er i venstre undertre; vi trenger bare å søke i riktig undertre.
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)
La oss prøve å visualisere dette med et diagram.
4 er ikke funnet så, krysser gjennom venstre undertre av 8 
4 er ikke funnet så, krysser gjennom høyre undertre av 3 
4 er ikke funnet så, krysser gjennom venstre undertre av 6 4 er funnet
Hvis verdien blir funnet, returnerer vi verdien slik at den blir spredt i hvert rekursjonstrinn som vist på bildet nedenfor.
Hvis du kanskje har lagt merke til det, har vi ringt retursøk (struct node *) fire ganger. Når vi returnerer enten den nye noden eller NULL, blir verdien returnert igjen og igjen til search (root) returnerer det endelige resultatet.
Hvis verdien finnes i noen av undertrærene, forplantes den opp slik at den til slutt returneres, ellers returneres null
Hvis verdien ikke blir funnet, når vi til slutt barnet til venstre eller høyre for en bladnode som er NULL, og den blir forplantet og returnert.
Sett inn drift
Å sette inn en verdi i riktig posisjon ligner på å søke fordi vi prøver å opprettholde regelen om at venstre undertre er mindre enn rot og høyre undertre er større enn rot.
Vi fortsetter til enten høyre undertre eller venstre undertre avhengig av verdien, og når vi når et punkt er venstre eller høyre undertre null, setter vi den nye noden der.
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;
Algoritmen er ikke så enkel som den ser ut. La oss prøve å visualisere hvordan vi legger til et nummer til en eksisterende BST.
4 <8 så, tverrgående gjennom venstre barn av 8 
4> 3 så, tverrgående gjennom høyre barn av 8 
4 <6 så, tverrgående gjennom venstre barn av 6 
Sett inn 4 som venstre barn på 6
Vi har festet noden, men vi må fortsatt gå ut av funksjonen uten å skade resten av treet. Det er her return node;slutten kommer til nytte. I tilfelle NULLreturneres den nyopprettede noden og festes til foreldrenoden, ellers returneres den samme noden uten noen endring når vi går opp til vi går tilbake til roten.
Dette sørger for at når vi beveger oss oppover treet, endres ikke de andre nodeforbindelsene.
Bilde som viser viktigheten av å returnere rotelementet på slutten slik at elementene ikke mister sin posisjon under trinnet oppover.
Slettingsoperasjon
Det er tre tilfeller for å slette en node fra et binært søketre.
Sak I
I det første tilfellet er noden som skal slettes bladnoden. I et slikt tilfelle er det bare å slette noden fra treet.
4 skal slettes. 
Slett noden
Sak II
I det andre tilfellet har noden som skal slettes, en enkelt undernode. I slike tilfeller følger du trinnene nedenfor:
- Erstatt den noden med den underordnede noden.
- Fjern underordnet node fra sin opprinnelige posisjon.
6 skal slettes, 
kopier verdien av barnet sitt til noden og slett det 
endelige treet
Sak III
I det tredje tilfellet har noden som skal slettes to barn. I slike tilfeller følger du trinnene nedenfor:
- Få etterfølgeren til den noden.
- Bytt ut noden med etterfølgeren.
- Fjern ordren etterfølgeren fra sin opprinnelige posisjon.
3 skal slettes Kopier verdien av ordren etterfølgeren (4) til noden 
Slett ordren etterfølgeren
Python, Java og C / C ++ eksempler
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); )
Binære søketre-kompleksiteter
Tidskompleksitet
| Operasjon | Beste sakskompleksitet | Gjennomsnittlig sakskompleksitet | Verste sakskompleksitet |
| Søk | O (log n) | O (log n) | På) |
| Innsetting | O (log n) | O (log n) | På) |
| Sletting | O (log n) | O (log n) | På) |
Her er n antall noder i treet.
Romkompleksitet
Romkompleksiteten for alle operasjonene er O (n).
Binære søketre-applikasjoner
- I indeksering på flere nivåer i databasen
- For dynamisk sortering
- For administrering av virtuelle minneområder i Unix-kjernen
