În acest tutorial, veți afla cum funcționează Arborele de căutare binară. De asemenea, veți găsi exemple de lucru ale arborelui de căutare binară în C, C ++, Java și Python.
Arborele de căutare binar este o structură de date care ne permite rapid să menținem o listă sortată de numere.
- Se numește copac binar, deoarece fiecare nod al copacului are maximum doi copii.
- Se numește copac de căutare, deoarece poate fi folosit pentru a căuta prezența unui număr în
O(log(n))timp.
Proprietățile care separă un copac binar de căutare de un copac binar obișnuit sunt
- Toate nodurile subarborelui stâng sunt mai mici decât nodul rădăcină
- Toate nodurile subarborelui drept sunt mai mult decât nodul rădăcină
- Ambele subarburi ale fiecărui nod sunt, de asemenea, BST, adică au cele două proprietăți de mai sus
Un arbore care are un subarborel drept cu o valoare mai mică decât rădăcina este arătat pentru a demonstra că nu este un arbore binar de căutare valid
Arborele binar din dreapta nu este un arbore binar de căutare, deoarece subarborele din dreapta al nodului „3” conține o valoare mai mică decât acesta.
Există două operații de bază pe care le puteți efectua pe un arbore de căutare binară:
Operațiunea de căutare
Algoritmul depinde de proprietatea BST că, dacă fiecare subarboroz din stânga are valori sub rădăcină și fiecare subarborescent drept are valori deasupra rădăcinii.
Dacă valoarea este sub rădăcină, putem spune cu siguranță că valoarea nu se află în subarborele potrivit; trebuie să căutăm numai în subarborele din stânga și dacă valoarea este deasupra rădăcinii, putem spune cu siguranță că valoarea nu se află în subarborele din stânga; trebuie să căutăm numai în subarborele potrivit.
Algoritm:
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)
Să încercăm să vizualizăm acest lucru cu o diagramă.
4 nu se găsește așa, traversează sub arborele stâng al lui 8 
4 nu se găsește așa, traversează sub arborele drept al lui 3 
4 nu se găsește așa, traversează sub arborele stâng al lui 6 4 este găsit
Dacă valoarea este găsită, returnăm valoarea astfel încât să fie propagată în fiecare etapă de recursivitate așa cum se arată în imaginea de mai jos.
Dacă ați fi observat, am apelat de patru ori căutare return (nod struct *). Când returnăm fie noul nod, fie NULL, valoarea este returnată din nou și din nou până când căutarea (rădăcina) returnează rezultatul final.
Dacă valoarea se găsește în oricare dintre subarburi, aceasta este propagată astfel încât în cele din urmă să fie returnată, altfel se returnează nul
Dacă valoarea nu este găsită, ajungem în cele din urmă la stânga sau la dreapta copilului unui nod frunză care este NULL și se propagă și se returnează.
Operațiunea de inserare
Introducerea unei valori în poziția corectă este similară căutării, deoarece încercăm să menținem regula conform căreia subarborele din stânga este mai mic decât rădăcina și subarborele din dreapta este mai mare decât rădăcina.
Continuăm să mergem la subarborele drept sau subarborele stâng în funcție de valoare și când ajungem la un punct subarborele stânga sau dreapta este nul, punem noul nod acolo.
Algoritm:
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;
Algoritmul nu este atât de simplu pe cât pare. Să încercăm să vizualizăm modul în care adăugăm un număr la un BST existent.
4 <8 deci, transversal prin copilul stâng al lui 8 
4> 3 deci, transversal prin copilul drept al lui 8 
4 <6 deci, transversal prin copilul stâng al lui 6 
Introduceți 4 ca un copil stâng de 6
Am atașat nodul, dar trebuie totuși să ieșim din funcție fără a afecta restul arborelui. Aici este return node;la îndemână sfârșitul. În cazul NULL, nodul nou creat este returnat și atașat nodului părinte, altfel același nod este returnat fără nicio modificare pe măsură ce urcăm până ne întoarcem la rădăcină.
Acest lucru ne asigură că, pe măsură ce ne deplasăm înapoi în copac, celelalte conexiuni de nod nu sunt modificate.
Imagine care arată importanța returnării elementului rădăcină la sfârșit, astfel încât elementele să nu-și piardă poziția în timpul pasului de recursiune în sus.
Operațiunea de ștergere
Există trei cazuri pentru ștergerea unui nod dintr-un arbore de căutare binară.
Cazul I
În primul caz, nodul care trebuie șters este nodul frunză. Într-un astfel de caz, pur și simplu ștergeți nodul din copac.
4 urmează să fie șters 
Ștergeți nodul
Cazul II
În al doilea caz, nodul care trebuie șters are un singur nod copil. Într-un astfel de caz, urmați pașii de mai jos:
- Înlocuiți acel nod cu nodul său copil.
- Scoateți nodul copil din poziția sa inițială.
6 trebuie șters 
copiați valoarea copilului său în nod și ștergeți 
arborele final copil
Cazul III
În al treilea caz, nodul care trebuie șters are doi copii. Într-un astfel de caz, urmați pașii de mai jos:
- Obțineți succesorul inorder al acelui nod.
- Înlocuiți nodul cu succesorul inorder.
- Scoateți succesorul inorder din poziția sa inițială.
3 urmează să fie șters Copiați valoarea succesorului inorder (4) în nod 
Ștergeți succesorul inorder
Exemple Python, Java și 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); )
Complexități arborescente de căutare binare
Complexitatea timpului
| Operațiune | Complexitatea celui mai bun caz | Complexitatea medie a cazurilor | Cel mai prost caz de complexitate |
| Căutare | O (jurnal n) | O (jurnal n) | Pe) |
| Inserare | O (jurnal n) | O (jurnal n) | Pe) |
| Ștergere | O (jurnal n) | O (jurnal n) | Pe) |
Aici, n este numărul de noduri din arbore.
Complexitatea spațială
Complexitatea spațiului pentru toate operațiile este O (n).
Aplicații pentru arborele de căutare binară
- În indexarea pe mai multe niveluri din baza de date
- Pentru sortare dinamică
- Pentru gestionarea zonelor de memorie virtuală în kernel-ul Unix
