Binární strom v datové struktuře (PŘÍKLAD)
Sarah Chen
⚡ Chytré shrnutí
Binární strom v datové struktuře je hierarchická struktura, kde každý uzel má maximálně dva potomky, nazývané levý a pravý. Tento zdroj vysvětluje binární stromy, binární vyhledávací strom, jejich typy, aplikace a kompletní jazyk C. C++, a Python implementace.
Co je to binární strom?
Slovo binární znamená dva. Ve stromové datové struktuře „Binary Tree“ znamená strom, kde každý uzel může mít maximálně dva podřízené uzly (levý a pravý uzel). Je to jednoduchý binární strom.
Existuje však další binární strom, který se používá nejčastěji a má několik případů použití. Říká se tomu Binary Search Tree (BST). Tento strom může urychlit vyhledávací algoritmus, přesněji log(n) časovou složitost. V datové struktuře n znamená počet uzlů v binárním stromu.
Jaké jsou rozdíly mezi binárním stromem a binárním vyhledávacím stromem?
Rozdíl mezi BST a běžným binárním stromem je v tom, že levý uzel BST má menší hodnotu než kořenový uzel a pravý uzel má větší hodnotu než kořenový uzel. Takže levý podstrom bude vždy obsahovat menší hodnotu než kořen a pravý podstrom bude vždy obsahovat větší hodnotu než kořen.
Příklad binárních vyhledávacích stromů
Uveďme si následující příklad pro demonstraci konceptů binárního vyhledávacího stromu.
Zde můžete všechny uzly sledovat danou disciplínu. Existuje vzorec pro maximální počet uzlů ve stromu binárního vyhledávání. Pokud pozorujeme výše uvedený strom, můžeme vidět, že každý uzel má dva potomky kromě všech listových uzlů. A výška(h) daného binárního stromu je 4. Vzorec je 2h - 1. Takže dává 15.
Výše uvedený obrázek není úplný binární strom nebo vyvážený binární strom, nazývá se úplný binární strom nebo vyvážený binární strom. Existuje další datová struktura nazvaná AVL (jiný typ binárního stromu), která optimalizuje výšku binárního stromu a rychleji vyhledá BST jako na obr. 3.
Pokuste se spočítat průchod Binárního Stromu uvedený výše v pořadí. Zjistíte, že bude dávat neklesající tříděné pole a algoritmy Traversal budou stejné jako binární strom.
Typy binárních stromů
Zde jsou některé důležité typy binárních stromů:
- Úplný binární strom: Každý uzel může mít v tomto binárním stromu 0 nebo 2 podřízené uzly. V tomto typu binárního stromu není povolen pouze jeden podřízený uzel. Takže kromě listového uzlu budou mít všechny uzly 2 potomky.
- Kompletní binární strom: Každý uzel může mít 0 nebo 2 uzly. Vypadá to jako úplný binární strom, ale všechny prvky listu jsou nakloněny k levému podstromu, zatímco v úplném binárním stromě může být uzel v pravém nebo levém podstromu.
- Dokonalý binární strom: Všechny uzly musí mít 0 nebo 2 uzly a všechny listové uzly by měly být ve stejné úrovni nebo výšce. Výše uvedený příklad úplné binární stromové struktury není dokonalý binární strom, protože uzel 6 a uzel 1,2,3 nejsou ve stejné výšce. Ale příklad úplného binárního stromu je dokonalý binární strom.
- Degenerovaný binární strom: Každý uzel může mít pouze jedno dítě. Všechny operace jako vyhledávání, vkládání a mazání zaberou O(N) čas.
- Vyvážený binární strom: Zde je u tohoto binárního stromu výškový rozdíl levého a pravého podstromu maximálně 1. Takže při přidávání nebo odstraňování uzlu musíme výšku stromu znovu vyvážit. Tento typ samovyváženého binárního stromu se nazývá strom AVL.
Existují tři základní operace BST. Ty jsou podrobně popsány níže.
Implementace binárního stromu v C a 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); }
Výstup:
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
Implementace binárního stromu v 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)
Výstup:
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
Aplikace binárního stromu
Zde jsou některé běžné aplikace binárního stromu:
- Uspořádání dat uzlů v seřazeném pořadí
- Používá se v objektech uzlů mapy a množin v knihovnách programovacích jazyků.
- Vyhledávání prvků v datových strukturách
» Přečtěte si náš další tutoriál o Kombinační algoritmus
