Arborele binar în structura datelor (EXEMPLU)
Sarah Chen
Ce este un arbore binar?
Cuvântul binar înseamnă doi. În structura de date arborescentă „Arborele binar”, înseamnă un arbore în care fiecare nod poate avea maximum două noduri secundare (noduri stânga și dreapta). Este un arbore binar simplu.
Cu toate acestea, există un alt arbore binar care este folosit cel mai frecvent și are mai multe cazuri de utilizare. Se numește Arborele de căutare binar (BST). Acest arbore poate face algoritmul de căutare mult mai rapid, exact log(n) complexitatea timpului. În structura de date, n înseamnă numărul de noduri din arborele binar.
Care sunt diferențele dintre arborele binar și arborele de căutare binar?
Diferența dintre BST și arborele binar obișnuit este că nodul din stânga BST are o valoare mai mică decât nodul rădăcină, iar nodul din dreapta are o valoare mai mare decât nodul rădăcină. Deci, subarborele din stânga va conține întotdeauna o valoare mai mică decât rădăcina, iar subarborele din dreapta va conține întotdeauna o valoare mai mare decât rădăcina.
Exemplu de arbori binari de căutare
Să avem următorul exemplu pentru a demonstra conceptele Arborele de căutare binar.
Aici puteți toate nodurile să urmeze disciplina dată. Există o formulă pentru numărul maxim de noduri în Arborele de căutare binar. Dacă observăm arborele de mai sus, putem vedea că fiecare nod are doi copii, cu excepția tuturor nodurilor frunze. Și înălțimea (h) a arborelui binar dat este 4. Formula este 2h - 1. Deci, dă 15.
Imaginea de mai sus nu este un arbore binar complet sau un arbore binar echilibrat, ci se numește arbore binar complet sau arbore binar echilibrat. Există o altă structură de date numită AVL (un alt tip de arbore binar) care optimizează înălțimea arborelui binar și efectuează căutarea mai rapid pentru BST, ca în figura 3.
Încercați să calculați traversarea în ordine a arborelui binar prezentat mai sus. Veți descoperi că va oferi o matrice sortată nedescrescătoare, iar algoritmii Traversal vor fi la fel ca și Arborele binar.
Tipuri de arbore binar
Iată câteva tipuri importante de arbore binar:
- Arborele binar complet: Fiecare nod poate avea 0 sau 2 noduri copil în acest arbore binar. Un singur nod copil nu este permis în acest tip de arbore binar. Deci, cu excepția nodului frunză, toate nodurile vor avea 2 copii.
- Arborele binar complet: Fiecare nod poate avea 0 sau 2 noduri. Pare a arborelui binar complet, dar toate elementele frunzelor sunt înclinate către subarborele din stânga, în timp ce în arborele binar complet nodul poate fi în subarborele din dreapta sau din stânga.
- Arborele binar perfect: Toate nodurile trebuie să aibă 0 sau 2 noduri, iar toate nodurile frunzelor trebuie să fie la același nivel sau înălțime. Exemplul de mai sus al unei structuri de arbore binar complet nu este un arbore binar perfect deoarece nodul 6 și nodul 1,2,3 nu sunt la aceeași înălțime. Dar exemplul Arborelui Binar Complet este un arbore binar perfect.
- Arborele binar degenerat: Fiecare nod poate avea doar un singur copil. Toate operațiunile precum căutarea, inserarea și ștergerea durează O(N).
- Arborele binar echilibrat: Aici acest arbore binar, diferența de înălțime a subarborelui din stânga și din dreapta este de cel mult 1. Deci, în timp ce adăugăm sau ștergem un nod, trebuie să echilibrăm din nou înălțimea arborelui. Acest tip de arbore binar auto-echilibrat se numește Copac AVL.
Există trei operațiuni de bază ale BST. Acestea sunt discutate în detaliu mai jos.
Implementarea arborelui binar în 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);
}
ieșire:
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
Implementarea arborelui binar în 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)
ieșire:
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
Aplicarea arborelui binar
Iată câteva aplicații comune ale arborelui binar:
- Organizarea datelor nodurilor în ordine sortată
- Folosit în hartă și set de obiecte nod în bibliotecile limbajului de programare.
- Căutarea elementelor în structurile de date
» Aflați următorul nostru tutorial despre Algoritmul de combinare
