V tej vadnici boste izvedeli, kako deluje binarno drevo iskanja. Prav tako boste našli delovne primere binarnega drevesa iskanja v C, C ++, Java in Python.
Binarno drevo iskanja je podatkovna struktura, ki nam hitro omogoča, da vzdržujemo razvrščen seznam številk.
- Imenuje se binarno drevo, ker ima vsako vozlišče drevesa največ dva otroka.
- Išče se drevo iskanja, ker se z njim lahko pravočasno išče prisotnost številke
O(log(n)).
Lastnosti, ki ločujejo binarno drevo iskanja od običajnega binarnega drevesa, so
- Vsa vozlišča levega poddrevesa so manjša od korenskega vozlišča
- Vsa vozlišča desnega poddrevesa so več kot korensko vozlišče
- Oba poddrevesa vsakega vozlišča sta tudi BST, tj. Imata zgornji dve lastnosti
Drevo, ki ima desno poddrevo z eno vrednostjo, manjšo od korena, prikazuje, da ni veljavno binarno drevo iskanja
Binarno drevo na desni strani ni binarno drevo iskanja, ker desno poddrevo vozlišča "3" vsebuje vrednost, manjšo od njega.
Na drevesu binarnega iskanja lahko izvedete dve osnovni operaciji:
Iskalna operacija
Algoritem je odvisen od lastnosti BST, da če ima vsako levo poddrevo vrednosti pod korenom in vsako desno poddrevo vrednosti nad korenom.
Če je vrednost pod korenom, lahko zagotovo trdimo, da vrednost ni v pravem poddrevesu; iskati moramo le v levem poddrevesu in če je vrednost nad korenom, lahko zagotovo trdimo, da vrednost ni v levem poddrevesu; iskati moramo samo v pravem poddrevesu.
Algoritem:
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)
Poskusimo si to ponazoriti s pomočjo diagrama.
4 ni mogoče najti, prečka skozi levo poddrevo 8 
4 ni mogoče najti, prečka skozi desno poddrevo 3 
4 ni mogoče najti, prečenje skozi levo poddrevo 6 4 je najdeno
Če je vrednost najdena, jo vrnemo tako, da se razširi v vsakem koraku ponovitve, kot je prikazano na spodnji sliki.
Če ste morda opazili, smo štirikrat poklicali vrnitev iskanja (strukturno vozlišče *). Ko vrnemo bodisi novo vozlišče bodisi NULL, se vrednost vrne znova in znova, dokler iskanje (root) ne vrne končnega rezultata.
Če je vrednost najdena v katerem koli poddrevesu, se razširi navzgor, tako da je na koncu vrnjena, sicer pa vrne null
Če vrednosti ne najdemo, sčasoma pridemo do levega ali desnega podrejenega listnega vozlišča, ki je NULL, in se razmnoži in vrne.
Vstavite postopek
Vstavljanje vrednosti v pravilen položaj je podobno iskanju, ker poskušamo ohraniti pravilo, da je levo poddrevo manjše od korenskega, desno poddrevesno pa večje od korenskega.
Nadaljujemo v desno ali levo poddrevo, odvisno od vrednosti, in ko pridemo do točke, je levo ali desno poddrevo nično, novo vozlišče postavimo tja.
Algoritem:
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;
Algoritem ni tako preprost, kot je videti. Poskusimo si predstaviti, kako dodamo številko obstoječemu BST.
4 <8 torej, prečno skozi levega otroka 8 
4> 3 torej, prečno skozi desnega otroka 8 
4 <6 torej, prečno skozi levega otroka 6 
Vstavite 4 kot levi otrok 6
Vozlišče smo pritrdili, vendar moramo še vedno zapustiti funkcijo, ne da bi poškodovali preostalo drevo. Tule return node;na koncu pride prav. V primeru NULLse novo ustvarjeno vozlišče vrne in pritrdi na nadrejeno vozlišče, sicer pa se isto vozlišče vrne brez sprememb, ko gremo navzgor, dokler se ne vrnemo v koren.
To zagotavlja, da se med premikanjem nazaj po drevesu druge povezave vozlišč ne spremenijo.
Slika, ki prikazuje pomembnost vrnitve korenskega elementa na koncu, tako da elementi ne bodo izgubili svojega položaja med korakom rekurzije navzgor.
Postopek brisanja
Obstajajo trije primeri brisanja vozlišča iz binarnega drevesa iskanja.
Primer I
V prvem primeru je vozlišče, ki ga je treba izbrisati, vozlišče listov. V takem primeru vozlišče preprosto izbrišete iz drevesa.
4 je treba izbrisati. 
Izbrišite vozlišče
Primer II
V drugem primeru ima vozlišče, ki ga je treba izbrisati, eno podrejeno vozlišče. V takem primeru sledite spodnjim korakom:
- Nadomestite to vozlišče z njegovim podrejenim vozliščem.
- Odstranite podrejeno vozlišče s prvotnega položaja.
6 je treba izbrisati, 
kopirajte vrednost njegovega podrejenega v vozlišče in izbrišite podrejeno 
končno drevo
Primer III
V tretjem primeru ima vozlišče, ki ga je treba izbrisati, dva otroka. V takem primeru sledite spodnjim korakom:
- Pridobite naslednika tega vozlišča.
- Zamenjajte vozlišče z naslednikom inorder.
- Odstranite naslednika inorder s prvotnega položaja.
3 je treba izbrisati Kopirajte vrednost naslednika inorder (4) v vozlišče 
Izbrišite naslednika inorder
Primeri Python, Java in 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); )
Kompleksnosti binarnega drevesa iskanja
Zapletenost časa
| Delovanje | Najboljši primer zapletenosti | Povprečna zapletenost primera | Najslabša zapletenost |
| Iskanje | O (log n) | O (log n) | O (n) |
| Vstavitev | O (log n) | O (log n) | O (n) |
| Izbris | O (log n) | O (log n) | O (n) |
Tu je n število vozlišč v drevesu.
Zapletenost prostora
Prostorska zapletenost vseh operacij je O (n).
Aplikacije binarnega drevesa iskanja
- Pri indeksiranju na več ravneh v zbirki podatkov
- Za dinamično razvrščanje
- Za upravljanje območij navideznega pomnilnika v jedru Unix
