copacii de căutare binară acceptă trei operații principale: inserarea elementelor, ștergerea elementelor și căutarea (verificarea prezenței unei chei).căutarea într-un arbore de căutare binar pentru o anumită cheie poate fi programată recursiv sau iterativ.

începem prin examinarea nodului rădăcină. Dacă arborele este nul, cheia pe care o căutăm nu există în copac. În caz contrar, dacă cheia este egală cu cea a rădăcinii, căutarea are succes și returnăm nodul. Dacă cheia este mai mică decât cea a rădăcinii, căutăm subarborele din stânga., În mod similar, dacă cheia este mai mare decât cea a rădăcinii, căutăm sub-arborele drept. Acest proces se repetă până când cheia este găsit sau subarbore rămas este nul. Dacă cheia căutată nu este găsită după atingerea unui sub-arbore nul, atunci cheia nu este prezentă în arbore. Acest lucru este ușor de exprimat ca un algoritm recursiv (implementat în Python):

același algoritm poate fi implementat iterativ:

aceste două exemple nu acceptă duplicate, adică se bazează pe relația de ordine fiind o ordine totală.

se poate observa că algoritmul recursiv este coada recursivă., Într-o limbă de sprijin de optimizare apel coada, exemplele recursive și iterative va compila la programe echivalente.deoarece în cel mai rău caz acest algoritm trebuie să caute de la rădăcina arborelui până la frunza cea mai îndepărtată de rădăcină, operația de căutare necesită timp proporțional cu înălțimea arborelui (vezi terminologia arborelui). În medie, arborii de căutare binari cu chei de noduri au înălțimea O(log| Nodes/). Cu toate acestea, în cel mai rău caz, copacii de căutare binari pot avea o(|noduri|) înălțime, când arborele dezechilibrat seamănă cu o listă legată (copac degenerat).,dacă relația de ordine este doar o precomandă totală, o extensie rezonabilă a funcționalității este următoarea: de asemenea, în cazul căutării egalității până la frunze. Permițând astfel să specificați (sau hard-wire) o direcție, în cazul în care pentru a insera un duplicat, fie la dreapta sau la stânga tuturor duplicatelor din copac până în prezent. Dacă direcția este hard-wired, ambele opțiuni, dreapta și stânga, susțineți o stivă cu inserați duplicat ca operație de împingere și ștergeți ca operație pop.,: 155

un fel de arbore binar echipat cu o astfel de funcție de căutare devine stabil.

InsertionEdit

inserarea începe ca o căutare ar începe; dacă cheia nu este egală cu cea a rădăcinii, căutăm subtreele din stânga sau din dreapta ca înainte. În cele din urmă, vom ajunge la un nod extern și vom adăuga noua pereche cheie-valoare (aici codificată ca o înregistrare „newNode”) ca copil drept sau stâng, în funcție de cheia nodului., Cu alte cuvinte, examinăm rădăcina și introducem recursiv noul nod în subarborele din stânga dacă cheia sa este mai mică decât cea a rădăcinii sau subarborele din dreapta dacă cheia sa este mai mare sau egală cu rădăcina.

Iată cum ar putea fi efectuată o inserție tipică de arbore de căutare binară într-un arbore binar în C++:

alternativ, o versiune nerecursivă ar putea fi implementată astfel., Folosind un pointer-to-pointer pentru a urmări de unde am venit permite codului să evite verificarea explicită și manipularea cazului în care trebuie să introducă un nod la rădăcina arborelui:

varianta procedurală distructivă de mai sus modifică arborele în loc. Utilizează doar spațiu heap constant (iar versiunea iterativă folosește și spațiu stack constant), dar versiunea anterioară a arborelui este pierdută., Alternativ, ca în următorul exemplu Python, putem reconstrui toți strămoșii nodului inserat; orice referire la rădăcina arborelui original rămâne validă, făcând arborele o structură de date persistentă:

partea care este reconstruită folosește spațiul O(log n) în cazul mediu și O(n) în cel mai rău caz.în oricare dintre versiuni, această operație necesită timp proporțional cu înălțimea copacului în cel mai rău caz, care este timpul O(log n) în cazul mediu pentru toți copacii, dar timpul O(n) în cel mai rău caz.,un alt mod de a explica inserarea este că, pentru a insera un nou nod în arbore, cheia sa este mai întâi comparată cu cea a rădăcinii. Dacă cheia sa este mai mică decât cea a rădăcinii, este apoi comparată cu cheia copilului stâng al rădăcinii. Dacă cheia sa este mai mare, este comparată cu copilul drept al rădăcinii. Acest proces continuă, până când noul nod este comparat cu un nod de frunze și apoi este adăugat ca copilul drept sau stâng al acestui nod, în funcție de cheia sa: dacă cheia este mai mică decât cheia frunzei, atunci este introdus ca copilul stâng al frunzei, altfel ca copilul drept al frunzei.,există și alte modalități de introducere a nodurilor într-un arbore binar, dar aceasta este singura modalitate de a introduce noduri la frunze și, în același timp, de a păstra structura BST.

DeletionEdit

când eliminați un nod dintr-un arbore de căutare binar, este obligatoriu să mențineți secvența în ordine a nodurilor. Există multe posibilități de a face acest lucru. Cu toate acestea, următoarea metodă care a fost propusă de T. Hibbard în 1962 garantează că înălțimile subtreelor subiectului sunt modificate de cel mult unul., Există trei cazuri posibile de luat în considerare:

• ștergerea unui nod fără copii: pur și simplu eliminați nodul din copac.
• ștergerea unui nod cu un copil: eliminați nodul și înlocuiți-l cu copilul său.
• ștergerea unui nod D cu doi copii: alegeți fie predecesorul În ordine al lui D, fie succesorul în ordine E (vezi figura). În loc să ștergeți D, suprascrieți cheia și valoarea cu E. dacă E nu are un copil, eliminați e de la părintele său anterior G. Dacă E are un copil F, este un copil potrivit, astfel încât să înlocuiască e la părintele E.,

în toate cazurile, când D se întâmplă să fie rădăcina, faceți din nou rădăcina nodului de înlocuire.nodurile cu doi copii sunt mai greu de șters., Succesorul în ordine al unui nod este copilul cel mai stâng al subtree-ului drept, iar predecesorul în ordine al unui nod este copilul cel mai drept al subtree-ului stâng. În ambele cazuri, acest nod va avea doar unul sau niciun copil. Ștergeți-l în conformitate cu unul dintre cele două cazuri mai simple de mai sus.utilizarea consecventă a succesorului în ordine sau a predecesorului în ordine pentru fiecare instanță a cazului cu doi copii poate duce la un arbore dezechilibrat, astfel încât unele implementări selectează una sau alta în momente diferite.,analiza Runtime: deși această operație nu traversează întotdeauna copacul până la o frunză, aceasta este întotdeauna o posibilitate; astfel, în cel mai rău caz, necesită timp proporțional cu înălțimea copacului. Nu necesită mai mult chiar și atunci când nodul are doi copii, deoarece urmează încă o singură cale și nu vizitează niciun nod de două ori.,

TraversalEdit

Odată ce arbore binar de căutare a fost creat, elementele sale pot fi preluate în scopul de recursiv traversează subarborele stâng al nodului rădăcină, accesarea nodul în sine, apoi recursiv traversează subarborele drept al nodului, continuând acest model cu fiecare nod din arbore ca e recursiv accesate. Ca și în cazul tuturor copacilor binari, se poate efectua o traversare pre-comandă sau o traversare post-comandă, dar nici nu este probabil să fie utilă pentru copacii de căutare binară., O traversare în ordine a unui arbore de căutare binar va avea ca rezultat întotdeauna o listă sortată de elemente de nod (numere, șiruri sau alte elemente comparabile).

codul pentru traversarea în ordine în Python este prezentat mai jos. Acesta va apela callback (unele funcții programatorul dorește să apeleze la valoarea nodului, cum ar fi imprimarea pe ecran) pentru fiecare nod din copac.

Traversal necesită o (n) timp, deoarece trebuie să viziteze fiecare nod. Acest algoritm este, de asemenea, O(n), deci este optim asimptotic.

Traversal poate fi, de asemenea, implementat iterativ. Pentru anumite aplicații, de ex., căutare egală mai mare, căutare aproximativă, o operație pentru traversarea cu un singur pas (iterativ) poate fi foarte utilă. Acest lucru este, desigur, implementat fără construcția de apel invers și ia O(1) în medie și O(log n) în cel mai rău caz.uneori avem deja un arbore binar și trebuie să determinăm dacă este un BST. Această problemă are o soluție recursivă simplă.,

proprietatea BST-fiecare nod din subarborele din dreapta trebuie să fie mai mare decât nodul curent și fiecare nod din subarborele din stânga trebuie să fie mai mic decât nodul curent—este cheia pentru a afla dacă un arbore este un BST sau nu. Algoritmul lacom—pur și simplu traversați arborele, la fiecare nod verificați dacă nodul conține o valoare mai mare decât valoarea la copilul stâng și mai mică decât valoarea copilului drept—nu funcționează pentru toate cazurile., Luați în considerare următoarele copac:

 20 / \ 10 30 / \ 5 40

În arborele de mai sus, fiecare nod îndeplinește condiția ca nod conține o valoare mai mare decât cea a lăsat copilul și mai mici decât dreptul său de copil ține, și totuși nu este un BST: valoarea 5 este pe subarborele drept al nodului care conțin 20, o încălcare a BST proprietate.

în loc să luăm o decizie bazată exclusiv pe valorile unui nod și ale copiilor săi, avem nevoie și de informații care curg în jos de la părinte., În cazul arborelui de mai sus, dacă ne-am putea aminti despre nodul care conține valoarea 20, am vedea că nodul cu valoarea 5 încalcă contractul de proprietate BST.,

Deci, starea de care avem nevoie pentru a verifica la fiecare nod este:

• dacă nodul este plecat copil de-al său părinte, atunci acesta trebuie să fie mai mică decât (sau egală cu) părinte și acesta trebuie să treacă în jos valoarea la părintele său subarbore drept al acestuia de a face sigur că nici unul dintre nodurile în care subarbore este mai mare decât părintele
• dacă nodul este dreptul copilului de mamă, atunci acesta trebuie să fie mai mare decât mamă și trebuie să treacă în jos valoarea de la mamă la subarbore stânga sa să asigurați-vă că nici unul dintre nodurile în care subarbore este mai mică decât mamă.,

O soluție recursivă în C++ pot explica acest lucru în continuare:

node->key+1 și node->key-1 sunt făcute pentru a permite numai elemente distincte în BST.

dacă dorim ca aceleași elemente să fie prezente, atunci putem folosi doar node->key în ambele locuri.

apelul inițial pentru această funcție poate fi ceva de genul:

if (isBST(root, INT_MIN, INT_MAX)) { puts("This is a BST.");} else { puts("This is NOT a BST!");}

în Esență, putem păstra crearea de un interval valid (incepand de la ) și să păstreze în scădere în jos pentru fiecare nod ca vom merge în jos recursiv.,

așa cum se arată în secțiunea #Traversal, o traversare în ordine a unui arbore de căutare binar returnează nodurile sortate. Astfel, trebuie doar să păstrăm ultimul nod vizitat în timp ce traversăm arborele și să verificăm dacă cheia sa este mai mică (sau mai mică/egală, dacă duplicatele trebuie permise în arbore) în comparație cu cheia curentă.

Paralel algorithmsEdit

Există, de asemenea, algoritmi paraleli pentru copaci binar de căutare, inclusiv introducerea/ștergerea mai multe elemente de construcție din matrice, filtru cu anumite predicator, aplatiza pentru a o matrice, care fuzionează/scăderea/intersectează doi copaci, etc., Acești algoritmi pot fi implementate folosind join pe baza de arbore de algoritmi, care poate ține, de asemenea, arborele echilibrat, folosind mai multe echilibrarea schemelor (inclusiv AVL tree, rosu-negru copac, greutate echilibrat copac și treap) .