Бінарне дерево в структурі даних (ПРИКЛАД)
Сара Чен
Що таке бінарне дерево?
Слово двійковий означає два. У структурі даних дерева «Двійкове дерево» означає дерево, де кожен вузол може мати максимум два дочірні вузли (лівий і правий вузли). Це просте бінарне дерево.
Однак є інше бінарне дерево, яке використовується найчастіше і має кілька варіантів використання. Це називається Двійкове дерево пошуку (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, XNUMX, XNUMX мають різну висоту. Але приклад повного бінарного дерева є ідеальним бінарним деревом.
- Вироджене бінарне дерево: Кожен вузол може мати лише одного дочірнього елемента. Усі операції, такі як пошук, вставка та видалення, займають 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
Застосування бінарного дерева
Ось кілька поширених застосувань бінарного дерева:
- Організація даних вузла в порядку сортування
- Використовується в об’єктах карт і набору вузлів у бібліотеках мови програмування.
- Пошук елементів у структурах даних
» Дізнайтеся про наступний підручник Алгоритм комбінування
