Tässä opetusohjelmassa opit, kuinka Binary Search Tree toimii. Löydät myös toimivia esimerkkejä binäärihakupuusta C-, C ++ -, Java- ja Python-tiedostoissa.
Binaarinen hakupuu on tietorakenne, jonka avulla voimme nopeasti ylläpitää lajiteltu luettelo numeroista.
- Sitä kutsutaan binääripuuksi, koska jokaisessa puun solmussa on enintään kaksi lasta.
- Sitä kutsutaan hakupuuksi, koska sitä voidaan käyttää etsimään luvun läsnäoloa
O(log(n))ajoissa.
Ominaisuudet, jotka erottavat binäärisen hakupuun tavallisesta binääripuusta, ovat
- Kaikki vasemman alipuun solmut ovat pienempiä kuin juurisolmu
- Kaikki oikean alipuun solmut ovat enemmän kuin juurisolmu
- Jokaisen solmun molemmat alipuut ovat myös BST: itä, ts. Niillä on kaksi yllä olevaa ominaisuutta
Puun, jolla on oikea alipuu, jonka arvo on pienempi kuin juuri, osoitetaan osoittavan, että se ei ole kelvollinen binaarinen hakupuu
Oikealla oleva binääripuu ei ole binäärinen hakupuu, koska solmun "3" oikea alipuu sisältää sitä pienemmän arvon.
Binaarihakupuussa voidaan suorittaa kaksi perustoimintoa:
Hakutoiminto
Algoritmi riippuu BST: n ominaisuudesta, että jos jokaisella vasemmalla alipuussa on juuren alapuolella olevat arvot ja jokaisella oikealla alipuussa juuren yläpuolella.
Jos arvo on juuren alapuolella, voimme varmasti sanoa, että arvo ei ole oikeassa alipuussa; meidän on etsittävä vain vasemmasta alipuusta ja jos arvo on juuren yläpuolella, voimme sanoa varmasti, että arvo ei ole vasemmalla alipuussa; meidän on etsittävä vain oikeasta alipuusta.
Algoritmi:
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)
Yritetään visualisoida tämä kaavion avulla.
4 ei löydy niin, poikkisuunta vasemmasta 8 osasta 
4 4 ei löydy niin, 3 
4 oikean osapuun läpi ei löydy niin, 6 4 vasemman osapuun läpi löytyy
Jos arvo löytyy, palautamme arvon siten, että se etenee jokaisessa rekursiovaiheessa alla olevan kuvan mukaisesti.
Jos olet ehkä huomannut, olemme kutsuneet paluuhakua (struct solmu *) neljä kertaa. Kun palautamme joko uuden solmun tai NULL-arvon, arvo palautetaan uudestaan ja uudestaan, kunnes haku (juuri) palauttaa lopullisen tuloksen.
Jos arvo löytyy jostakin alipuusta, se levitetään ylöspäin niin, että lopulta se palautetaan, muuten null palautetaan
Jos arvoa ei löydy, saavutamme lopulta NULL-lehtisolmun vasemman tai oikean lapsen ja se levitetään ja palautetaan.
Lisää toiminta
Arvon lisääminen oikeaan kohtaan on samanlainen kuin haku, koska yritämme ylläpitää sääntöä, jonka mukaan vasen osa on pienempi kuin juuri ja oikea osa on suurempi kuin juuri.
Jatkamme joko oikealle tai vasemmalle alipuulle arvon mukaan ja kun saavutamme pisteen, vasen tai oikea alipuu on tyhjä, laitamme uuden solmun sinne.
Algoritmi:
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;
Algoritmi ei ole niin yksinkertainen kuin miltä se näyttää. Yritetään visualisoida, kuinka lisätään numero olemassa olevaan BST: hen.
4 <8 niin, poikittain 8 
4> 3: n vasemman lapsen läpi, poikittain 8 
4 <6: n oikean lapsen läpi, poikittain 6: n vasemman lapsen läpi 
Aseta 4 kuin 6 : n vasen lapsi
Olemme liittäneet solmun, mutta meidän on silti poistuttava toiminnosta tekemättä mitään vahinkoa muulle puulle. Täällä return node;loppu on kätevä. Tällöin NULLuusi luotu solmu palautetaan ja liitetään yläsolmuun, muuten sama solmu palautetaan ilman muutoksia, kun nousemme ylöspäin, kunnes palaamme juurelle.
Tämä varmistaa, että kun siirrymme takaisin puuhun, muita solmuyhteyksiä ei muuteta.
Kuva, joka osoittaa juurielementin palauttamisen tärkeyden lopussa, jotta elementit eivät menetä asemaansa ylöspäin tapahtuvan rekursiovaiheen aikana.
Poistotoiminto
Solmun poistamiseksi binaarihakupuusta on kolme tapausta.
Tapaus I
Ensimmäisessä tapauksessa poistettava solmu on lehtisolmu. Poista tällöin solmu yksinkertaisesti puusta.
4 on poistettava 
Poista solmu
Tapaus II
Toisessa tapauksessa poistettavalla solmulla on yksi alisolmu. Noudata tällöin seuraavia ohjeita:
- Korvaa kyseinen solmu lapsisolmulla.
- Irrota lapsisolmu alkuperäisestä asemastaan.
6 on poistettava, 
kopioi alatasonsa arvo solmuun ja poista 
alipuun loppupuu
Tapaus III
Kolmannessa tapauksessa poistettavalla solmulla on kaksi lasta. Noudata tällöin seuraavia vaiheita:
- Hanki kyseisen solmun sisäinen seuraaja.
- Korvaa solmu sisäisellä seuraajalla.
- Poista sisäinen seuraaja alkuperäisestä asemastaan.
3 on poistettava Kopioi tilauksen seuraaja (4) arvo solmuun 
Poista tilattava seuraaja
Python-, Java- ja C / C ++ -esimerkkejä
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); )
Binaarihakupuun monimutkaisuus
Ajan monimutkaisuus
| Operaatio | Parhaan tapauksen monimutkaisuus | Keskimääräinen tapauksen monimutkaisuus | Pahimman tapauksen monimutkaisuus |
| Hae | O (log n) | O (log n) | Päällä) |
| Lisäys | O (log n) | O (log n) | Päällä) |
| Poistaminen | O (log n) | O (log n) | Päällä) |
Tässä n on puun solmujen määrä.
Avaruuden monimutkaisuus
Kaikkien operaatioiden avaruuden monimutkaisuus on O (n).
Binaariset hakupuuohjelmat
- Monitasoisessa indeksoinnissa tietokannassa
- Dynaamiseen lajitteluun
- Virtuaalimuistialueiden hallintaan Unix-ytimessä
