Binært tre i datastruktur (EKSEMPEL)
Sarah Chen
Hva er et binært tre?
Ordet binær betyr to. I tredatastrukturen betyr "Binært tre" et tre der hver node kan ha maksimalt to underordnede noder (venstre og høyre noder). Det er et enkelt binært tre.
Imidlertid er det et annet binært tre som brukes oftest og har flere brukstilfeller. Det kalles Binary Search Tree (BST). Dette treet kan gjøre søkealgoritmen mye raskere, nøyaktig logg(n) tidskompleksitet. I datastrukturen betyr n antall noder i det binære treet.
Hva er forskjellene mellom binært tre og binært søketre?
Forskjellen mellom BST og det vanlige binære treet er at BST venstre node har en mindre verdi enn rotnoden, og den høyre noden har en større verdi enn rotnoden. Så det venstre undertreet vil alltid inneholde en mindre verdi enn roten, og det høyre undertreet vil alltid inneholde en større verdi enn roten.
Eksempel på binære søketrær
La oss ha følgende eksempel for å demonstrere konseptene til det binære søketreet.
Her kan du alle nodene følge den gitte disiplinen. Det er en formel for maksimalt antall noder i det binære søketreet. Hvis vi observerer treet ovenfor, kan vi se at hver node har to barn bortsett fra alle bladnodene. Og høyden(h) til det gitte binære treet er 4. Formelen er 2h - 1. Så det gir 15.
Bildet ovenfor er ikke et komplett binært tre eller balansert binært tre, kalles det komplette binære treet eller balansert binært tre. Det er en annen datastruktur kalt AVL (en annen type binært tre) som optimerer høyden på binært tre og utfører søk raskere etter BST som i fig 3.
Prøv å beregne gjennomgangen i rekkefølge av det binære treet gitt ovenfor. Du vil finne at det vil gi en ikke-minskende sortert matrise, og gjennomgangsalgoritmer vil være de samme som det binære treet.
Typer av binært tre
Her er noen viktige typer binære tre:
- Fullt binært tre: Hver node kan ha 0 eller 2 underordnede noder i dette binære treet. Bare én underordnet node er ikke tillatt i denne typen binærtre. Så, bortsett fra bladnoden, vil alle noder ha 2 barn.
- Fullt binært tre: Hver node kan ha 0 eller 2 noder. Det virker som det fullstendige binære treet, men alle bladelementene lener seg til venstre undertre, mens noden i det fullstendige binære treet kan være i høyre eller venstre undertre.
- Perfekt binært tre: Alle nodene må ha 0 eller 2 noder, og alle bladnodene skal være på samme nivå eller høyde. Eksemplet ovenfor på en full binær trestruktur er ikke et perfekt binært tre fordi node 6 og node 1,2,3 ikke er i samme høyde. Men eksemplet med det komplette binære treet er et perfekt binært tre.
- Degenerert binært tre: Hver node kan bare ha ett enkelt barn. Alle operasjoner som å søke, sette inn og slette tar O(N) tid.
- Balansert binært tre: Her i dette binære treet, er høydeforskjellen til venstre og høyre undertre maksimalt 1. Så mens vi legger til eller sletter en node, må vi balansere treets høyde igjen. Denne typen selvbalansert binært tre kalles AVL-treet.
Det er tre grunnleggende operasjoner for BST. Disse diskuteres i detalj nedenfor.
Implementering av Binary Tree i C og 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);
}
Utgang:
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
Implementering av Binary Tree i 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)
Utgang:
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
Bruk av binært tre
Her er noen vanlige bruksområder for Binary Tree:
- Organisere nodedata i sortert rekkefølge
- Brukes i kartet og sette nodeobjekter i programmeringsspråkbiblioteker.
- Søke etter elementer i datastrukturene
» Lær vår neste veiledning om Kombinasjonsalgoritme
