Bináris fa az adatstruktúrában (PÉLDA)
Sarah Chen
⚡ Okos összefoglaló
A bináris fa az adatstruktúrában egy hierarchikus struktúra, ahol minden csomópontnak legfeljebb két gyermeke van, a bal és a jobb oldali. Ez az anyag ismerteti a bináris fákat, a bináris keresőfát, azok típusait, alkalmazásait és a teljes C nyelvet. C++és Python megvalósítások.
Mi az a bináris fa?
A bináris szó kettőt jelent. A fa adatszerkezetében a „bináris fa” olyan fát jelent, amelyben minden csomópontnak maximum két gyermekcsomópontja lehet (bal és jobb oldali csomópont). Ez egy egyszerű bináris fa.
Van azonban egy másik bináris fa, amelyet a leggyakrabban használnak, és számos felhasználási esettel rendelkezik. Bináris keresőfának (BST) hívják. Ez a fa sokkal gyorsabbá teheti a keresési algoritmust, pontosan log(n) időbonyolítással. Az adatstruktúrában n a bináris fa csomópontjainak számát jelenti.
Mi a különbség a bináris fa és a bináris keresőfa között?
A BST és a normál bináris fa közötti különbség abban van, hogy a BST bal oldali csomópont értéke kisebb, mint a gyökércsomóponté, a jobb oldali pedig nagyobb, mint a gyökércsomóponté. Tehát a bal oldali részfa mindig kisebb értéket fog tartalmazni, mint a gyökér, a jobb oldali részfa pedig mindig nagyobb értéket fog tartalmazni, mint a gyökér.
Példa bináris keresőfákra
Nézzük a következő példát a bináris keresőfa fogalmainak bemutatására.
Itt minden csomópont követheti az adott diszciplínát. Van egy képlet a csomópontok maximális számához a bináris keresőfában. Ha megfigyeljük a fenti fát, láthatjuk, hogy minden csomópontnak két gyermeke van, kivéve az összes levélcsomópontot. Az adott bináris fa magassága(h) pedig 4. A képlet az 2h - 1. Tehát 15-öt ad.
A fenti kép nem egy teljes bináris fa vagy kiegyensúlyozott bináris fa, hanem teljes bináris fának vagy kiegyensúlyozott bináris fának nevezik. Van egy másik adatstruktúra, az AVL (egy másik típusú bináris fa), amely optimalizálja a bináris fa magasságát, és gyorsabban keresi a BST-t, mint a 3. ábrán.
Próbálja kiszámolni a fent megadott bináris fa sorrendben történő bejárását. Látni fogja, hogy nem csökkenő rendezett tömböt ad, és a bejárási algoritmusok megegyeznek a bináris fával.
A bináris fa típusai
Íme néhány fontos bináris fa típus:
- Teljes bináris fa: Ebben a bináris fában minden csomópontnak 0 vagy 2 gyermekcsomópontja lehet. Csak egy gyermek csomópont nem engedélyezett az ilyen típusú bináris fákban. Tehát a levél csomópont kivételével minden csomópontnak 2 gyermeke lesz.
- Teljes bináris fa: Minden csomópontnak lehet 0 vagy 2 csomópontja. Úgy tűnik, mint a teljes bináris fa, de az összes levélelem a bal oldali részfához hajlik, míg a teljes bináris fa csomópontja lehet a jobb vagy a bal részfában.
- Tökéletes bináris fa: Minden csomópontnak 0 vagy 2 csomóponttal kell rendelkeznie, és az összes levélcsomópontnak azonos szinten vagy magasságban kell lennie. A teljes bináris faszerkezet fenti példája nem egy tökéletes bináris fa, mivel a 6. és az 1,2,3, XNUMX, XNUMX csomópont nem azonos magasságban van. De a teljes bináris fa példája egy tökéletes bináris fa.
- Degenerált bináris fa: Minden csomópontnak csak egyetlen gyermeke lehet. Minden művelet, például a keresés, beszúrás és törlés O(N) időt vesz igénybe.
- Kiegyensúlyozott bináris fa: Itt ez a bináris fa, a bal és jobb részfa magasságkülönbsége legfeljebb 1. Tehát egy csomópont hozzáadása vagy törlése közben ismét ki kell egyensúlyoznunk a fa magasságát. Az önkiegyensúlyozott bináris fának ezt a típusát a AVL fa.
A BST-nek három alapvető művelete van. Ezeket az alábbiakban részletesen tárgyaljuk.
A bináris fa megvalósítása C-ben és C++
#include <iostream> #include <bits/stdc++.h> using namespace std; struct Node { int value; struct Node *left, *right; } struct Node *getEmptynode(int val) { struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node)); tempNode->value = val; tempNode->left = NULL; tempNode->right = NULL; return tempNode; } struct Node *successor(struct Node *node) { struct Node *present = node; // going to the left most node while (present != NULL && present->left != NULL) { present = present->left; } return present; } struct Node *insert(struct Node *node, int value) { if (node == NULL) { return getEmptynode(value); } if (value < node->value) { node->left = insert(node->left, value); } else { node->right = insert(node->right, value); } return node; } int searchInBST(struct Node *node, int value) { struct Node *current = node; while (current->value != value) { if (current->value > value) { current = current->left; } else { current = current->right; } if (current == NULL) { return 0; } } return 1; } void inorder(struct Node *root) { if (root != NULL) { inorder(root->left); cout << root->value << " "; inorder(root->right); } } struct Node *deleteNode(struct Node *node, int value) { if (node == NULL) { return node; } if (value < node->value) { node->left = deleteNode(node->left, value); } else if (value > node->value) { node->right = deleteNode(node->right, value); } else { if (node->left == NULL) { struct Node *temp = node->right; free(node); return temp; } else if (node->right == NULL) { struct Node *temp = node->left; free(node); return temp; } struct Node *temp = successor(node->right); node->value = temp->value; node->right = deleteNode(node->right, temp->value); } return node; } int main() { struct Node *root = NULL; root = insert(root, 8); root = insert(root, 4); root = insert(root, 12); root = insert(root, 2); root = insert(root, 6); root = insert(root, 10); root = insert(root, 14); root = insert(root, 1); root = insert(root, 3); root = insert(root, 5); root = insert(root, 7); root = insert(root, 9); root = insert(root, 11); root = insert(root, 13); root = insert(root, 15); cout << "InOrder Traversal after inserting all nodes: " << endl; inorder(root); root = insert(root, -10); cout << "\nInOrder Traversal after inserting -10 : " << endl; inorder(root); cout << "\nSearching -5 in the BST: " << searchInBST(root, -5) << endl; cout << "Searching -10 in the BST: " << searchInBST(root, -10) << endl; root = deleteNode(root,8); cout<<"After deleting node 8, inorder traversal: "<<endl; inorder(root); root = deleteNode(root,-10); cout<<"\nAfter deleting node -10, inorder traversal: "<<endl; inorder(root); }
output:
InOrder Traversal after inserting all nodes: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: 0 Searching -10 in the BST: 1 After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
A bináris fa implementációja Python
class Node: def __init__(self,value): self.left = None self.right = None self.value = value def insert(root,value): if root == None: return Node(value) if value< root.value: root.left = insert(root.left,value) else: root.right = insert(root.right,value) return root def searchInBST(root,value): current = root while current.value != value: if current.value > value: current = current.left else: current = current.right if current == None: return "Not found" return "Found" def inorder(root): if root != None: inorder(root.left) print(root.value,end=" ") inorder(root.right) def successor(root): present = root while present != None and present.left != None: present = present.left return present def deleteNode(root,value): if root == None: return root if value < root.value: root.left = deleteNode(root.left, value) elif value>root.value: root.right = deleteNode(root.right, value) else: if root.left == None: temp = root.right root = None return temp elif root.right == None: temp = root.left root = None return temp temp = successor(root.right) root.value = temp.value root.right = deleteNode(root.right, temp.value) return root root = Node(8) root = insert(root, 4) root = insert(root, 12) root = insert(root, 2) root = insert(root, 6) root = insert(root, 10) root = insert(root, 14) root = insert(root, 1) root = insert(root, 3) root = insert(root, 5) root = insert(root, 7) root = insert(root, 9) root = insert(root, 11) root = insert(root, 13) root = insert(root, 15) print("InOrder Traversal after inserting all nodes: ") inorder(root) root = insert(root, -10) print("\nInOrder Traversal after inserting -10 : ") inorder(root) print("\nSearching -5 in the BST: ",searchInBST(root, -5)) print("Searching -5 in the BST: ",searchInBST(root, -10)) root = deleteNode(root,8) print("After deleting node 8, inorder traversal:") inorder(root) root = deleteNode(root,-10) print("\nAfter deleting node -10, inorder traversal:") inorder(root)
output:
InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: Not found Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
A bináris fa alkalmazása
Íme a Binary Tree néhány gyakori alkalmazása:
- Csomóponti adatok rendezése rendezett sorrendben
- A programozási nyelvi könyvtárak leképezésében és beállítási csomóponti objektumaiban használatos.
- Elemek keresése az adatstruktúrákban
» Ismerje meg következő oktatóanyagunkat Kombinációs algoritmus
