Un copac este o structură de date compusă din noduri care are următoarele caracteristici:
- Fiecare copac are un nod rădăcină (în partea de sus) având o anumită valoare.
- Nodul rădăcină are zero sau mai multe noduri copil.
- Fiecare nod copil are zero sau mai multe noduri copil și așa mai departe. Aceasta creează un subarbore în copac. Fiecare nod are propriul subarborel alcătuit din copiii săi și copiii lor, etc. Aceasta înseamnă că fiecare nod singur poate fi un copac.
Un arbore de căutare binar (BST) adaugă aceste două caracteristici:
- Fiecare nod are maximum doi copii.
- Pentru fiecare nod, valorile nodurilor descendente din stânga sunt mai mici decât cele ale nodului curent, care la rândul lor este mai mic decât nodurile descendente din dreapta (dacă există).
BST este construit pe ideea de căutare binară algoritm, care permite căutarea rapidă, inserarea și eliminarea nodurilor. Modul în care sunt configurate înseamnă că, în medie, fiecare comparație permite operațiunilor să sară aproximativ jumătate din arbore, astfel încât fiecare căutare, inserare sau ștergere să ia timp proporțional cu logaritmul numărului de articole stocate în arbore, O(log n).
Cu toate acestea, uneori se poate întâmpla cel mai rău caz, atunci când arborele nu este echilibrat și complexitatea timpului este O(n) pentru toate aceste trei funcții. De aceea, arborii auto-echilibrați (AVL, roșu-negru etc.) sunt mult mai eficienți decât BST de bază.
Exemplu de scenariu cel mai prost: Acest lucru se poate întâmpla când adăugați în continuare noduri care sunt mereu mai mare decât nodul anterior (este părinte), la fel se poate întâmpla atunci când adăugați întotdeauna noduri cu valori mai mici decât părinții lor.
Operații de bază pe un BST
- Creați: creează un copac gol.
- Insert: introduceți un nod în copac.
- Căutare: caută un nod în copac.
- Șterge: șterge un nod din copac.
Crea
Inițial se creează un copac gol, fără noduri. Variabila / identificatorul care trebuie să indice spre nodul rădăcină este inițializată cu un NULL valoare.
Căutare
Începeți mereu să căutați copacul de la nodul rădăcină și coborâți de acolo. Comparați datele din fiecare nod cu cel pe care îl căutați. Dacă nodul comparat nu se potrivește, fie treceți la copilul din dreapta, fie la copilul din stânga, ceea ce depinde de rezultatul următoarei comparații: Dacă nodul pe care îl căutați este mai mic decât cel cu care îl comparați, treceți la copilul din stânga, altfel (dacă este mai mare) mergeți la copilul din dreapta. De ce? Deoarece BST este structurat (conform definiției sale), copilul potrivit este întotdeauna mai mare decât părintele, iar copilul stâng este întotdeauna mai mic.
Introduce
Este foarte asemănător cu funcția de căutare. Începeți din nou de la rădăcina copacului și coborâți recursiv, căutând locul potrivit pentru a insera noul nostru nod, în același mod așa cum s-a explicat în funcția de căutare. Dacă un nod cu aceeași valoare este deja în arbore, puteți alege fie să inserați duplicatul, fie să nu. Unii copaci permit duplicate, alții nu. Depinde de o anumită implementare.
Șterge
Există 3 cazuri care se pot întâmpla atunci când încercați să ștergeți un nod. Dacă are,
- Fără subarbore (fără copii): Acesta este cel mai ușor. Puteți pur și simplu să ștergeți nodul, fără a fi necesare acțiuni suplimentare.
- Un subarbore (un copil): Trebuie să vă asigurați că după ștergerea nodului, copilul său este apoi conectat la părintele nodului șters.
- Două subarburi (doi copii): Trebuie să găsiți și să înlocuiți nodul pe care doriți să îl ștergeți cu succesorul său (cel mai mare nod din subarborele din dreapta).
Complexitatea timpului pentru crearea unui copac este O(1). Complexitatea de timp pentru căutarea, inserarea sau ștergerea unui nod depinde de înălțimea arborelui h, deci cel mai rău caz este O(h).
Predecesorul unui nod
Predecesorii pot fi descriși ca nodul care ar veni chiar înainte de nodul în care vă aflați în prezent. Pentru a găsi predecesorul nodului curent, uitați-vă la cel mai drept / cel mai mare nod frunză din subarborele din stânga.
Succesorul unui nod
Succesorii pot fi descriși ca nodul care ar veni imediat după nodul în care vă aflați în prezent. Pentru a găsi succesorul nodului curent, uitați-vă la cel mai stâng / cel mai mic nod frunză din subarborele din dreapta.
Tipuri speciale de BT
- Morman
- Copac roșu-negru
- B-copac
- Arborele Splay
- Copac N-ari
- Trie (arborele Radix)
Runtime
Structura datelor: matrice
- Performanță în cel mai rău caz:
O(log n) - Performanță în cel mai bun caz:
O(1) - Performanță medie:
O(log n) - Complexitatea spațiului în cel mai rău caz:
O(1)
Unde n este numărul de noduri din BST.
Implementarea BST
Iată o definiție pentru un nod BST care are unele date, referindu-se la nodurile copil stânga și dreapta.
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};Operațiunea de căutare
Ori de câte ori trebuie căutat un element, începeți să căutați din nodul rădăcină. Apoi, dacă datele sunt mai mici decât valoarea cheii, căutați elementul din subarborele din stânga. În caz contrar, căutați elementul din subarborele din dreapta. Urmați același algoritm pentru fiecare nod.
struct node* search(int data){
struct node *current = root;
printf("Visiting elements: ");
while(current->data != data){
if(current != NULL) {
printf("%d ",current->data);
//go to left tree
if(current->data > data){
current = current->leftChild;
}//else go to right tree
else {
current = current->rightChild;
}
//not found
if(current == NULL){
return NULL;
}
}
}
return current;
}Operațiunea de inserare
Ori de câte ori se introduce un element, localizați mai întâi locația corectă. Începeți să căutați din nodul rădăcină, apoi dacă datele sunt mai mici decât valoarea cheii, căutați locația goală din subarborele din stânga și introduceți datele. În caz contrar, căutați locația goală din subarborele din dreapta și introduceți datele.
void insert(int data) {
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//if tree is empty
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}//go to right of the tree
else {
current = current->rightChild;
//insert to the right
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
} Arborii de căutare binari (BST) ne oferă, de asemenea, acces rapid la predecesori și succesori. Predecesorii pot fi descriși ca nodul care ar veni chiar înainte de nodul în care vă aflați în prezent.
- Pentru a găsi predecesorul nodului curent, uitați-vă la cel mai drept / cel mai mare nod frunză din subarborele din stânga. Succesorii pot fi descriși ca nodul care ar veni imediat după nodul în care vă aflați în prezent.
- Pentru a găsi succesorul nodului curent, uitați-vă la cel mai stâng / cel mai mic nod frunză din subarborele din dreapta.
Să ne uităm la câteva proceduri care operează pe copaci.
Deoarece copacii sunt definiți recursiv, este foarte obișnuit să scrieți rutine care funcționează pe copaci care sunt recursivi.
De exemplu, dacă vrem să calculăm înălțimea unui copac, adică înălțimea unui nod rădăcină, putem merge mai departe și recursiv să facem acest lucru, trecând prin copac. Deci putem spune:
- De exemplu, dacă avem un copac nul, atunci înălțimea acestuia este 0.
- În caz contrar, suntem 1 plus maximul arborelui copil stâng și arborele copil drept.
Deci, dacă ne uităm la o frunză, de exemplu, înălțimea ar fi 1, deoarece înălțimea copilului din stânga este zero, este 0 și înălțimea copilului din dreapta este, de asemenea, 0. Deci, maxima este 0, atunci 1 plus 0.
Algoritm de înălțime (copac)
if tree = nil:
return 0
return 1 + Max(Height(tree.left),Height(tree.right))Iată codul din C ++
int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{
int rDepth = maxDepth(node->right);
int lDepth = maxDepth(node->left);
if (lDepth > rDepth)
{
return(lDepth+1);
}
else
{
return(rDepth+1);
}
}
} Ne-am putea uita și la calcularea dimensiunii unui copac care este numărul de noduri.
- Din nou, dacă avem un copac nul, avem zero noduri.
În caz contrar, avem numărul de noduri din copilul din stânga plus 1 pentru noi înșine, plus numărul de noduri din copilul din dreapta. Deci 1 plus dimensiunea arborelui din stânga plus dimensiunea arborelui din dreapta.
Algoritm de dimensiune (copac)
if tree = nil
return 0
return 1 + Size(tree.left) + Size(tree.right)Iată codul din C ++
int treeSize(struct node* node)
{
if (node==NULL)
return 0;
else
return 1+(treeSize(node->left) + treeSize(node->right));
}Videoclipuri relevante pe canalul YouTube Routech
Următoarele sunt tipurile comune de arbori binari:
Arborele binar complet / Arborele binar strict: un arbore binar este complet sau strict dacă fiecare nod are exact 0 sau 2 copii.
18
/
15 30
/ /
40 50 100 40În Arborele binar complet, numărul de noduri frunze este egal cu numărul de noduri interne plus unu.
Arborele binar complet: un arbore binar este arborele binar complet dacă toate nivelurile sunt complet umplute, cu excepția eventualului ultim nivel, iar ultimul nivel are toate tastele cât mai stânga posibil
18
/
15 30
/ /
40 50 100 40
/ /
8 7 9 
