Binaarne puu andmestruktuuris (EXAMPLE)
Sarah Chen
Mis on binaarne puu?
Sõna binaarne tähendab kahte. Puu andmestruktuuris tähendab “Binary Tree” puud, kus igal sõlmel võib olla maksimaalselt kaks alamsõlme (vasak ja parem sõlm). See on lihtne kahendpuu.
Siiski on veel üks kahendpuu, mida kasutatakse kõige sagedamini ja millel on mitu kasutusjuhtu. Seda nimetatakse binaarseks otsingupuuks (BST). See puu võib muuta otsingualgoritmi palju kiiremaks, täpselt logi(n) aja keerukusega. Andmestruktuuris tähendab n kahendpuu sõlmede arvu.
Mis vahe on binaarsel puul ja binaarsel otsingupuul?
BST ja tavalise binaarpuu erinevus seisneb selles, et BST vasakpoolsel sõlmel on väiksem väärtus kui juursõlmel ja parempoolsel sõlmel on suurem väärtus kui juursõlmel. Seega sisaldab vasakpoolne alampuu alati väiksemat väärtust kui juur ja parempoolne alampuu alati suuremat väärtust kui juur.
Näide binaarsetest otsingupuudest
Toome järgmise näite binaarse otsingupuu mõistete demonstreerimiseks.
Siin saate kõik sõlmed järgida antud distsipliini. Binaarse otsingupuu sõlmede maksimaalse arvu jaoks on valem. Kui vaatleme ülaltoodud puud, näeme, et igal sõlmel on kaks last, välja arvatud kõik lehesõlmed. Ja antud kahendpuu kõrgus(h) on 4. Valem on 2h - 1. Nii et see annab 15.
Ülaltoodud pilt ei ole täielik kahendpuu või tasakaalustatud kahendpuu, seda nimetatakse täielikuks kahendpuuks või tasakaalustatud kahendpuuks. On veel üks andmestruktuur nimega AVL (teine binaarpuu tüüp), mis optimeerib binaarpuu kõrgust ja otsib BST-d kiiremini, nagu on näidatud joonisel 3.
Proovige arvutada ülaltoodud binaarpuu läbimine järjekorras. Leiate, et see annab mitte-kahaneva sorteeritud massiivi ja läbimise algoritmid on samad, mis binaarpuul.
Binaarse puu tüübid
Siin on mõned olulised binaarpuu tüübid:
- Täielik kahendpuu: Igal sõlmel võib selles kahendpuus olla 0 või 2 alamsõlme. Seda tüüpi kahendpuus pole lubatud ainult üks alamsõlm. Seega, välja arvatud lehesõlme, on kõigil sõlmedel 2 last.
- Täielik kahendpuu: Igal sõlmel võib olla 0 või 2 sõlme. Tundub, et see on täielik kahendpuu, kuid kõik leheelemendid on kaldu vasakpoolsele alampuule, samas kui täisbinaarpuu sõlm võib olla paremas või vasakpoolses alampuus.
- Täiuslik kahendpuu: Kõikidel sõlmedel peab olema 0 või 2 sõlme ja kõik lehtede sõlmed peavad olema samal tasemel või kõrgusel. Ülaltoodud näide täielikust kahendpuustruktuurist ei ole täiuslik kahendpuu, kuna sõlm 6 ja sõlm 1,2,3 ei ole samal kõrgusel. Kuid täieliku kahendpuu näide on täiuslik kahendpuu.
- Degenereerunud kahendpuu: Igal sõlmel võib olla ainult üks laps. Kõik toimingud, nagu otsimine, sisestamine ja kustutamine, võtavad O(N) aega.
- Tasakaalustatud kahendpuu: Siin on see kahendpuu, vasaku ja parema alampuu kõrguste erinevus maksimaalselt 1. Seega peame sõlme lisamisel või kustutamisel taas puu kõrguse tasakaalustama. Seda tüüpi isetasakaalustatud binaarset puud nimetatakse AVL puu.
BST-l on kolm põhitoimingut. Neid arutatakse üksikasjalikult allpool.
Binary Tree rakendamine C 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);
}
Väljund:
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
Binaarse puu juurutamine 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äljund:
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
Binaarse puu rakendamine
Siin on mõned Binary Tree levinumad rakendused:
- Sõlmeandmete korraldamine sorteeritud järjekorras
- Kasutatakse programmeerimiskeele teekide kaardi- ja seadistussõlmeobjektides.
- Elementide otsimine andmestruktuuridest
» Tutvuge meie järgmise õpetusega Kombinatsiooni algoritm
