I denne vejledning lærer du, hvordan Binary Search Tree fungerer. Du finder også arbejdseksempler på Binary Search Tree i C, C ++, Java og Python.
Binært søgetræ er en datastruktur, der hurtigt giver os mulighed for at opretholde en sorteret nummerliste.
- Det kaldes et binært træ, fordi hvert træknudepunkt maksimalt har to børn.
- Det kaldes et søgetræ, fordi det kan bruges til at søge efter tilstedeværelsen af et nummer i
O(log(n))tide.
Egenskaberne, der adskiller et binært søgetræ fra et almindeligt binært træ er
- Alle noder i venstre undertræ er mindre end rodnoden
- Alle noder med højre undertræ er mere end rodnoden
- Begge undertræer for hver knude er også BST'er, dvs. de har de ovennævnte to egenskaber
Et træ med et rigtigt undertræ med en værdi mindre end roden vises for at demonstrere, at det ikke er et gyldigt binært søgetræ
Det binære træ til højre er ikke et binært søgetræ, fordi det højre undertræ i noden "3" indeholder en værdi, der er mindre end det.
Der er to grundlæggende handlinger, som du kan udføre på et binært søgetræ:
Søgning
Algoritmen afhænger af BST's egenskab, at hvis hvert venstre undertræ har værdier under roden, og hvert højre undertræ har værdier over roden.
Hvis værdien er under roden, kan vi med sikkerhed sige, at værdien ikke er i det rigtige undertræ; vi behøver kun at søge i venstre undertræ, og hvis værdien er over roden, kan vi med sikkerhed sige, at værdien ikke er i venstre undertræ; vi skal kun søge i det rigtige undertræ.
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)
Lad os prøve at visualisere dette med et diagram.
4 findes ikke så, krydser gennem venstre undertræ af 8 
4 findes ikke så, krydser gennem højre undertræ på 3 
4 findes ikke, krydser gennem venstre undertræ 6 6 findes
Hvis værdien findes, returnerer vi værdien, så den forplantes i hvert rekursionstrin som vist på billedet nedenfor.
Hvis du måske har bemærket det, har vi ringet til retursøgning (struct node *) fire gange. Når vi returnerer enten den nye node eller NULL, returneres værdien igen og igen, indtil søgning (root) returnerer det endelige resultat.
Hvis værdien findes i nogen af undertrærne, forplantes den op, så den til sidst returneres, ellers returneres null
Hvis værdien ikke findes, når vi til sidst til venstre eller højre barn af en bladknude, der er NULL, og den formeres og returneres.
Indsæt operation
At indsætte en værdi i den rigtige position svarer til søgning, fordi vi forsøger at opretholde reglen om, at venstre undertræ er mindre end rod, og det højre undertræ er større end rod.
Vi fortsætter med at gå til enten højre undertræ eller venstre undertræ afhængigt af værdien, og når vi når et punkt er venstre eller højre undertræ nul, sætter vi den nye node 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 ud. Lad os prøve at visualisere, hvordan vi føjer et nummer til en eksisterende BST.
4 <8 så, på tværs gennem venstre barn af 8 
4> 3 så, på tværs gennem højre barn på 8 
4 <6 så, på tværs gennem venstre barn af 6 
Indsæt 4 som et venstre barn på 6
Vi har knyttet knuden, men vi skal stadig forlade funktionen uden at skade resten af træet. Det er her return node;slutningen kommer til nytte. I tilfælde af NULLreturneres den nyoprettede node og knyttes til den overordnede node, ellers returneres den samme node uden nogen ændring, når vi går op, indtil vi vender tilbage til roden.
Dette sørger for, at når vi bevæger os tilbage op i træet, ændres de andre knudeforbindelser ikke.
Billede, der viser vigtigheden af at returnere rodelementet i slutningen, så elementerne ikke mister deres position under det opadgående rekursionstrin.
Sletning
Der er tre tilfælde til sletning af en node fra et binært søgetræ.
Sag I
I det første tilfælde er noden, der skal slettes, bladnoden. I et sådant tilfælde skal du blot slette noden fra træet.
4 skal slettes 
Slet noden
Sag II
I det andet tilfælde har noden, der skal slettes, en enkelt undernode. I et sådant tilfælde skal du følge nedenstående trin:
- Udskift den node med dens underknude.
- Fjern underordnet knude fra dets oprindelige position.
6 skal slettes, 
kopier værdien af sit barn til noden og slet det 
sidste barn
Sag III
I det tredje tilfælde har den knude, der skal slettes, to børn. I et sådant tilfælde skal du følge nedenstående trin:
- Få efterfølgeren til den node.
- Udskift noden med efterfølgeren til ordren.
- Fjern efterfølgeren til ordren fra sin oprindelige position.
3 skal slettes Kopier værdien af ordrefølgeren (4) til noden 
Slet ordrefø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øgetræskompleksiteter
Tidskompleksitet
| Operation | Bedste sagskompleksitet | Gennemsnitlig sagskompleksitet | Kompleksitet i værste tilfælde |
| Søg | O (log n) | O (log n) | På) |
| Indskud | O (log n) | O (log n) | På) |
| Sletning | O (log n) | O (log n) | På) |
Her er n antallet af noder i træet.
Rumkompleksitet
Rumkompleksiteten for alle operationer er O (n).
Binære søgetræsapplikationer
- I indeksering på flere niveauer i databasen
- Til dynamisk sortering
- Til styring af virtuelle hukommelsesområder i Unix-kernen
