Ce este un arbore de căutare binară?
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 (cunoscut și sub numele de părinte) care conține o anumită valoare (poate fi orice tip de date).
- 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. Acest lucru 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 atunci când adăugați în continuare noduri care sunt mereu mai mare decât nodul anterior (părintele său), același lucru 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.
- Inorder: traversarea în ordine a arborelui.
- Preordonare: traversarea precomandă a copacului.
- Postorder: traversarea după comandă a arborelui.
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 drept, fie la copilul stâng, 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, treci la copilul din stânga, altfel (dacă este mai mare) mergi 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.
Căutare în lățime (BFS)
Căutarea prin lățime este un algoritm folosit pentru a traversa un BST. Începe de la nodul rădăcină și se deplasează într-o manieră laterală (de la o parte la alta), căutând nodul dorit. Acest tip de căutare poate fi descris ca O (n) având în vedere că fiecare nod este vizitat o dată și dimensiunea arborelui se corelează direct cu lungimea căutării.
Căutare în profunzime (DFS)
Cu o abordare de căutare pentru prima adâncime, începem cu nodul rădăcină și călătorim pe o singură ramură. Dacă nodul dorit se găsește de-a lungul acelei ramuri, minunat, dar dacă nu, continuați în sus și căutați noduri nevizitate. Acest tip de căutare are, de asemenea, o mare notație O a lui O (n).
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 implementarea anume.
Ștergere
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 inorder (nodul cel mai la stânga 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) în cazul copacilor înclinați.
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 mare / 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 curent. 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: BST
- Performanță în cel mai rău caz:
O(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. Cel mai rău caz este O (n), deoarece BST poate fi dezechilibrat.
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 de la 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;
}
}
}
}
}
Ștergeți operațiunea
void deleteNode(struct node* root, int data){
if (root == NULL) root=tempnode;
if (data < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else
{
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
struct node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}
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 ei înșiși 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));
}
Traversal
Există 3 tipuri de traversări care se efectuează de obicei peste un arbore de căutare binar. Toate aceste traversări au un mod oarecum comun de a trece peste nodurile arborelui.
Pentru a
Această traversare trece mai întâi pe subarborele din stânga al nodului rădăcină, apoi accesează nodul curent, urmat de subarborele din dreapta al nodului curent. Codul reprezintă și cazul de bază, care spune că un copac gol este, de asemenea, un copac de căutare binar.
void inOrder(struct node* root) {
// Base case
if (root == null) {
return;
}
// Travel the left sub-tree first.
inOrder(root.left);
// Print the current node value
printf("%d ", root.data);
// Travel the right sub-tree next.
inOrder(root.right);
}
Pre-comanda
Această traversare accesează mai întâi valoarea curentă a nodului, apoi traversează sub-arborii din stânga și respectiv din dreapta.
void preOrder(struct node* root) {
if (root == null) {
return;
}
// Print the current node value
printf("%d ", root.data);
// Travel the left sub-tree first.
preOrder(root.left);
// Travel the right sub-tree next.
preOrder(root.right);
}
Post-comandă
Această traversare pune valoarea rădăcinii în sfârșit și trece mai întâi pe sub-copacii din stânga și din dreapta. Ordinea relativă a sub-copacilor din stânga și din dreapta rămâne aceeași. Doar poziția rădăcinii se schimbă în toate traversările menționate mai sus.
void postOrder(struct node* root) {
if (root == null) {
return;
}
// Travel the left sub-tree first.
postOrder(root.left);
// Travel the right sub-tree next.
postOrder(root.right);
// Print the current node value
printf("%d ", root.data);
}
Videoclipuri relevante pe canalul YouTube Routech
Arborele de căutare binar: transversal și înălțime
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
Arborele binar perfect Un arbore binar este arborele binar perfect în care toate nodurile interne au doi copii și toate frunzele sunt la același nivel.
18
/
/
15 30
/ /
40 50 100 40
Mărirea unui BST
Uneori trebuie să stocăm câteva informații suplimentare cu structurile de date tradiționale pentru a ne ușura sarcinile. De exemplu, luați în considerare un scenariu în care ar trebui să găsiți al zecelea cel mai mic număr dintr-un set. Aici puteți folosi forța brută, dar putem reduce complexitatea problemei la O(lg n) prin mărirea unui roșu-negru sau a oricărui arbore auto-echilibrat (unde n este numărul de elemente din set). De asemenea, putem calcula rangul oricărui element din O(lg n) timp. Să luăm în considerare un caz în care mărim un copac roșu-negru pentru a stoca informațiile suplimentare necesare. Pe lângă atributele obișnuite, putem stoca numărul de noduri interne în subarborele înrădăcinat la x (dimensiunea subarborelui înrădăcinat la x, inclusiv nodul în sine). Fie x orice nod arbitrar al unui copac.
x.size = x.left.size + x.right.size + 1
În timp ce mărim arborele, ar trebui să ținem cont de faptul că ar trebui să putem menține informațiile mărite, precum și alte operații precum inserarea, ștergerea, actualizarea în O(lg n) timp.
Din moment ce, știm că valoarea x.left.size ne va da numărul de noduri care continuă x în ordinea traversării arborelui. Prin urmare, x.left.size + 1 este rangul lui x din subarborele înrădăcinat la x.
