Binarno stablo niti

Definicija binarnog stabla niti glasi:

"Binarno stablo pretrage zovemo Binarno stablo niti ako svaki pokazivač na desno dete koji bi inače bio NULL pokazuje na sledbenika datog čvora, a svaki pokazivač na levo dete koji bi inače bio NULL pokazuje na prethodnika datog čvora."

Binarno stablo niti omogućuje obilazak čvorova u binarnom stablu linearnom putanjom koja je kraća nego rekurzivni obilazak. Takođe je moguće otkriti roditelja čvora u binarnom stablu niti, bez upotreba pokazivača na roditelja ili steka. To može biti korisno kada je veličina steka ograničena, ili kada su pokazivači na roditelja nedostupni (pri traženju roditelja korišćenjem pretrage u dubinu).

Da bi se videlo kako je ovo moguće, uzme se u obzir čvor k koji ima desno dete r. Tada levi pokazivač od r mora ili pokazivati ka detetu ili nazad prema k. U slučaju da r ima levo dete, to dete mora ili imati levo dete ili imati pokazivač prema k, i tako dalje za svako naredno levo dete. To znači da prateći lanac levih pokazivača iz r, u jednom trenutku nailazim na pokazivač koji vodi nazad do k. Imamo simetričnu situaciju ako je q levo dete od p, tada pratimo desnu decu od q , dok ne dođemo do pokazivača koji vodi nazad do p.

Tipovi binarnih stabala niti

1. Binarnih stabla sa jednostrukim nitima: svaki čvor ima niti ili ka prethodniku ili ka sledbeniku.
2. Binarnih stabla sa dvostrukim nitima: svaki čvor ima niti i ka prethodniku i ka sledbeniku.

U Pajtonu:

def parent(node):
    if node is node.tree.root:
        return None
    else:
        x = node
        y = node
        while True:
            if is_thread(y.right):
                p = y.right
                if p is None or p.left is not node:
                    p = x
                    while not is_thread(p.left):
                        p = p.left
                    p = p.left
                return p
            elif is_thread(x.left):
                p = x.left
                if p is None or p.right is not node:
                    p = y
                    while not is_thread(p.right):
                        p = p.right
                    p = p.right
                return p
            x = x.left
            y = y.right

Inorder obilazak

Niti su veze do prethodnika i sledbenika sudeći po inorder obilasku.

Inorder obilazak stabla je ABCDEFGHI, prethodnik od E je D, a sledbenik od E je F.

Primer

Postupak formiranja stabla niti od običnog binarnog stabla:

Inorder obilazak datog stabla je D B A E C. Iz toga sledi da će odgovarajuće binarno stablo niti biti:

Nerekurzivni inorder obilazak binarnog stabla niti

Pošto je ovo nerekurzivna metoda obilaska, ona mora imati iterativnu proceduru; što znači, svaki korak u obilasku čvora mora biti u petlji da bi se isti primenio za svaki čvor u stablu. Posmatraćemo inorder obilazak. U tom slučaju, za svaki čvor, posetićemo levo podstablo (ako ono postoji) prvo (ako ga nismo posetili ranije); onda ćemo posetiti (u našem slučaju ispisati njegovu vrednost) samog čvora i na kraju desno podstablo (ako ono postoji). Ako desno podstablo ne postoji, proveravamo da li postoji nit ka nekom čvoru i ako postoji onda razmatramo taj čvor. Sledeći primer ilustruje dati algoritam.

Algoritam

Korak-1: Za trenutni čvor proveriti da li ima levo dete koje se ne nalazi na listi posećenih. Ako ima prelazi se na korak-2, inače na korak-3.

Korak-2: To levo dete se dodaje na listu posećenih čvorova i uzima se za dalje razmatranje. Prelazi se na korak-6.

Korak-3: Za trenutni čvor se proveri da li ima desno dete. Ako ima, prelazi se na korak-4, inače na korak-5.

Korak-4: To desno dete se uzima za dalje razmatranje. Prelazi se na korak-6.

Korak-5: Proverava se da li postoji nit ka nekom čvoru i ako postoji onda se razmatra taj čvor.

Korak-6: Prelazi se na korak-1 ako nisu svi čvorovi obiđeni, inače kraj.

		Li
Korak-1	'A' ima levo dete B, koje nije posećeno. Zato, smeštamo B u „listu posećenih čvorova“ i B se dalje razmatra.	B
Korak-2	'B' takođe ima levo dete, 'D', koje nije na listi posećenih čvorova. Zato, smeštamo 'D' u tu listu i dalje ga razmatramo.	B D
Korak-3	'D' nema levo dete, pa ispisujemo 'D'. Onda proveravamo da li ima desno dete. 'D' nema desno dete pa onda tražimo nit koja ide iz njega. Nit ide ka 'B'. Zato, dalje razmatramo 'B'.	B D	D
Korak-4	'B' svakako ima levo dete ali se ono već nalazi na listi posećenih čvorova. Zato, ispisujemo 'B'. Onda tražimo njegovo desno dete ali ono ne postoji. Zato, dalje razmatramo 'A' jer prema njemu ide nit.	B D	D B
Korak-5	'A' ima levo dete, 'B', ali ono je već na listi posećenih čvorova. Zato, ispisujemo 'A'. Proveramo da li ima desno dete. 'A' ima desno dete, 'C' koje nije na listi posećenih čvorova. Zato, dodajemo ga na tu listu i dalje ga razmatramo.	B D C	D B A
Korak-6	'C' ima levo dete 'E' koje nije na listi posećenih čvorova. Zato ga dodajemo na tu listu i dalje razmatramo.	B D C E	D B A
Korak-7		i konačno.....	D B A E C

Spoljašnje veze

• Tutorial on threaded binary trees
• GNU libavl 2.0.2, Section on threaded binary search trees