Двоично дърво в структурата на данните (ПРИМЕР)
Сара Чен
Какво е бинарно дърво?
Думата двоичен означава две. В дървовидната структура на данните „Двоично дърво“ означава дърво, където всеки възел може да има максимум два дъщерни възела (ляв и десен възел). Това е просто двоично дърво.
Има обаче друго двоично дърво, което се използва най-често и има няколко случая на употреба. Нарича се Двоично дърво за търсене (BST). Това дърво може да направи алгоритъма за търсене много по-бърз, точно log(n) времева сложност. В структурата на данните n означава броя на възлите в двоичното дърво.
Какви са разликите между двоично дърво и двоично дърво за търсене?
Разликата между BST и обикновеното двоично дърво е в това, че BST левият възел има по-малка стойност от основния възел, а десният възел има по-голяма стойност от основния възел. Така че лявото поддърво винаги ще съдържа по-малка стойност от корена, а дясното поддърво винаги ще съдържа по-голяма стойност от корена.
Пример за двоични дървета за търсене
Нека имаме следния пример за демонстриране на концепциите на двоичното дърво за търсене.
Тук можете всички възли да следват дадената дисциплина. Има формула за максималния брой възли в двоичното дърво за търсене. Ако наблюдаваме горното дърво, можем да видим, че всеки възел има две деца, с изключение на всички листови възли. И височината (h) на даденото двоично дърво е 4. Формулата е 2h - 1. И така, дава 15.
Даденото по-горе изображение не е пълно двоично дърво или балансирано двоично дърво, нарича се пълно двоично дърво или балансирано двоично дърво. Има друга структура от данни, наречена AVL (друг тип двоично дърво), която оптимизира височината на двоичното дърво и извършва търсене по-бързо за BST, както е показано на фиг. 3.
Опитайте се да изчислите обхождането по ред на двоичното дърво, дадено по-горе. Ще откриете, че ще даде ненамаляващ сортиран масив, а алгоритмите за обхождане ще бъдат същите като при двоичното дърво.
Видове двоично дърво
Ето някои важни типове двоично дърво:
- Пълно двоично дърво: Всеки възел може да има 0 или 2 дъщерни възела в това двоично дърво. Само един дъщерен възел не е разрешен в този тип двоично дърво. Така че, с изключение на листовия възел, всички възли ще имат 2 деца.
- Пълно двоично дърво: Всеки възел може да има 0 или 2 възела. Изглежда като пълното двоично дърво, но всички листни елементи са наклонени към лявото поддърво, докато в пълното двоично дърво възелът може да бъде в дясното или лявото поддърво.
- Перфектно двоично дърво: Всички възли трябва да имат 0 или 2 възли и всички листови възли трябва да са на едно и също ниво или височина. Горният пример за пълна двоична дървовидна структура не е перфектно двоично дърво, тъй като възел 6 и възел 1,2,3 не са на една и съща височина. Но примерът на пълното двоично дърво е перфектно двоично дърво.
- Изродено двоично дърво: Всеки възел може да има само едно дете. Всички операции като търсене, вмъкване и изтриване отнемат O(N) време.
- Балансирано двоично дърво: Ето това двоично дърво, разликата във височината на лявото и дясното поддърво е най-много 1. Така че, докато добавяме или изтриваме възел, трябва отново да балансираме височината на дървото. Този тип самобалансирано двоично дърво се нарича AVL дърво.
Има три основни операции на BST. Те са обсъдени подробно по-долу.
Внедряване на двоично дърво в C и 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);
}
Изход:
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
Внедряване на двоично дърво в 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)
Изход:
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
Приложение на двоично дърво
Ето някои често срещани приложения на Binary Tree:
- Организиране на данни за възли в сортиран ред
- Използва се в обекти на карта и набор от възли в библиотеки на езици за програмиране.
- Търсене на елементи в структурите от данни
» Научете следващия ни урок за Алгоритъм за комбиниране
