Arborele de căutare binar

Arborele de căutare binar
Tip de	lemn
Anul inventiei	1960
Autor	Andrew Donald Booth
Complexitatea în simbolurile O
In medie În cel mai rău caz Consumul de memorie Pe) Pe) Căutare O(log n) Pe) Introduce O(log n) Pe) Îndepărtarea O(log n) Pe)
Fișiere media la Wikimedia Commons

Arborele de căutare binar ( ing.  arbore de căutare binar , BST) este un arbore binar pentru care sunt îndeplinite următoarele condiții suplimentare ( proprietățile arborelui de căutare ):

• ambii subarbori - stânga și dreapta - sunt arbori de căutare binari;
• toate nodurile subarborelului din stânga al unui nod arbitrar X au valori ale cheii de date mai mici decât valoarea cheii de date a nodului X însuși;
• pentru toate nodurile subarborelului drept al unui nod arbitrar X, valorile cheilor de date sunt mai mari sau egale cu valoarea cheii de date a nodului X însuși.

Evident, datele de la fiecare nod trebuie să aibă chei pe care operația de comparare este mai mică decât este definită .

De obicei, informațiile care reprezintă fiecare nod sunt o înregistrare, nu un singur câmp de date. Totuși, este vorba despre implementare, nu despre natura arborelui de căutare binar.

În scopuri de implementare, un arbore de căutare binar poate fi definit ca:

• Un arbore binar este format din noduri (vertice) - înregistrări ale formei (date, stânga, dreapta), unde datele sunt niște date atașate nodului, stânga și dreapta sunt legături către nodurile care sunt copii ale acestui nod - stânga și dreapta fiii, respectiv. Pentru optimizarea algoritmilor, implementările specifice presupun și definiția câmpului părinte în fiecare nod (cu excepția rădăcinii) - o legătură către elementul părinte.
• Datele (date) au o cheie (cheie) pe care este definită operația de comparare „mai puțin decât”. În implementări specifice, aceasta poate fi o pereche (cheie, valoare) - (cheie și valoare), sau o referință la o astfel de pereche, sau o simplă definiție a unei operațiuni de comparare a structurii de date necesare sau o referință la aceasta.
• Pentru orice nod X sunt îndeplinite proprietățile arborelui de căutare: cheie[stânga[X]] < cheie[X] ≤ cheie[dreapta[X]], adică cheile de date ale nodului părinte sunt mai mari decât datele cheile fiului stâng și nu strict mai puțin decât cheile de date ale celui drept.

Arborele de căutare binar nu trebuie confundat cu heap-ul binar , care este construit după reguli diferite.

Principalul avantaj al unui arbore de căutare binar față de alte structuri de date este posibila eficiență ridicată a implementării algoritmilor de căutare și sortare bazați pe acesta .

Arborele de căutare binar este folosit pentru a construi structuri mai abstracte, cum ar fi seturi , multiseturi , tablouri asociative .

Operații de bază într-un arbore de căutare binar

Interfața de bază a arborelui de căutare binară constă din trei operații:

• FIND(K) - caută un nod care stochează o pereche (cheie, valoare) cu cheie = K.
• INSERT(K, V) - adăugarea unei perechi (cheie, valoare) = (K, V) în arbore.
• REMOVE(K) - eliminați nodul care stochează perechea (cheie, valoare) cu cheia = K.

Această interfață abstractă este un caz general, de exemplu, al unor astfel de interfețe luate din probleme de aplicație:

• „Agendă telefonică” - un depozit de înregistrări (numele unei persoane, numărul său de telefon) cu operațiuni de căutare și ștergere a înregistrărilor după numele unei persoane și operația de adăugare a unei noi înregistrări.
• Domain Name Server este un depozit de perechi (nume de domeniu, adresa IP) cu operațiuni de modificare și căutare.
• Spațiul de nume este o stocare a numelor de variabile cu valorile lor, care apare în compilatoarele de limbaje de programare.

De fapt, un arbore binar de căutare este o structură de date care poate stoca un tabel de perechi (cheie, valoare) și suportă trei operații: FIND, INSERT, REMOVE.

În plus, interfața de arbore binar include trei traversări suplimentare de noduri de arbore: INFIX_TRAVERSE, PREFIX_TRAVERSE și POSTFIX_TRAVERSE. Primul dintre ele vă permite să traversați nodurile arborelui în ordinea cheilor nedescrescătoare.

Găsirea unui element (FIND)

Dat : arborele T și cheia K.

Sarcină : verificați dacă există un nod cu cheia K în arborele T și, dacă da, returnați un link către acest nod.

Algoritm :

• Dacă arborele este gol, raportați că nodul nu a fost găsit și opriți.
• În caz contrar, comparați K cu valoarea cheie a nodului rădăcină X.
  • Dacă K=X, emiteți o legătură către acest nod și opriți.
  • Dacă K>X, căutați recursiv cheia K în subarborele din dreapta al lui T.
  • Dacă K<X, căutați recursiv cheia K în subarborele din stânga al lui T.

Adăugarea unui element (INSERT)

Dat : arborele T și perechea (K, V).

Sarcină : introduceți o pereche (K, V) în arborele T (dacă K se potrivește, înlocuiți V).

Algoritm :

• Dacă arborele este gol, înlocuiți-l cu un arbore cu un singur nod rădăcină ((K, V), nul, nul) și opriți.
• În caz contrar, comparați K cu cheia nodului rădăcină X.
  • Dacă K>X, adăugați recursiv (K, V) la subarborele din dreapta al lui T.
  • Dacă K<X, adăugați recursiv (K, V) la subarborele din stânga al lui T.
  • Dacă K=X, înlocuiți V-ul nodului curent cu noua valoare.

Eliminarea unui nod (REMOVE)

Dat : arborele T cu rădăcina n și cheia K.

Sarcină : eliminați din arborele T un nod cu cheia K (dacă există).

Algoritm :

• Dacă arborele T este gol, opriți;
• În caz contrar, comparați K cu cheia X a nodului rădăcină n .
  • Dacă K>X, îndepărtați recursiv K din subarborele din dreapta al lui T;
  • Dacă K<X, îndepărtați recursiv K din subarborele stâng al lui T;
  • Dacă K=X, atunci este necesar să luăm în considerare trei cazuri.
    • Dacă nu există ambii copii, atunci ștergem nodul curent și resetam legătura către el de la nodul părinte;
    • Dacă unul dintre copii nu există, atunci punem valorile câmpurilor copilului m în locul valorilor corespunzătoare ale nodului rădăcină, suprascriind vechile valori ale acestuia și eliberând memoria ocupată de nodul m ;
    • Dacă ambii copii sunt prezenți, atunci
      • Dacă lipsește nodul stâng m al subarborelui din dreapta (n->dreapta->stânga)
        • Copiem din nodul din dreapta în câmpurile șterse K, V și un link către nodul din dreapta al descendentului din dreapta.
      • In caz contrar
        • Luați nodul din stânga m al subarborelui din dreapta n->dreapta;
        • Copiați datele (cu excepția referințelor la elemente copil) din m în n ;
        • Îndepărtați recursiv nodul m .

Tree traversal (TRAVERSE)

Există trei operații de parcurgere a nodurilor arborescente care diferă în ordinea în care sunt parcurse nodurile.

Prima operație, INFIX_TRAVERSE, vă permite să traversați toate nodurile arborelui în ordinea crescătoare a tastelor și să aplicați o funcție de apel invers definită de utilizator f fiecărui nod, al cărui operand este adresa nodului. Această funcție funcționează de obicei numai pe perechea (K, V) stocată în nod. Operația INFIX_TRAVERSE poate fi implementată recursiv: mai întâi rulează singur pe subarborele din stânga, apoi rulează funcția dată pe rădăcină, apoi rulează singur pe subarborele din dreapta.

• INFIX_TRAVERSE (tr) Parcurgeți întregul arbore urmând ordinea (subarborele stânga, vârful , subarborele din dreapta). Elemente crescătoare
• PREFIX_TRAVERSE (tr) - traversează întregul arbore urmând ordinea ( sus , subarborele stânga, subarborele din dreapta). Elemente ca într-un copac
• POSTFIX_TRAVERSE (tr) Parcurgeți întregul arbore urmând ordinea (subarborele stânga, subarborele din dreapta, sus ). Elemente în ordine inversă, ca într-un arbore

În alte surse aceste funcții sunt numite inorder, preorder, respectiv postorder [1]

INFIX_TRAVERSE

Dat : arborele T și funcția f

Sarcină : aplicați f la toate nodurile arborelui T în ordinea crescătoare a tastelor

Algoritm :

• Dacă copacul este gol, oprește-te.
• In caz contrar
  • Traversați subarborele din stânga lui T în mod recursiv.
  • Aplicați funcția f la nodul rădăcină.
  • Traversați recursiv subarborele din dreapta lui T.

În cel mai simplu caz, funcția f poate scoate valoarea perechii (K, V). Când utilizați operația INFIX_TRAVERSE, toate perechile vor fi afișate în ordinea crescătoare a tastelor. Dacă utilizați PREFIX_TRAVERSE, atunci perechile vor fi afișate în ordinea corespunzătoare descrierii arborelui dată la începutul articolului.

Împărțirea unui arbore după cheie

Operația „divizarea arborelui după cheie” vă permite să împărțiți un arbore de căutare în două: cu tastele < K 0 și ≥ K 0 .

Combinând doi copaci într-unul singur

Operație inversă: există doi arbori de căutare, unul are chei < K 0 , celălalt are chei ≥ K 0 . Îmbină-le într-un singur copac.

Avem doi arbori: T 1 (mai mic) și T 2 (mai mare). Mai întâi trebuie să decideți unde să luați rădăcina: de la T 1 sau T 2 . Nu există o metodă standard, opțiunile posibile sunt:

• Luați la întâmplare (vezi arbore cartezian ).
• Dacă dimensiunea întregii ramuri este menținută la fiecare nod din arbore (vezi arborele chei implicite ), dezechilibrul pentru ambele opțiuni poate fi estimat cu ușurință.

algTree Union (T1, T2) dacă T1 este gol, returnați T2 dacă T2 este gol, returnați T1 dacă decideți să faceți T1 rădăcină, atunci T = UnionTrees(T1.dreapta, T2) T1.dreapta = T întoarce T1 in caz contrar T = UnionTrees(T1, T2.stânga) T2.stânga = T întoarcere T2

Echilibrarea arborilor

Este întotdeauna de dorit ca toate căile dintr-un copac de la rădăcină la frunze să aibă aproximativ aceeași lungime, adică ca adâncimea ambelor subarbori din stânga și din dreapta să fie aproximativ aceeași la orice nod. În caz contrar, performanța este pierdută.

În cazul degenerat, se poate dovedi că întregul arbore din stânga este gol la fiecare nivel, există doar arbori din dreapta, caz în care arborele degenerează într-o listă (mergând la dreapta). Căutarea (și, prin urmare, ștergerea și adăugarea) într-un astfel de arbore este egală ca viteză cu căutarea într-o listă și mult mai lentă decât căutarea într-un arbore echilibrat.

Operația de rotație a arborelui este utilizată pentru a echilibra arborele. Virajul la stânga arată astfel:

• a fost Stânga (A) = L, Dreapta (A) = B, Stânga (B) = C, Dreapta (B) = R
• rotația schimbă A și B, obținând Stânga (A) = L, Dreapta (A) = C, Stânga (B) = A, Dreapta (B) = R
• legătura care a indicat anterior spre A se schimbă și în nodul Parent(A), după rotație indică către B.

Întoarcerea la dreapta arată la fel, este suficient să înlocuiți toate stânga cu dreapta în exemplul de mai sus și invers. Este destul de evident că rotația nu rupe ordinea arborelui și are un efect previzibil (+1 sau -1) asupra adâncimii tuturor subarborilor afectați. Algoritmi precum arborele roșu-negru și AVL sunt utilizați pentru a decide ce rotații să efectueze după adăugarea sau eliminarea . Ambele necesită informații suplimentare în noduri - 1 bit pentru roșu-negru sau un număr semnat pentru AVL. Un copac roșu-negru necesită nu mai mult de două ture după adăugare și nu mai mult de trei după îndepărtare, dar cel mai grav dezechilibru poate fi de până la 2 ori (cea mai lungă cale este de 2 ori mai lungă decât cea mai scurtă). Arborele AVL necesită nu mai mult de două rotații după adăugare și până la adâncimea arborelui după ștergere, dar este perfect echilibrat (dezechilibru cu cel mult 1).

Vezi și

• Matrice asociativă
• arbore cartezian
• Sortare cu un arbore binar

Copaci echilibrați:

• B-arborele
• arborele AVL
• Copac roșu-negru

Note

1. ↑ Roman Akopov. Arbori binari de căutare . Revista RSDN #5-2003 (13 martie 2005). Consultat la 1 noiembrie 2014. Arhivat din original la 1 noiembrie 2014. (nedefinit)

Link -uri

• Binary Tree Visualizer  (animație JavaScript a diferitelor structuri de date bazate pe BT)

Arborele (structura de date)
Arborele de căutare binar Arborele (teoria graficelor) structura arborelui
Arbori binari	arbore binar T-tree
Arbori binari cu auto-echilibrare	arbore AA arborele AVL Copac roșu-negru Splay arbore copac cu amenzi arbore cartezian Arborele Fibonacci B-arborele T-tree
B-copaci	2-3-copac B⁺-arborele B*-copac B x -arbore arborele UB 2-3-4 arbore (a,b)-copac copac dansant
arbori de prefix	arbore de sufix Arborele de prefix comprimat Arborele de căutare ternar
Partiționarea binară a spațiului	arbore k-dimensional arborele VP
Arbori non-binari	Quadtree octree Voxel rar Octree arbore exponenţial Arborele PQ
Despărțirea spațiului	R-arborele Arborele R Hilbert R+-arborele R*-copac X-arborele M-arbore Arborele Fenwick Arborele segmentului
Alți copaci	morman arbore de hash arborele degetelor arbore metric Arborele de acoperire BK-arborele Copac cu lanțuri duble iDistanța Arbore tăiat de legături Arborele LSM
Algoritmi	Lățimea prima căutare Profunzime prima căutare Algoritmul DSW protocolul spanning tree

Structuri de date
Liste	matrice listă legată individual listă dublu legată Lista de trecere
Copaci	B-arborele Arborele de căutare binar arborele AVL Copac roșu-negru morman
Contează	Graficul dirijat Graficul aciclic direcționat Diagrama de decizie binară Hipergraf
Alte	Tabel de hash Grămadă