Binarno stablo u strukturi podataka (PRIMJER)
Sarah Chen
Što je binarno stablo?
Riječ binarno znači dvoje. U strukturi podataka stabla "Binarno stablo" znači stablo u kojem svaki čvor može imati najviše dva podređena čvora (lijevi i desni čvor). To je jednostavno binarno stablo.
Međutim, postoji još jedno binarno stablo koje se najčešće koristi i ima nekoliko slučajeva upotrebe. Zove se binarno stablo pretraživanja (BST). Ovo stablo može učiniti algoritam pretraživanja puno bržim, točno log(n) vremensku složenost. U strukturi podataka n označava broj čvorova u binarnom stablu.
Koje su razlike između binarnog stabla i binarnog stabla pretraživanja?
Razlika između BST i običnog binarnog stabla je u tome što BST lijevi čvor ima manju vrijednost od korijenskog čvora, a desni čvor ima veću vrijednost od korijenskog čvora. Dakle, lijevo podstablo će uvijek sadržavati manju vrijednost od korijena, a desno podstablo će uvijek sadržavati veću vrijednost od korijena.
Primjer stabala binarnog pretraživanja
Uzmimo sljedeći primjer za demonstraciju koncepata stabla binarnog pretraživanja.
Ovdje možete svi čvorovi slijediti zadanu disciplinu. Postoji formula za najveći broj čvorova u stablu binarnog pretraživanja. Ako promatramo gornje stablo, možemo vidjeti da svaki čvor ima dva djeteta osim svih lisnih čvorova. A visina(h) zadanog binarnog stabla je 4. Formula je 2h - 1. Dakle, daje 15.
Gornja slika nije potpuno binarno stablo ili uravnoteženo binarno stablo, zove se potpuno binarno stablo ili uravnoteženo binarno stablo. Postoji još jedna struktura podataka koja se zove AVL (još jedna vrsta binarnog stabla) koja optimizira visinu binarnog stabla i brže izvodi pretragu za BST kao na slici 3.
Pokušajte izračunati obilazak gore navedenog binarnog stabla po redu. Vidjet ćete da će dati sortirano polje koje se ne smanjuje, a algoritmi obilaska bit će isti kao i binarno stablo.
Vrste binarnog stabla
Evo nekoliko važnih vrsta binarnog stabla:
- Potpuno binarno stablo: Svaki čvor može imati 0 ili 2 podređena čvora u ovom binarnom stablu. Samo jedan podređeni čvor nije dopušten u ovoj vrsti binarnog stabla. Dakle, osim čvora lista, svi čvorovi će imati 2 djece.
- Potpuno binarno stablo: Svaki čvor može imati 0 ili 2 čvora. Čini se kao potpuno binarno stablo, ali svi elementi listova naslonjeni su na lijevo podstablo, dok u punom binarnom stablu čvor može biti u desnom ili lijevom podstablu.
- Savršeno binarno stablo: Svi čvorovi moraju imati 0 ili 2 čvora, a svi čvorovi listova trebaju biti na istoj razini ili visini. Gornji primjer pune strukture binarnog stabla nije savršeno binarno stablo jer čvor 6 i čvor 1,2,3 nisu na istoj visini. Ali primjer potpunog binarnog stabla je savršeno binarno stablo.
- Degenerirano binarno stablo: Svaki čvor može imati samo jedno dijete. Sve operacije poput pretraživanja, umetanja i brisanja oduzimaju O(N) vremena.
- Uravnoteženo binarno stablo: Ovdje u ovom binarnom stablu razlika u visini lijevog i desnog podstabla je najviše 1. Dakle, dok dodajemo ili brišemo čvor, trebamo ponovno uravnotežiti visinu stabla. Ova vrsta samouravnoteženog binarnog stabla naziva se AVL stablo.
Tri su osnovne operacije BST-a. O njima se detaljno govori u nastavku.
Implementacija binarnog stabla u C i 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);
}
Izlaz:
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
Implementacija binarnog stabla u 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)
Izlaz:
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
Primjena binarnog stabla
Evo nekih uobičajenih primjena binarnog stabla:
- Organiziranje podataka o čvorovima poredanim redoslijedom
- Koristi se u objektima mapiranja i postavljanja čvorova u bibliotekama programskih jezika.
- Traženje elemenata u strukturama podataka
» Saznajte o našem sljedećem vodiču Algoritam kombinacije
