Binaire boom in gegevensstructuur (VOORBEELD)
Sara Chen
Wat is een binaire boom?
Het woord binair betekent twee. In de boomdatastructuur betekent “Binaire Boom” een boom waarin elk knooppunt maximaal twee onderliggende knooppunten kan hebben (linker- en rechterknooppunten). Het is een eenvoudige binaire boom.
Er is echter nog een binaire boom die het meest wordt gebruikt en verschillende use cases heeft. Deze heet de Binary Search Tree (BST). Deze boom kan het zoekalgoritme veel sneller maken, precies log(n) tijdcomplexiteit. In de datastructuur betekent n het aantal knooppunten in de binaire boom.
Wat zijn de verschillen tussen binaire boom en binaire zoekboom?
Het verschil tussen de BST en de reguliere binaire boom is dat het linkerknooppunt van de BST een kleinere waarde heeft dan het hoofdknooppunt, en dat het rechterknooppunt een grotere waarde heeft dan het hoofdknooppunt. De linker subboom zal dus altijd een kleinere waarde bevatten dan de wortel, en de rechter subboom zal altijd een grotere waarde bevatten dan de wortel.
Voorbeeld van binaire zoekbomen
Het volgende voorbeeld illustreert de concepten van de binaire zoekboom.
Hier kun je alle knooppunten de gegeven discipline volgen. Er is een formule voor het maximale aantal knooppunten in de binaire zoekboom. Als we de bovenstaande boom bekijken, kunnen we zien dat elk knooppunt twee kinderen heeft, behalve alle bladknooppunten. En de hoogte(h) van de gegeven binaire boom is 4. De formule is 2h - 1. Het levert dus 15 op.
De hierboven gegeven afbeelding is geen volledige binaire boom of gebalanceerde binaire boom, maar wordt de complete binaire boom of gebalanceerde binaire boom genoemd. Er is een andere gegevensstructuur genaamd AVL (een ander type binaire boom) die de hoogte van de binaire boom optimaliseert en sneller naar de BST zoekt, zoals in figuur 3.
Probeer de in-order traversal van de Binary Tree hierboven te berekenen. U zult zien dat het een niet-afnemende gesorteerde array oplevert, en Traversal-algoritmen zullen hetzelfde zijn als de Binary Tree.
Soorten binaire boom
Hier zijn enkele belangrijke typen binaire bomen:
- Volledige binaire boom: Elk knooppunt kan 0 of 2 onderliggende knooppunten in deze binaire boom hebben. Slechts één onderliggend knooppunt is niet toegestaan in dit type binaire boom. Dus, behalve het bladknooppunt, zullen alle knooppunten 2 kinderen hebben.
- Volledige binaire boom: Elk knooppunt kan 0 of 2 knooppunten hebben. Het lijkt op de volledige binaire boom, maar alle bladelementen bevinden zich in de linker subboom, terwijl in de volledige binaire boom het knooppunt zich in de rechter of linker subboom kan bevinden.
- Perfecte binaire boom: Alle knooppunten moeten 0 of 2 knooppunten hebben en alle bladknooppunten moeten zich op hetzelfde niveau of dezelfde hoogte bevinden. Het bovenstaande voorbeeld van een volledige binaire boomstructuur is geen perfecte binaire boom omdat knooppunt 6 en knooppunt 1,2,3 zich niet op dezelfde hoogte bevinden. Maar het voorbeeld van de complete binaire boom is een perfecte binaire boom.
- Gedegenereerde binaire boom: Elke node kan slechts één kind hebben. Alle bewerkingen zoals zoeken, invoegen en verwijderen nemen O(N) tijd in beslag.
- Evenwichtige binaire boom: Hier in deze binaire boom is het hoogteverschil tussen de linker en rechter deelboom maximaal 1. Dus tijdens het toevoegen of verwijderen van een knooppunt moeten we de hoogte van de boom opnieuw in evenwicht brengen. Dit type zelfgebalanceerde binaire boom wordt de AVL-boom.
Er zijn drie basisbewerkingen van BST. Deze worden hieronder in detail besproken.
Implementatie van binaire boom in C en 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
Implementatie van binaire boom in 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
Toepassing van binaire boom
Hier zijn enkele veelvoorkomende toepassingen van Binary Tree:
- Knooppuntgegevens in gesorteerde volgorde ordenen
- Wordt gebruikt in de kaart- en set-node-objecten in programmeertaalbibliotheken.
- Zoeken naar elementen in de datastructuren
» Lees onze volgende tutorial over Combinatie-algoritme
