Šajā apmācībā jūs uzzināsiet, kā darbojas binārais meklēšanas koks. Jūs atradīsit arī binārā meklēšanas koka piemērus C, C ++, Java un Python.
Binārais meklēšanas koks ir datu struktūra, kas ļauj ātri uzturēt sakārtotu numuru sarakstu.
- To sauc par bināro koku, jo katrā koka mezglā ir ne vairāk kā divi bērni.
- To sauc par meklēšanas koku, jo to var izmantot, lai savlaicīgi meklētu skaitļa klātbūtni
O(log(n)).
Īpašības, kas atdala bināro meklēšanas koku no parastā binārā koka, ir
- Visi kreisās apakškoku mezgli ir mazāki par saknes mezglu
- Visi labās apakškoka mezgli ir vairāk nekā saknes mezgls
- Katra mezgla abas apakškokas ir arī BST, ti, tām ir iepriekš minētās divas īpašības
Tiek parādīts koks, kura labais apakškoks ir ar vienu vērtību, kas ir mazāka par sakni, lai parādītu, ka tas nav derīgs binārs meklēšanas koks
Labajā pusē esošais binārais koks nav binārs meklēšanas koks, jo mezgla "3" labajā apakškokā ir mazāka vērtība.
Binārajā meklēšanas kokā varat veikt divas pamata darbības:
Meklēšanas darbība
Algoritms ir atkarīgs no BST īpašības, ka, ja katrai kreisajai apakškokai ir vērtības zem saknes un katrai labajai apakškokai ir vērtības virs saknes.
Ja vērtība ir zem saknes, mēs varam droši apgalvot, ka vērtība nav pareizajā apakškokā; mums ir jāmeklē tikai kreisajā apakškokā un, ja vērtība ir virs saknes, mēs varam droši pateikt, ka vērtība nav kreisajā apakškokā; mums ir jāmeklē tikai pareizajā apakškokā.
Algoritms:
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)
Mēģināsim to vizualizēt ar diagrammu.
4 nav atrasts, šķērsojums pa 8 kreiso apakškoku 
4 nav atrasts, šķērsojums pa 3 
4 labo apakškoku nav atrasts, ir atrasts šķērsojums pa kreiso 6 4 apakškoku
Ja vērtība ir atrasta, mēs atgriežam vērtību tā, lai tā tiktu izplatīta katrā rekursijas posmā, kā parādīts zemāk esošajā attēlā.
Ja jūs, iespējams, pamanījāt, mēs esam četras reizes izsaukuši atgriešanās meklēšanu (struct mezgls *). Kad mēs atgriežam vai nu jauno mezglu, vai NULL, vērtība tiek atgriezta atkal un atkal, līdz meklēšana (sakne) atgriež galīgo rezultātu.
Ja vērtība ir atrodama kādā no apakkokiem, tā tiek pavairota uz augšu tā, ka beigās tā tiek atgriezta, pretējā gadījumā tiek atgriezta vērtība null
Ja vērtība netiek atrasta, mēs galu galā sasniedzam lapas mezgla kreiso vai labo bērnu, kas ir NULL, un tas tiek izplatīts un atgriezts.
Ievietot darbību
Vērtības ievietošana pareizajā pozīcijā ir līdzīga meklēšanai, jo mēs cenšamies saglabāt likumu, ka kreisais apakškoks ir mazāks par sakni un labais apakškoks ir lielāks par sakni.
Atkarībā no vērtības mēs turpinām iet vai nu pa labi, vai pa kreisi, un, sasniedzot punktu, kreisā vai labā apakškoks ir nulle, mēs tur ievietojam jauno mezglu.
Algoritms:
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;
Algoritms nav tik vienkāršs, kā izskatās. Mēģināsim vizualizēt, kā mēs pievienojam numuru esošam BST.
4 <8 so, šķērsvirzienā caur 8 
4> 3 kreiso bērnu , šķērsvirzienā caur 8 
4 <6 labo bērnu , šķērsvirzienā caur 6 kreiso bērnu 
Ievietojiet 4 kā kreiso bērnu no 6
Mēs esam pievienojuši mezglu, taču mums joprojām ir jāiziet no funkcijas, nekaitējot pārējam kokam. Šeit return node;noder beigu beigas. Gadījumā NULL, jaunizveidotais mezgls tiek atgriezts un pievienots vecākajam mezglam, pretējā gadījumā tas pats mezgls tiek atgriezts bez izmaiņām, ejot augšup, līdz atgriežamies pie saknes.
Tas nodrošina, ka, pārvietojoties atpakaļ kokā, pārējie mezglu savienojumi netiek mainīti.
Attēls, kurā parādīts, cik svarīgi ir atgriezt saknes elementu beigās, lai elementi nezaudētu savu pozīciju rekursijas augšup virzienā.
Dzēšanas darbība
Mezgla dzēšanai no binārā meklēšanas koka ir trīs gadījumi.
I gadījums
Pirmajā gadījumā dzēšamais mezgls ir lapu mezgls. Šādā gadījumā vienkārši izdzēsiet mezglu no koka.
4 ir jāsvītro 
Dzēsiet mezglu
II gadījums
Otrajā gadījumā dzēšamajam mezglam ir viens bērna mezgls. Šādā gadījumā rīkojieties šādi:
- Nomainiet šo mezglu ar tā apakšmezglu.
- Noņemiet bērna mezglu no sākotnējā stāvokļa.
6 ir jāizdzēš, 
kopējiet tā bērna vērtību uz mezglu un izdzēsiet bērna 
gala koku
III gadījums
Trešajā gadījumā dzēšamajam mezglam ir divi bērni. Šādā gadījumā rīkojieties šādi:
- Iegūstiet šī mezgla kārtējo pēcteci.
- Nomainiet mezglu ar pasūtījuma pēcteci.
- Noņemiet pasūtījuma pēcteci no sākotnējā stāvokļa.
3 ir jāsvītro Kopējiet pasūtījuma pēctecības (4) vērtību mezglā 
Dzēst pasūtījuma pēcteci
Python, Java un C / C ++ piemēri
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āro meklēšanas koku sarežģītība
Laika sarežģītība
| Darbība | Labākā gadījuma sarežģītība | Vidējā lietu sarežģītība | Sliktākā gadījuma sarežģītība |
| Meklēt | O (log n) | O (log n) | O (n) |
| Ievietošana | O (log n) | O (log n) | O (n) |
| Dzēšana | O (log n) | O (log n) | O (n) |
Šeit n ir koku mezglu skaits.
Kosmosa sarežģītība
Kosmosa sarežģītība visām operācijām ir O (n).
Bināro meklēšanas koku lietojumprogrammas
- Daudzlīmeņu indeksēšanā datu bāzē
- Dinamiskai šķirošanai
- Virtuālās atmiņas apgabalu pārvaldīšanai Unix kodolā
