Ebben az oktatóanyagban megtudhatja, hogyan működik a Binary Search Tree. Ezenkívül találhat működő példákat a bináris keresési fára C, C ++, Java és Python nyelven.
A bináris keresési fa egy olyan adatstruktúra, amely lehetővé teszi számunkra a rendezett számok felsorolását.
- Bináris fának hívják, mert minden facsomópontnak legfeljebb két gyermeke van.
- Kereső fának hívják, mert felhasználható arra, hogy
O(log(n))időben számot keressen egy szám jelenlétére .
Azok a tulajdonságok, amelyek elválasztják a bináris kereső fát a szabályos bináris fától
- A bal alfa összes csomópontja kevesebb, mint a gyökércsomópont
- A jobb részfa összes csomópontja több, mint a gyökércsomópont
- Minden csomópont mindkét alfája szintén BST, azaz a fenti két tulajdonsággal rendelkezik
Az a fa, amelynek egy jobb részfája van, amelynek értéke kisebb, mint a gyökér, megmutatja, hogy ez nem érvényes bináris keresési fa
A jobb oldali bináris fa nem bináris keresőfa, mert a "3" csomópont jobb alfája kisebb értéket tartalmaz.
Két alapvető műveletet hajthat végre egy bináris keresési fán:
Keresés művelet
Az algoritmus a BST azon tulajdonságától függ, hogy ha minden bal részfának gyökér alatti értékei vannak, és minden jobb részfának a gyökér felett vannak értékei.
Ha az érték a gyök alatt van, akkor biztosan kijelenthetjük, hogy az érték nincs a jobb részfán; csak a bal alfában kell keresnünk, és ha az érték a gyökér felett van, akkor biztosan kijelenthetjük, hogy az érték nincs a bal alfában; csak a megfelelő alfában kell keresnünk.
Algoritmus:
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)
Próbáljuk meg ezt ábrázolni.
A 4 nem található, a 8 bal bal 
részén keresztül 
nem haladunk 4
Ha megtalálta az értéket, akkor visszaadjuk az értéket úgy, hogy az minden rekurziós lépésben tovább terjedjen, ahogy az alábbi képen látható.
Ha észrevette, négyszer hívtuk meg a return keresést (struct csomópont *). Amikor visszaküldjük az új csomópontot vagy a NULL értéket, az érték újra és újra visszatér, amíg a keresés (root) vissza nem adja a végeredményt.
Ha az érték megtalálható bármelyik részfában, akkor azt fel kell terjeszteni úgy, hogy a végén visszatérjen, különben a null visszatér
Ha az érték nem található, akkor végül elérjük a levél csomópont bal vagy jobb gyermekét, amely NULL, és ez továbbterjed és visszatér.
Helyezze be a műveletet
Az érték helyes pozícióba történő beillesztése hasonló a kereséshez, mert megpróbáljuk fenntartani azt a szabályt, miszerint a bal részfa kisebb, mint a gyökér, a jobb részfa pedig nagyobb, mint a gyökér.
A jobb vagy a bal alfa felé haladunk az érték függvényében, és amikor elérünk egy pontot, a bal vagy a jobb részfa semmis, oda tesszük az új csomópontot.
Algoritmus:
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;
Az algoritmus nem olyan egyszerű, mint amilyennek látszik. Próbáljuk meg vizualizálni, hogyan adunk hozzá egy számot egy meglévő BST-hez.
4 <8 tehát, keresztirányban a 8 
4> 3 bal gyermekén keresztben, keresztben a 8 
4 <6 jobb oldali gyermekén , keresztben a 6 bal bal gyermekén keresztbe helyezve a 
4-et 6- os bal gyermekként
Csatoltuk a csomópontot, de még mindig ki kell lépnünk a funkcióból, anélkül, hogy a fa többi részét károsítanánk. Itt return node;jön jól a vége. Abban az esetben NULL, ha az újonnan létrehozott csomópont visszaküldik és csatolja a szülő csomópontot, különben ugyanaz a csomópont minden változás nélkül visszakerül, ahogy felfelé haladunk, amíg vissza nem térünk a gyökérhez.
Ez biztosítja, hogy amint visszafelé haladunk a fán, a többi csomópont kapcsolat nem változik.
Kép, amely megmutatja a gyökérelem visszatérésének fontosságát a végén, hogy az elemek ne veszítsék el helyzetüket a felfelé rekurziós lépés során.
Törlés művelet
Három esetben lehet törölni egy csomópontot egy bináris keresési fáról.
I. eset
Az első esetben a törlendő csomópont a levélcsomópont. Ilyen esetben egyszerűen törölje a csomópontot a fáról.
A 4-et törölni kell. 
Törölje a csomópontot
II. Eset
A második esetben a törölni kívánt csomópontnak egyetlen gyermekcsomópontja van. Ilyen esetben kövesse az alábbi lépéseket:
- Cserélje le ezt a csomópontot annak gyermekcsomópontjára.
- Távolítsa el a gyermekcsomópontot az eredeti helyzetéből.
A 6 törlendő, 
másolja gyermekének értékét a csomópontba, és törölje a gyermek 
végső fáját
III. Eset
A harmadik esetben a törlendő csomópontnak két gyermeke van. Ilyen esetben kövesse az alábbi lépéseket:
- Szerezd meg a csomópont belső utódját.
- Cserélje ki a csomópontot a belső utódra.
- Távolítsa el a belső utódot az eredeti helyzetéből.
A 3-at törölni kell. Másolja a megrendelés utódjának (4) értékét a csomópontba. 
Törölje a rendelt utódot
Példák Python, Java és 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); )
Bináris keresőfa komplexitások
Az idő komplexitása
| Művelet | Legjobb eset komplexitás | Átlagos esetösszetétel | Legrosszabb eset komplexitás |
| Keresés | O (log n) | O (log n) | Tovább) |
| Beszúrás | O (log n) | O (log n) | Tovább) |
| Törlés | O (log n) | O (log n) | Tovább) |
Itt n a fa csomópontjainak száma.
Tér komplexitás
Az összes művelet térbonyolultsága O (n).
Bináris keresőfa alkalmazások
- Többszintű indexelésben az adatbázisban
- Dinamikus rendezéshez
- Virtuális memóriaterületek kezeléséhez a Unix kernelben
