Binääripuu tietorakenteessa (ESIMERKKI)
Sarah Chen
Mikä on binääripuu?
Sana binääri tarkoittaa kahta. Puutietorakenteessa "Binary Tree" tarkoittaa puuta, jossa jokaisessa solmussa voi olla enintään kaksi lapsisolmua (vasen ja oikea solmu). Se on yksinkertainen binääripuu.
On kuitenkin toinen binääripuu, jota käytetään useimmin ja jolla on useita käyttötapauksia. Sitä kutsutaan binäärihakupuuksi (BST). Tämä puu voi tehdä hakualgoritmista paljon nopeammaksi, tarkalleen log(n)-ajan monimutkaisuuden. Tietorakenteessa n tarkoittaa binääripuun solmujen määrää.
Mitä eroa on binääripuun ja binaarihakupuun välillä?
Ero BST:n ja tavallisen binaaripuun välillä on siinä, että BST:n vasemmalla solmulla on pienempi arvo kuin juurisolmulla ja oikealla solmulla on suurempi arvo kuin juurisolmulla. Vasen alipuu sisältää siis aina pienemmän arvon kuin juuri ja oikea alipuu aina suuremman arvon kuin juuri.
Esimerkki binaarisista hakupuista
Otetaan seuraava esimerkki binaarihakupuun käsitteiden havainnollistamiseksi.
Täällä voit kaikki solmut noudattaa annettua kurinalaisuutta. Binäärihakupuussa on kaava solmujen enimmäismäärälle. Jos tarkkailemme yllä olevaa puuta, voimme nähdä, että jokaisella solmulla on kaksi lasta paitsi kaikkia lehtien solmuja. Ja annetun binääripuun korkeus(h) on 4. Kaava on 2h - 1. Joten se antaa 15.
Yllä oleva kuva ei ole täydellinen binaaripuu tai tasapainotettu binaaripuu, sitä kutsutaan täydelliseksi binaaripuuksi tai tasapainotetuksi binaaripuuksi. On olemassa toinen tietorakenne nimeltä AVL (toinen binaaripuu), joka optimoi binääripuun korkeuden ja suorittaa BST-haun nopeammin, kuten kuvassa 3.
Yritä laskea edellä esitetyn binääripuun järjestyksessä kulkeminen. Tulet huomaamaan, että se antaa ei-vähenevän lajitellun taulukon, ja Traversal-algoritmit ovat samat kuin binääripuu.
Binaaripuun tyypit
Tässä on joitain tärkeitä binääripuutyyppejä:
- Täysi binääripuu: Jokaisella solmulla voi olla 0 tai 2 lapsisolmua tässä binääripuussa. Vain yksi lapsisolmu ei ole sallittu tämän tyyppisessä binääripuussa. Joten lehtisolmua lukuun ottamatta kaikilla solmuilla on 2 lasta.
- Täysi binääripuu: Jokaisessa solmussa voi olla 0 tai 2 solmua. Näyttää siltä, että koko binääripuu, mutta kaikki lehtielementit ovat kallistuneet vasempaan alipuuhun, kun taas täydessä binääripuussa solmu voi olla oikeassa tai vasemmassa alipuussa.
- Täydellinen binääripuu: Kaikissa solmuissa on oltava 0 tai 2 solmua, ja kaikkien lehtien solmujen tulee olla samalla tasolla tai korkeudella. Yllä oleva esimerkki täydellisestä binääripuurakenteesta ei ole täydellinen binaaripuu, koska solmu 6 ja solmu 1,2,3 eivät ole samalla korkeudella. Mutta esimerkki täydellisestä binääripuusta on täydellinen binääripuu.
- Degeneroitunut binääripuu: Jokaisella solmulla voi olla vain yksi lapsi. Kaikki toiminnot, kuten etsiminen, lisääminen ja poistaminen, vievät O(N) aikaa.
- Tasapainotettu binääripuu: Tässä binääripuussa vasemman ja oikean alipuun korkeusero on korkeintaan 1. Joten lisättäessä tai poistaessamme solmua meidän on tasapainotettava puun korkeus uudelleen. Tämän tyyppistä itsetasapainoista binaaripuuta kutsutaan nimellä AVL-puu.
BST:ssä on kolme perustoimintoa. Niitä käsitellään yksityiskohtaisesti alla.
Binaaripuun toteutus C:ssä ja 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);
}
lähtö:
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
Binaaripuun käyttöönotto 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)
lähtö:
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
Binaaripuun sovellus
Tässä on joitain Binary Treen yleisiä sovelluksia:
- Solmutietojen järjestäminen lajiteltuun järjestykseen
- Käytetään ohjelmointikielikirjastojen kartassa ja solmuobjekteissa.
- Elementtien etsiminen tietorakenteista
» Opi seuraavasta opetusohjelmastamme Yhdistelmäalgoritmi
