Binární strom v datové struktuře (PŘÍKLAD)
Sarah Chen
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.
- Úplný 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
