Binärt träd i datastruktur (EXEMPEL)
Sarah Chen
Vad är ett binärt träd?
Ordet binär betyder två. I träddatastrukturen betyder "Binary Tree" ett träd där varje nod kan ha maximalt två underordnade noder (vänster och höger noder). Det är ett enkelt binärt träd.
Det finns dock ett annat binärt träd som används oftast och som har flera användningsfall. Det kallas det binära sökträdet (BST). Detta träd kan göra sökalgoritmen mycket snabbare, exakt logga (n) tidskomplexitet. I datastrukturen betyder n antalet noder i det binära trädet.
Vad är skillnaderna mellan binärt träd och binärt sökträd?
Skillnaden mellan BST och det vanliga binära trädet är att BST:s vänstra nod har ett mindre värde än rotnoden, och den högra noden har ett större värde än rotnoden. Så det vänstra underträdet kommer alltid att innehålla ett mindre värde än roten, och det högra underträdet kommer alltid att innehålla ett större värde än roten.
Exempel på binära sökträd
Låt oss ta följande exempel för att demonstrera begreppen i det binära sökträdet.
Här kan du alla noder följa den givna disciplinen. Det finns en formel för det maximala antalet noder i det binära sökträdet. Om vi observerar ovanstående träd kan vi se att varje nod har två barn utom alla bladnoder. Och höjden(h) för det givna binära trädet är 4. Formeln är 2h - 1. Så det ger 15.
Ovanstående givna bild är inte ett komplett binärt träd eller balanserat binärt träd, utan kallas för det kompletta binära trädet eller det balanserade binära trädet. Det finns en annan datastruktur som heter AVL (en annan typ av binärt träd) som optimerar höjden på binärt träd och utför sökningar snabbare efter BST som i fig 3.
Försök att beräkna genomgången av det binära trädet i ordning ovan. Du kommer att upptäcka att det kommer att ge en icke-minskande sorterad array, och Traversal-algoritmer kommer att vara desamma som det binära trädet.
Typer av binärt träd
Här är några viktiga typer av binära träd:
- Fullständigt binärt träd: Varje nod kan ha 0 eller 2 underordnade noder i detta binära träd. Endast en underordnad nod är inte tillåten i den här typen av binärt träd. Så, förutom lövnoden, kommer alla noder att ha 2 barn.
- Fullständigt binärt träd: Varje nod kan ha 0 eller 2 noder. Det verkar som det fullständiga binära trädet, men alla bladelement lutar åt det vänstra underträdet, medan noden i det fullständiga binära trädet kan vara i det högra eller vänstra underträdet.
- Perfekt binärt träd: Alla noder måste ha 0 eller 2 noder, och alla bladnoder ska vara på samma nivå eller höjd. Ovanstående exempel på en fullständig binär trädstruktur är inte ett perfekt binärt träd eftersom nod 6 och nod 1,2,3 inte är i samma höjd. Men exemplet med det kompletta binära trädet är ett perfekt binärt träd.
- Degenererat binärt träd: Varje nod kan bara ha ett enda barn. Alla operationer som att söka, infoga och radera tar O(N) tid.
- Balanserat binärt träd: Här är detta binära träd, höjdskillnaden mellan vänster och höger underträd är högst 1. Så när vi lägger till eller tar bort en nod måste vi balansera trädets höjd igen. Denna typ av självbalanserade binära träd kallas AVL-träd.
Det finns tre grundläggande funktioner för BST. Dessa diskuteras i detalj nedan.
Implementering av Binary Tree i C och 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);
}
Produktion:
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)
Produktion:
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
Tillämpning av binärt träd
Här är några vanliga tillämpningar av Binary Tree:
- Organisera noddata i sorterad ordning
- Används i kartan och nodobjekt i programmeringsspråksbibliotek.
- Söka efter element i datastrukturerna
» Lär dig vår nästa handledning om Kombinationsalgoritm
