Pretraga stabla

U informatici, pretraga stabla je struktura podataka koja se koristi za nalaženje određene vrednosti unutar skupa. Da bi stablo funkcionisalo kao stablo za pretragu, ključ svakog čvora mora biti veći od svih ključeva u levom podstablu i manji od svih ključeva u desnom podstablu.^[1]

Prednost pretrage stabla je njegova vremenska delotvornost, jer je stablo uravnoteženo, što znači da su listovi na oba kraja uporedivi. Postoje razne vrste stabala-pretraga, kod nekih su efikasna dodavanja i brisanja elemenata, s tim što nakon tih operacija stablo se mora održavati uravnoteženim.

Vrste stabala

Binarno stablo pretrage

Binarno stablo pretrage zasniva se na čvorovima kod kojih je svaki čvor struktura koja se sastoji iz ključa čvora i najviše dva podstabla, levog i desnog. Svi čvorovi u levom podstablu moraju imati manji ključ od ključa čvora. Svi čvorovi u desnom podstablu moraju imati veći ključ od ključa čvora. Stabla sa ovim osobinama se zovu binarna stabla pretrage.

Vremenska složenost za pretragu u binarnom stablu pretrage je u proseku $O(logn).$

B-stabla

B-stablo je generalizacija binarnog stabla pretrage, pa stablo može da ima promenljiv broj podstabala iz svakog čvora. Potomci u stablu imaju unapred definisan opseg, oni neće obavezno biti ispunjeni podacima, što znači B-stablo može potencijalno da gubi malo prostora. Prednost je u tome što B-stablo nije potrebno da se uravnotežuje onoliko često koliko to zahtevaju ostali načini balansiranja drveta.

Zbog promenljivog raspona broja potomaka, B-stabla su optimizovana za sisteme koji čitaju velike blokove podataka. Koriste se i u bazama podataka.

Vremenska složenost za pretragu u B-stablu je $O(logn)$

(a, b)-stablo pretrage

(a, b)-stablo je struktura u kojoj su svi njeni listovi na istoj dubini. Svaki čvor ima najmanje a-potomaka i najviše b-potomaka, dok koren ima najmanje 2 potomka, a najviše b-potomaka.

a i b može odlučivati sledećom formulom:^[2]

$2\leq a\leq {\frac {(b+1)}{2}}$

Vremenska složenost pretrage (a, b)-stabla je $O(logn)$

Ternarno stablo pretrage

Ternarno stablo pretrage je tip stabla koje ima 3 čvora: manjeg sina, istog sina i većeg sina. Svaki čvor čuva jedan znak i samo stablo je u redosledu kao i binarno stablo pretrage, samo je izuzetak mogućnost trećeg čvora.

Pretraga ternarnog stabla pretrage obuhvata prebacivanje u nisku radi testiranja da li put sadrži traženi ključ. Vremenska složenost pretrage je $O(logn)$

Algoritmi za pretragu

Pretraga vrednosti

Pod pretpostavkom da je drvo uravnoteženo, osoba može uzeti ključ i pokušati da ga locira u drvetu. Sledeći algoritmi su univerzalni za binarne pretrage stabla, ali ista ideja može da se primeni i na stabla drugih formata.

Pseudokodovi za pronalazak ključa implementirani na rekurzivni i iterativni način:

Rekurzivna implementacija

search-recursive(key, node)
    if node is NULL
        return EMPTY_TREE
    if key < node.key
        return search-recursive(key, node.left)
    else if key > node.key
        return search-recursive(key, node.right)
    else
        return node

Iterativna implementacija

searchIterative(key, node)
    currentNode := node
    while currentNode is not NULL
        if currentNode.key = key
            return currentNode
        else if currentNode.key < key
            currentNode := currentNode.left
        else
            currentNode := currentNode.right

Pretraga najmanjeg i najvećeg elementa

U sortiranom stablu, namanji element je list koji se nalazi skroz levo, a najveći element je list koji se nalazi skroz desno.^[3]

Pseudokodovi za nalazak najmanjeg i najvećeg elementa:

Pretraga najmanjeg

findMinimum(node)
    if node is NULL
        return EMPTY_TREE
    min := node
    while min.left is not NULL
        min := min.left
    return min.key

Pretraga najvećeg

findMaximum(node)
    if node is NULL
        return EMPTY_TREE
    max := node
    while max.right is not NULL
        max := max.right
    return max.key

Vidi još

Reference

^ Black, Paul and Pieterse, Vreda (2005). „search tree”. Dictionary of Algorithms and Data Structures
^ Toal, Ray. „(a, b) Trees”
^ Gildea, Dan (2004). „Binary Search Tree”

[1] Black, Paul and Pieterse, Vreda (2005). „search tree”. Dictionary of Algorithms and Data Structures

[2] Toal, Ray. „(a, b) Trees”

[3] Gildea, Dan (2004). „Binary Search Tree”

[1]

[2]

[3]