B-stablo

Izvor: Vidipedija
Skoči na: orijentacija, traži

POTPUNO BINARNO STABLO

Kada se binarno stablo realizira preko polja novi član jednostavno se doda na kraj polja te se zatim primjeni operacija uređaja tako da stablo i nakon dodavanja ostane onakvo kakvo želimo. Primjer ovoga radi se na predavanjima iz Algoritama i struktura podataka kada se obrađuje struktura zvana gomila. No postavlja se pitanje kako saznati kamo član treba ubaciti ako se stablo radi kao dinamička struktura. Ili još jednostavnije pitanje: dam vam pokazivač na glavu binarnog stabla, i želim da mi ispišete n-ti član tog stabla, uz pretpostavku da je stablo potpuno.

MOGUĆE RIJEŠENJE: BINARNI BROJEVNI SUSTAV (osobni osvrt autora)

Razmišljajući o ovom problemu dosjetio sam se da slične probleme (ili zakonitosti, kako želite) muče i binarni brojevni sustav. Naime, poznato vam je da tamo postoji sam 0 i 1. Lijevo i desno. 0 i 1.... Ma sigurno ima neke logike. I moram se pohvaliti da sam logiku i pronašao. Evo o čemu se radi. Recimo da želimo pronaći stazu do člana broj 11 potpunog binarnog stabla. U tu svrhu potrebno je broj 11 prvo pretvoriti u binarni broj. Postupak možete vidjeti na donjoj sličici. Skračemo bismo mogli pisati i ovako: 11 = 8 + 2 + 1 tj. binarno %1011 (oznaku % koristiti ću u nastavku za označavanje binarnih brojeva). Iz ovog broja se još ne vidi kako do traženog čvora. Ono što je potrebno jest najprije odbaciti vodeću znamenku. Odbacivanjem od broja %1011 dobijemo broj %011. I odmah jedno upozorenje. Ne odbacujte vodeće nule! Trebati će nam. Nadalje prihvatimo jedan dogovor. Ako je znamenka 0, kretati ćemo se lijevo, ako je znamenka 1 kretati ćemo se desno. Pa da vidimo. Rekli smo da želimo doći do jedanaestoga člana stabla. Jedanaest smo pretvorili u binarno %1011 i odbacili smo vodeću znamenku te nam je ostalo %011. Krenimo sada od glave stabla i primjenjujmo pravilo na preostale znamenke, od prve (sa lijeve strane) do zadnje. Čitamo redom: 0 pa se od 1 krećemo lijevo na 2, zatim 1 pa se krećemo desno na 5, i konačno 1 pa se krećemo desno na 11.