Binært træ i datastruktur (EKSEMPEL)
Sarah Chen
Hvad er et binært træ?
Ordet binær betyder to. I trædatastrukturen betyder "Binært træ" et træ, hvor hver node maksimalt kan have to underordnede noder (venstre og højre noder). Det er et simpelt binært træ.
Der er dog et andet binært træ, der bruges oftest og har flere use cases. Det kaldes det binære søgetræ (BST). Dette træ kan gøre søgealgoritmen meget hurtigere, præcis log(n) tidskompleksitet. I datastrukturen betyder n antallet af noder i det binære træ.
Hvad er forskellene mellem binært træ og binært søgetræ?
Forskellen mellem BST og det almindelige binære træ er, at BST venstre knude har en mindre værdi end rodnoden, og den højre knude har en større værdi end rodknuden. Så det venstre undertræ vil altid indeholde en mindre værdi end roden, og det højre undertræ vil altid indeholde en større værdi end roden.
Eksempel på binære søgetræer
Lad os få følgende eksempel til at demonstrere koncepterne for det binære søgetræ.
Her kan du alle noderne følge den givne disciplin. Der er en formel for det maksimale antal noder i det binære søgetræ. Hvis vi observerer ovenstående træ, kan vi se, at hver node har to børn undtagen alle bladknuderne. Og højden(h) af det givne binære træ er 4. Formlen er 2h - 1. Så det giver 15.
Ovenstående givne billede er ikke et komplet binært træ eller et balanceret binært træ, kaldes det komplette binære træ eller det balancerede binære træ. Der er en anden datastruktur kaldet AVL (en anden type binært træ), der optimerer højden af binært træ og udfører søgning hurtigere efter BST som i fig.
Prøv at beregne gennemløbet af det binære træ i rækkefølge ovenfor. Du vil opdage, at det vil give et ikke-faldende sorteret array, og Traversal-algoritmer vil være de samme som det binære træ.
Typer af binært træ
Her er nogle vigtige typer af binært træ:
- Fuldt binært træ: Hver node kan have 0 eller 2 underordnede noder i dette binære træ. Kun én underordnet node er ikke tilladt i denne type binært træ. Så bortset fra bladknuden vil alle noder have 2 børn.
- Fuldt binært træ: Hver node kan have 0 eller 2 noder. Det ligner det fulde binære træ, men alle bladelementerne er lænet til venstre undertræ, hvorimod knudepunktet i det fulde binære træ kan være i højre eller venstre undertræ.
- Perfekt binært træ: Alle noder skal have 0 eller 2 noder, og alle bladknuder skal være på samme niveau eller højde. Ovenstående eksempel på en fuld binær træstruktur er ikke et perfekt binært træ, fordi node 6 og node 1,2,3 ikke er i samme højde. Men eksemplet med det komplette binære træ er et perfekt binært træ.
- Degenereret binært træ: Hver node kan kun have et enkelt barn. Alle handlinger som søgning, indsættelse og sletning tager O(N) tid.
- Balanceret binært træ: Her i dette binære træ er højdeforskellen mellem venstre og højre undertræ højst 1. Så mens vi tilføjer eller sletter en node, skal vi balancere træets højde igen. Denne type af selvbalanceret binært træ kaldes AVL-træ.
Der er tre grundlæggende funktioner i BST. Disse diskuteres i detaljer nedenfor.
Implementering af binært træ 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);
}
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
Implementering af 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)
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
Anvendelse af binært træ
Her er nogle almindelige anvendelser af Binary Tree:
- Organisering af nodedata i sorteret rækkefølge
- Bruges i kortet og sæt nodeobjekter i programmeringssprogsbiblioteker.
- Søgning efter elementer i datastrukturerne
» Lær vores næste selvstudie om Kombinationsalgoritme
