Drzewo binarne w strukturze danych (PRZYKŁAD)
Sara Chen
Co to jest drzewo binarne?
Słowo binarny oznacza dwa. W drzewiastej strukturze danych „Drzewo Binarne” oznacza drzewo, w którym każdy węzeł może mieć maksymalnie dwa węzły potomne (węzeł lewy i prawy). Jest to proste drzewo binarne.
Istnieje jednak inne drzewo binarne, które jest najczęściej używane i ma kilka przypadków użycia. Nazywa się Binary Search Tree (BST). Drzewo to może znacznie przyspieszyć algorytm wyszukiwania, dokładnie log(n) złożoności czasowej. W strukturze danych n oznacza liczbę węzłów w drzewie binarnym.
Jakie są różnice między drzewem binarnym a drzewem wyszukiwania binarnego?
Różnica między BST a zwykłym drzewem binarnym polega na tym, że lewy węzeł BST ma mniejszą wartość niż węzeł główny, a prawy węzeł ma większą wartość niż węzeł główny. Zatem lewe poddrzewo będzie zawsze zawierać mniejszą wartość niż korzeń, a prawe poddrzewo zawsze będzie zawierać większą wartość niż korzeń.
Przykład drzew wyszukiwania binarnego
Aby zobrazować koncepcję drzewa poszukiwań binarnych, przyjrzyjmy się następującemu przykładowi.
Tutaj możesz wszystkie węzły podążać za daną dyscypliną. Istnieje wzór na maksymalną liczbę węzłów w drzewie wyszukiwania binarnego. Jeśli przyjrzymy się powyższemu drzewu, zobaczymy, że każdy węzeł ma dwoje dzieci, z wyjątkiem wszystkich węzłów liści. Wysokość (h) danego drzewa binarnego wynosi 4. Wzór jest następujący 2h - 1. Daje więc 15.
Powyższy obraz nie jest kompletnym drzewem binarnym ani zrównoważonym drzewem binarnym, nazywany jest kompletnym drzewem binarnym lub zrównoważonym drzewem binarnym. Istnieje inna struktura danych zwana AVL (inny typ drzewa binarnego), która optymalizuje wysokość drzewa binarnego i zapewnia szybsze wyszukiwanie BST, jak na rys. 3.
Spróbuj obliczyć przechodzenie w kolejności drzewa binarnego podanego powyżej. Odkryjesz, że da ono niemalejącą posortowaną tablicę, a algorytmy przechodzenia będą takie same jak w drzewie binarnym.
Rodzaje drzew binarnych
Oto kilka ważnych typów drzew binarnych:
- Pełne drzewo binarne: Każdy węzeł może mieć 0 lub 2 węzły podrzędne w tym drzewie binarnym. W drzewie binarnym tego typu nie jest dozwolony tylko jeden węzeł podrzędny. Tak więc, z wyjątkiem węzła liścia, wszystkie węzły będą miały 2 dzieci.
- Pełne drzewo binarne: Każdy węzeł może mieć 0 lub 2 węzły. Wygląda jak pełne drzewo binarne, ale wszystkie elementy liścia pochylają się do lewego poddrzewa, podczas gdy w pełnym drzewie binarnym węzeł może znajdować się w prawym lub lewym poddrzewie.
- Idealne drzewo binarne: Wszystkie węzły muszą mieć 0 lub 2 węzły, a wszystkie węzły liściowe powinny znajdować się na tym samym poziomie lub wysokości. Powyższy przykład pełnej struktury drzewa binarnego nie jest idealnym drzewem binarnym, ponieważ węzeł 6 i węzeł 1,2,3 nie mają tej samej wysokości. Ale przykładem kompletnego drzewa binarnego jest doskonałe drzewo binarne.
- Zdegenerowane drzewo binarne: Każdy węzeł może mieć tylko jedno dziecko. Wszystkie operacje, takie jak wyszukiwanie, wstawianie i usuwanie, zajmują O(N) czasu.
- Zrównoważone drzewo binarne: W tym drzewie binarnym różnica wysokości lewego i prawego poddrzewa wynosi co najwyżej 1. Zatem podczas dodawania lub usuwania węzła musimy ponownie zrównoważyć wysokość drzewa. Ten typ samobalansującego drzewa binarnego nazywany jest Drzewo AVL.
Istnieją trzy podstawowe operacje BST. Są one omówione szczegółowo poniżej.
Implementacja drzewa binarnego w C i 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);
}
Wyjście:
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
Implementacja drzewa binarnego w 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)
Wyjście:
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
Zastosowanie drzewa binarnego
Oto kilka typowych zastosowań drzewa binarnego:
- Organizowanie danych węzłów w posortowanej kolejności
- Używany w mapowaniu i ustawianiu obiektów węzłów w bibliotekach języków programowania.
- Wyszukiwanie elementów w strukturach danych
» Poznaj nasz kolejny samouczek na temat Algorytm kombinacyjny
