Binarno stablo pretraživanja - strukturirana baza podataka koja sadrži čvorove, dvije veze na druge čvorove, desno i lijevo. Čvorovi su objekt klase koji ima podatke, a NULL je znak koji označava kraj stabla.
Često se naziva BST, što ima posebno svojstvo: čvorovi veći od korijena nalaze se desno od njega, a manji lijevo.
Opća teorija i terminologija
U binarnom stablu pretraživanja, svaki čvor, isključujući korijen, povezan je usmjerenim rubom od jednog čvora do drugog, koji se naziva roditelj. Svaki od njih može se povezati s proizvoljnim brojem čvorova, koji se nazivaju djeca. Čvorovi bez "djece" nazivaju se listovima (vanjski čvorovi). Elementi koji nisu listovi nazivaju se unutarnjim. Čvorovi s istim roditeljem su braća i sestre. Najviši čvor naziva se korijen. U BST-u, dodijelite element svakom čvoru i provjerite ima li za njih postavljeno posebno svojstvo.
Terminologija stabla:
- Dubina čvora je broj rubova definiranih od korijena do njega.
- Visina čvora je broj rubova definiranih od njega do najdubljeg lista.
- Visina stabla određena je visinom korijena.
- Binarni stablo pretraživanja je poseban dizajn, pruža najbolji omjer visine i broja čvorova.
- Visina h s N čvorova najviše O (log N).
To možete lako dokazati prebrojavanjem čvorova na svakoj razini, počevši od korijena, pod pretpostavkom da sadrži najveći broj njih: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Rješavanje ovoga za h daje h=O (log n).
Prednosti drva:
- Odražavaju strukturne odnose podataka.
- Koristi se za predstavljanje hijerarhija.
- Osigurajte učinkovitu instalaciju i pretraživanje.
- Stabla su vrlo fleksibilni podaci koji vam omogućuju premještanje podstabala uz minimalan napor.
Način pretraživanja
Općenito, da biste utvrdili nalazi li se vrijednost u BST-u, pokrenite binarno stablo pretraživanja u njegovom korijenu i odredite ispunjava li zahtjeve:
- budi u korijenu;
- biti u lijevom podstablu korijena;
- u desnom podstablu korijena.
Ako nijedan osnovni registar nije zadovoljen, vrši se rekurzivno pretraživanje u odgovarajućem podstablu. Zapravo postoje dvije osnovne opcije:
- Stablo je prazno - vrati false.
- Vrijednost je u korijenskom čvoru - vrati true.
Treba napomenuti da stablo binarnog pretraživanja s razvijenom shemom uvijek počinje tražiti duž putanje od korijena do lista. U najgorem slučaju ide sve do lista. Stoga je najgore vrijeme proporcionalno duljini najdužeg puta od korijena do lista, što je visina stabla. Općenito, ovo je kada trebate znati koliko je vremena potrebno za traženje u funkciji broja vrijednosti pohranjenih u stablu.
Drugim riječima, postoji odnos između broja čvorova u BST-u i visine stabla, ovisno o njegovom "oblici". U najgorem slučaju, čvorovi imaju samo jedno dijete, a uravnoteženo stablo binarnog pretraživanja u biti je povezana lista. Na primjer:
50
/
10
15
30
/
20
Ovo stablo ima 5 čvorova i visinu=5. Pronalaženje vrijednosti u rasponu 16-19 i 21-29 zahtijevat će sljedeći put od korijena do lista (čvor koji sadrži vrijednost 20), tj., trebat će vrijeme proporcionalno broju čvorova. U najboljem slučaju, svi imaju dvoje djece, a listovi se nalaze na istoj dubini.
Ovo stablo binarnog pretraživanja ima 7 čvorova i visinu=3. Općenito, stablo poput ovog (puno stablo) imat će visinu od približno log 2 (N), gdje je N broj čvorova u stablu. Vrijednost log 2 (N) je broj puta (2) da se N može podijeliti prije nego što se postigne nula.
Sažimanje: najgore vrijeme potrebno za pretraživanje u BST-u je O (visina stabla). Najgore "linearno" stablo je O(N), gdje je N broj čvorova u stablu. U najboljem slučaju, "potpuno" stablo je O(log N).
BST binarni umetak
Pitam se gdje bi trebao bitinovi čvor se nalazi u BST-u, morate razumjeti logiku, mora se postaviti tamo gdje ga korisnik pronađe. Osim toga, morate zapamtiti pravila:
- Duplikati nisu dopušteni, pokušaj umetanja duplicirane vrijednosti dovest će do iznimke.
- Javna metoda umetanja koristi pomoćnu rekurzivnu "pomoćnu" metodu za stvarno umetanje.
- Čvor koji sadrži novu vrijednost uvijek se umeće kao list u BST.
- Javna metoda umetanja vraća void, ali pomoćna metoda vraća BSTnode. To čini kako bi obradio slučaj kada je čvor koji mu je proslijeđen null.
Općenito, pomoćna metoda pokazuje da ako je izvorno stablo binarnog pretraživanja prazno, rezultat je stablo s jednim čvorom. Inače će rezultat biti pokazivač na isti čvor koji je proslijeđen kao argument.
Brisanje u binarnom algoritmu
Kao što možete očekivati, brisanje elementa uključuje pronalaženje čvora koji sadrži vrijednost koju treba ukloniti. Postoji nekoliko stvari u ovom kodu:
- BST koristi pomoćnu, preopterećenu metodu brisanja. Ako element koji tražite nije u stablu, tada će pomoćna metoda na kraju biti pozvana s n==null. To se ne smatra pogreškom, stablo se u ovom slučaju jednostavno ne mijenja. Pomoćna metoda za brisanje vraća vrijednost - pokazivač na ažurirano stablo.
- Kada se list ukloni, uklanjanje iz stabla binarnog pretraživanja postavlja odgovarajući podređeni pokazivač svog roditelja na null, ili korijen na null ako je onaj koji se uklanjačvor je korijen i nema djece.
- Napominjemo da poziv brisanja mora biti jedan od sljedećih: root=delete (root, ključ), n.setLeft (izbriši (n.getLeft (), ključ)), n.setRight (delete(n. getRight(), ključ)). Dakle, u sva tri slučaja ispravno je da metoda delete jednostavno vraća null.
- Kada potraga za čvorom koji sadrži vrijednost za brisanje uspije, postoje tri opcije: čvor za brisanje je list (nema djece), čvor za brisanje ima jedno dijete, ima dva djeca.
- Kada čvor koji se uklanja ima jedno dijete, možete ga jednostavno zamijeniti podređenim, vraćajući mu pokazivač.
- Ako čvor koji treba izbrisati ima nula ili 1 djece, tada će metoda brisanja "pratiti put" od korijena do tog čvora. Dakle, najgore vrijeme je proporcionalno visini stabla, i za pretraživanje i za umetanje.
Ako čvor koji treba ukloniti ima dvoje djece, poduzimaju se sljedeći koraci:
- Pronađi čvor koji treba izbrisati, prateći put od korijena do njega.
- Pronađi najmanju vrijednost v u desnom podstablu, nastavljajući stazom do lista.
- Rekurzivno uklonite vrijednost v, slijedite isti put kao u koraku 2.
- Tako se u najgorem slučaju put od korijena do lista izvodi dvaput.
Red prijelaza
Traversal je proces koji posjećuje sve čvorove u stablu. Budući da je C binarno stablo pretraživanja nelinearna struktura podataka, ne postoji jedinstveno prelaženje. Na primjer, ponekad nekoliko algoritama prelaskagrupiran u sljedeće dvije vrste:
- dubina prijelaza;
- prvi prolaz.
Postoji samo jedna vrsta križanja širine - zaobilaženje razine. Ovaj prijelaz posjećuje čvorove na razini dolje i lijevo, gore i desno.
Postoje tri različite vrste prijelaza dubine:
- Prolaz prednarudžbe - prvo posjetite roditelja, a zatim lijevo i desno dijete.
- Prolaz u redu - posjet lijevom djetetu, zatim roditelju i desnom djetetu.
- Poslije narudžbe - posjet lijevom djetetu, zatim desnom djetetu, pa roditelju.
Primjer za četiri obilaska binarnog stabla pretraživanja:
- Prednarudžba - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- Narudžba - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- Narudžba - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- Narudžba razine - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Slika prikazuje redoslijed posjećivanja čvorova. Broj 1 je prvi čvor u određenom obilasku, a 7 je posljednji čvor.
Ova opća putovanja mogu se predstaviti kao jedan algoritam, uz pretpostavku da se svaki čvor posjeti tri puta. Eulerov obilazak je šetnja oko binarnog stabla gdje se svaki rub tretira kao zid koji korisnik ne može prijeći. U ovoj šetnji, svaki čvor će biti posjećen ili s lijeve, ili ispod, ili s desne strane. Eulerov obilazak, koji posjećuje čvorove s lijeve strane, uzrokuje zaobilaženje prijedloga. Kada se posjećuju donji čvorovi, oni se prelaze redom. A kada se posjećuju čvorovi s desne strane - dobitizaobići korak po korak.
Navigacija i otklanjanje pogrešaka
Da biste olakšali navigaciju stablom, stvorite funkcije koje prvo provjeravaju jesu li lijevo ili desno dijete. Za promjenu položaja čvora, mora postojati lak pristup pokazivaču na roditeljskom čvoru. Ispravna implementacija stabla je vrlo teška, stoga morate znati i primijeniti procese otklanjanja pogrešaka. Binarno stablo pretraživanja s implementacijom često ima pokazivače koji zapravo ne pokazuju smjer putovanja.
Da bi se sve ovo shvatilo, koristi se funkcija koja provjerava može li stablo biti ispravno i pomaže pronaći mnoge pogreške. Na primjer, provjerava je li roditeljski čvor podređeni čvor. Uz assert(is_wellformed(root)) mnoge pogreške mogu biti uhvaćene prerano. Koristeći nekoliko zadanih prijelomnih točaka unutar ove funkcije, također možete točno odrediti koji je pokazivač pogrešan.
Function Konsolenausgabe
Ova funkcija ispire cijelo stablo na konzolu i stoga je vrlo korisna. Redoslijed kojim se cilj izlaznog stabla izvršava je:
- Da biste to učinili, prvo morate odrediti koje će informacije biti izlazne kroz čvor.
- A također morate znati koliko je drvo široko i visoko da biste uzeli u obzir koliko prostora treba ostaviti.
- Sljedeće funkcije izračunavaju ove informacije za stablo i svako podstablo. Budući da u konzolu možete pisati samo red po redak, također ćete morati ispisati stablo red po redak.
- Sada nam treba drugi način za povlačenjecijelo stablo, ne samo redak po red.
- Uz pomoć dump funkcije, možete čitati stablo i značajno poboljšati izlazni algoritam, što se brzine tiče.
Međutim, ovu funkciju će biti teško koristiti na velikim stablima.
Kopiraj konstruktor i destruktor
Budući da stablo nije trivijalna struktura podataka, bolje je implementirati konstruktor kopiranja, destruktor i operator dodjele. Destruktor je lako implementirati rekurzivno. Za vrlo velika stabla može podnijeti "preljev hrpe". U ovom slučaju, formulira se iterativno. Ideja je ukloniti list koji predstavlja najmanju vrijednost od svih listova, dakle na lijevoj strani stabla. Odsijecanjem prvih listova stvaraju se novi, a stablo se smanjuje sve dok konačno ne prestane postojati.
Konstruktor kopiranja također se može implementirati rekurzivno, ali budite oprezni ako se pojavi iznimka. Inače, stablo brzo postaje zbunjujuće i sklono pogreškama. Zato se preferira iterativna verzija. Ideja je proći kroz staro i novo stablo, kao što biste to učinili u destruktoru, klonirajući sve čvorove koji su u starom stablu, ali ne i nove.
S ovom metodom, implementacija binarnog stabla pretraživanja uvijek je u zdravom stanju i može je ukloniti destruktor čak iu nekompletnom stanju. Ako se dogodi iznimka, sve što trebate učiniti je uputiti destruktoru da izbriše polugotovo stablo. operator dodjelemože se jednostavno implementirati pomoću Copy & Swap.
Izrada binarnog stabla pretraživanja
Optimalna stabla binarnog pretraživanja nevjerojatno su učinkovita ako se njima pravilno upravlja. Neka pravila za stabla binarnog pretraživanja:
- Matični čvor ima najviše 2 podređena čvora.
- Lijevi podređeni čvor je uvijek manji od roditeljskog čvora.
- Valjani podređeni čvor je uvijek veći ili jednak roditeljskom čvoru.
Niz koji će se koristiti za izgradnju binarnog stabla pretraživanja:
- Osnovni cjelobrojni niz od sedam vrijednosti u nerazvrstanom redoslijedu.
- Prva vrijednost u nizu je 10, tako da je prvi korak u izgradnji stabla stvaranje korijenskog čvora od 10, kao što je prikazano ovdje.
- Sa skupom korijenskih čvorova, sve ostale vrijednosti bit će podređene ovom čvoru. Pozivajući se na pravila, prvi korak koji treba poduzeti da dodate 7 stablu jest usporediti ga s korijenskim čvorom.
- Ako je vrijednost 7 manja od 10, postat će lijevi podređeni čvor.
- Ako je vrijednost 7 veća ili jednaka 10, pomaknut će se udesno. Budući da je poznato da je 7 manje od 10, označava se kao lijevi podređeni čvor.
- Rekurzivno izvodite usporedbe za svaki element.
- Slijedeći isti uzorak, izvršite istu usporedbu s 14. vrijednošću u nizu.
- Uspoređivanje vrijednosti 14 s korijenskim čvorom 10, znajući da je 14 ispravno dijete.
- Šetajući nizom,dođi do 20.
- Počnite usporedbom niza s 10, ovisno o tome što je veće. Dakle, pomaknite se udesno i usporedite to s 14, on ima više od 14 godina i nema djece s desne strane.
- Sada postoji vrijednost 1. Slijedeći isti obrazac kao i ostale vrijednosti, usporedite 1 sa 10, pomičući se ulijevo i uspoređujući sa 7 i konačno s 1 lijevim podređenim 7. čvorom.
- Ako je vrijednost 5, usporedite je s 10. Budući da je 5 manje od 10, prijeđite ulijevo i usporedite sa 7.
- Znajući da je 5 manje od 7, nastavite niz stablo i usporedite 5 s vrijednošću 1.
- Ako 1 nema djece i 5 je veće od 1, tada je 5 valjano dijete 1 čvora.
- Konačno umetnite vrijednost 8 u stablo.
- Kada je 8 manje od 10, pomaknite ga ulijevo i usporedite sa 7, 8 je veće od 7, pa ga pomaknite udesno i dovršite stablo, čineći 8 pravim podređenim 7.
Dobivanje i procjena jednostavne elegancije optimalnih stabala binarnog pretraživanja. Kao i mnoge teme u programiranju, snaga binarnih stabala pretraživanja proizlazi iz njihove sposobnosti razrješavanja podataka u male, povezane komponente. Od sada možete raditi s cijelim skupom podataka na organiziran način.
Potencijalni problemi binarnog pretraživanja
Binarna stabla pretraživanja su sjajna, ali treba imati na umu nekoliko upozorenja. Obično su učinkoviti samo ako su uravnoteženi. Uravnoteženo stablo je drvo u kojemrazlika između visina podstabala bilo kojeg čvora u stablu je najviše jedan. Pogledajmo primjer koji bi mogao pomoći razjasniti pravila. Zamislimo da polje počinje kao sortiranje.
Ako pokušate pokrenuti algoritam binarnog stabla pretraživanja na ovom stablu, on će raditi točno kao da se samo ponavlja kroz niz dok se ne pronađe željena vrijednost. Moć binarnog pretraživanja leži u mogućnosti brzog filtriranja neželjenih vrijednosti. Kada stablo nije uravnoteženo, ono neće pružiti iste prednosti kao uravnoteženo stablo.
Vrlo je važno ispitati podatke s kojima korisnik radi prilikom izrade binarnog stabla pretraživanja. Možete integrirati rutine kao što je randomizacija niza prije implementacije binarnog stabla pretraživanja cijelih brojeva kako biste ga uravnotežili.
Primjeri izračuna binarnog pretraživanja
Moramo odrediti kakvo će stablo rezultirati ako se 25 umetne u sljedeće binarno stablo pretraživanja:
10
/
/
5 15
/ /
/ /
2 12 20
Kada umetnete x u stablo T koje još ne sadrži x, ključ x uvijek se stavlja u novi list. U vezi s tim, novo stablo će izgledati ovako:
10
/
/
5 15
/ /
/ /
2 12 20
25
Koju biste vrstu stabla dobili da umetnete 7 u sljedeće stablo binarnog pretraživanja?
10
/
/
5 15
/ /
/ /
2 12 20
Odgovor:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
Binarno stablo pretraživanja može se koristiti za pohranu bilo kojeg objekta. Prednost korištenja binarnog stabla pretraživanja umjesto povezanog popisa je u tome što ako je stablo razumno uravnoteženo i više liči na "puno" nego na "linearno" stablo, umetanje, pretraživanje i sve operacije brisanja mogu se implementirati da se izvode u O(log N) vrijeme.
