Implementacija binarnog stabla pretraživanja

2024 Autor: Angel Austin | [email protected]. Zadnja izmjena: 2023-12-17 05:19

Binarni stablo pretraživanja - strukturirana baza podataka koja sadrži čvorove, dvije veze ka drugim čvorovima, 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 usmjerenom ivicom od jednog čvora do drugog, koji se naziva roditelj. Svaki od njih može biti povezan sa proizvoljnim brojem čvorova, koji se nazivaju djeca. Čvorovi bez "djece" nazivaju se listovi (spoljni čvorovi). Elementi koji nisu listovi nazivaju se unutrašnjim. Čvorovi sa istim roditeljem su braća i sestre. Najviši čvor se naziva korijen. U BST-u, dodijelite element svakom čvoru i provjerite ima li za njih postavljeno posebno svojstvo.

Terminologija stabla:

Dubina čvora je broj ivica definiranih od korijena do njega.
Visina čvora je broj ivica definisanih od njega do najdubljeg lista.
Visina stabla je određena visinom korijena.
Binarni stablo pretraživanja je poseban dizajn, pruža najbolji omjer visine i broja čvorova.
Visina h sa N čvorova najviše O (log N).

To možete lako dokazati prebrojavanjem čvorova na svakom nivou, 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 drveta:

Odražavaju strukturalne odnose podataka.
Koristi se za predstavljanje hijerarhija.
Osigurajte efikasnu instalaciju i pretragu.
Stabla su veoma fleksibilni podaci, omogućavajući vam da pomerate podstabla uz minimalan napor.

Način pretraživanja

Uopšteno govoreći, da biste utvrdili da li je vrijednost u BST-u, pokrenite binarno stablo pretraživanja u njegovom korijenu i odredite da li ispunjava zahtjeve:

budi u korijenu;
biti u lijevom podstablu korijena;
u desnom podstablu korijena.

Ako nijedan osnovni registar nije zadovoljen, vrši se rekurzivna pretraga 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 sa razvijenom šemom uvijek počinje da traži duž putanje od korijena do lista. U najgorem slučaju, ide sve do lista. Stoga je najgore vrijeme proporcionalno dužini najdužeg puta od korijena do lista, što je visina drveta. Općenito, ovo je kada trebate znati koliko dugo je potrebno da se potraži 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 binarno stablo pretraživanja je u suštini povezana lista. Na primjer:

Ovo stablo ima 5 čvorova i visinu=5. Pronalaženje vrijednosti u rasponu 16-19 i 21-29 će zahtijevati sljedeću putanju od korijena do lista (čvor koji sadrži vrijednost 20), tj., biće potrebno vrijeme proporcionalno broju čvorova. U najboljem slučaju, svi imaju po 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) koji se N može podijeliti prije nego što se dostigne nula.

Rezimiranje: najgore vrijeme potrebno za pretragu 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 dozvoljeni, pokušaj umetanja duplirane vrijednosti će izazvati izuzetak.
Javna metoda umetanja koristi pomoćnu rekurzivnu "pomoćnu" metodu za stvarno umetanje.
Čvor koji sadrži novu vrijednost uvijek je umetnut kao list u BST.
Javna metoda umetanja vraća void, ali pomoćna metoda vraća BSTnode. To radi kako bi obradio slučaj kada je čvor koji mu je proslijeđen null.

Uopšteno govoreći, pomoćna metoda pokazuje da ako je originalno stablo binarnog pretraživanja prazno, rezultat je stablo sa jednim čvorom. U suprotnom, rezultat će 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, onda će pomoćna metoda na kraju biti pozvana sa n==null. Ovo se ne smatra greš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 binarnog stabla pretraživanja postavlja odgovarajući podređeni pokazivač njegovog roditelja na null, ili korijen na null ako je onaj koji se uklanjačvor je korijenski i nema djece.
Imajte na umu 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 je tačno da metoda delete jednostavno vraća null.
Kada potraga za čvorom koji sadrži vrijednost za brisanje uspije, postoje tri opcije: čvor koji treba obrisati je list (nema djece), čvor koji treba obrisati ima jedno dijete, ima dva djeca.
Kada čvor koji se uklanja ima jedno dijete, možete ga jednostavno zamijeniti podređenim, vraćajući pokazivač djetetu.
Ako čvor koji treba obrisati ima nula ili 1 djece, tada će metoda brisanja "pratiti putanju" 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 obrisati, prateći putanju 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.
Dakle, u najgorem slučaju, put od korijena do lista se izvodi dva puta.

Red traverza

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ća dva tipa:

dubina prelaza;
prvi prolaz.

Postoji samo jedna vrsta prelaska širine - zaobilaženje nivoa. Ovaj prelazak posjećuje čvorove nivoe dolje i lijevo, gore i desno.

Postoje tri različite vrste dubinskih prelaza:

Prolaz prednarudžbe - prvo posjetite roditelja, a zatim lijevo i desno dijete.
Prelazak u red - posjeta lijevom djetetu, zatim roditelju i desnom djetetu.
Prošlo narudžbu - posjeta lijevom djetetu, zatim desnom djetetu, pa roditelju.

Primjer za četiri obilaska binarnog stabla pretraživanja:

Prethodna narudžba - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
U redu - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
Narudžba - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
Narudžba nivoa - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Slika pokazuje redoslijed posjećivanja čvorova. Broj 1 je prvi čvor u određenom obilasku, a 7 je posljednji čvor.

Ova opšta obilaženja mogu se predstaviti kao jedan algoritam, pod pretpostavkom da se svaki čvor posjeti tri puta. Ojlerova tura je šetnja oko binarnog stabla gdje se svaka ivica tretira kao zid koji korisnik ne može prijeći. U ovoj šetnji, svaki čvor će biti posjećen ili lijevo, ili dolje, ili desno. Ojlerov obilazak, koji posjećuje čvorove na lijevoj strani, uzrokuje da se zaobiđe prijedlog. Kada se posjećuju donji čvorovi, oni se prelaze redom. A kada se posjećuju čvorovi sa desne strane - getzaobići korak po korak.

Navigacija i otklanjanje grešaka

Da biste olakšali navigaciju po stablu, kreirajte funkcije koje prvo provjeravaju da li su lijevo ili desno dijete. Da biste promijenili poziciju čvora, mora postojati lak pristup pokazivaču na roditeljskom čvoru. Ispravna implementacija stabla je vrlo teška, tako da morate znati i primijeniti procese otklanjanja grešaka. Binarno stablo pretraživanja sa implementacijom često ima pokazivače koji zapravo ne pokazuju smjer putovanja.

Da bi se sve ovo shvatilo, koristi se funkcija koja provjerava da li stablo može biti ispravno i pomaže u pronalaženju mnogih grešaka. Na primjer, provjerava da li je roditeljski čvor podređeni čvor. Sa assert(is_wellformed(root)) mnoge greške mogu biti uhvaćene prerano. Koristeći nekoliko datih tačaka prekida unutar ove funkcije, također možete odrediti tačno koji pokazivač je pogrešan.

Function Konsolenausgabe

Ova funkcija ispire cijelo stablo u konzolu i stoga je vrlo korisna. Redoslijed kojim se izvršava cilj izlaznog stabla je:

Da biste to uradili, prvo morate odrediti koje informacije će biti izlazne kroz čvor.
A takođe 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. Pošto u konzolu možete pisati samo red po red, takođe ćete morati da štampate stablo red po red.
Sada nam treba drugi način za povlačenjecijelo drvo, ne samo red 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 drvo nije trivijalna struktura podataka, bolje je implementirati konstruktor kopiranja, destruktor i operator dodjeljivanja. Destruktor je lako implementirati rekurzivno. Za vrlo velika stabla, može podnijeti "prelijevanje hrpe". U ovom slučaju, formulira se iterativno. Ideja je da se ukloni list koji predstavlja najmanju vrijednost od svih listova, tako da se nalazi na lijevoj strani drveta. Odsijecanjem prvih listova stvaraju se novi, a drvo se smanjuje sve dok konačno ne prestane postojati.

Konstruktor kopiranja se također može implementirati rekurzivno, ali budite oprezni ako se pojavi izuzetak. U suprotnom, stablo brzo postaje zbunjujuće i sklono greškama. Zato se preferira iterativna verzija. Ideja je da prođete kroz staro i novo stablo, kao što biste uradili u destruktoru, klonirajući sve čvorove koji su u starom stablu, ali ne i nove.

Sa ovom metodom, implementacija stabla binarnog pretraživanja je uvijek u zdravom stanju i može je ukloniti destruktor čak iu nekompletnom stanju. Ako se dogodi izuzetak, sve što trebate učiniti je uputiti destruktoru da izbriše polugotovo stablo. operator dodjeljivanjamože se lako implementirati pomoću Copy & Swap.

Kreiranje binarnog stabla pretrage

Optimalna stabla binarnog pretraživanja su nevjerovatno efikasna 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.
Važeći 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 nesortiranom redoslijedu.
Prva vrijednost u nizu je 10, tako da je prvi korak u izgradnji stabla kreiranje korijenskog čvora od 10, kao što je prikazano ovdje.
Sa skupom korijenskih čvorova, sve ostale vrijednosti će biti potomci ovog čvora. Pozivajući se na pravila, prvi korak koji treba preduzeti da dodate 7 stablu je da ga uporedite sa korijenskim čvorom.
Ako je vrijednost 7 manja od 10, postat će lijevi podređeni čvor.
Ako je vrijednost 7 veća ili jednaka 10, pomjerit će se udesno. Pošto je poznato da je 7 manje od 10, on je označen kao lijevi podređeni čvor.
Rekurzivno izvršite poređenja za svaki element.
Pratite isti obrazac, izvršite isto poređenje sa 14. vrijednošću u nizu.
Upoređivanje vrijednosti 14 sa korijenskim čvorom 10, znajući da je 14 ispravno dijete.
Šetajući kroz niz,dođi do 20.
Počnite upoređivanjem niza sa 10, koji god je veći. Zato se pomeri desno i uporedi sa 14, on ima preko 14 godina i nema dece desno.
Sada postoji vrijednost 1. Prateći isti obrazac kao i ostale vrijednosti, uporedite 1 sa 10, pomjerite se ulijevo i uporedite sa 7 i konačno sa 1 lijevim podređenim 7. čvorom.
Ako je vrijednost 5, uporedite je sa 10. Pošto je 5 manje od 10, prijeđite na lijevo i uporedite sa 7.
Znajući da je 5 manje od 7, nastavite niz stablo i uporedite 5 sa 1 vrijednošću.
Ako 1 nema djece i 5 je veće od 1, tada je 5 valjano dijete od 1 čvora.
Konačno umetnite vrijednost 8 u stablo.
Kada je 8 manje od 10, pomerite ga ulevo i uporedite sa 7, 8 je veće od 7, pa ga pomerite udesno i dovršite stablo, čineći 8 pravim detetom od 7.

Dobijanje i procena jednostavne elegancije optimalnog binarnog stabla pretrage. Kao i mnoge teme u programiranju, moć binarnih stabala pretraživanja dolazi iz njihove sposobnosti da razlože podatke u male, povezane komponente. Od sada, možete raditi s punim skupom podataka na organiziran način.

Potencijalni problemi binarnog pretraživanja

Binarna stabla pretraživanja su odlična, ali treba imati na umu nekoliko upozorenja. Obično su efikasne samo ako su izbalansirane. Uravnoteženo drvo je drvo u kojemrazlika između visina podstabala bilo kog čvora u stablu je najviše jedan. Pogledajmo primjer koji bi mogao pomoći da razjasnimo pravila. Zamislimo da niz počinje kao sortiranje.

Ako pokušate da pokrenete algoritam binarnog stabla pretraživanja na ovom stablu, on će raditi tač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 drvo nije uravnoteženo, ono neće pružiti iste prednosti kao uravnoteženo drvo.

Veoma je važno ispitati podatke sa kojima korisnik radi prilikom kreiranja binarnog stabla pretrage. Možete integrirati rutine kao što je randomizacija niza prije implementacije binarnog stabla pretraživanja cijelih brojeva kako biste ga izbalansirali.

Primjeri izračunavanja binarnog pretraživanja

Moramo odrediti kakvo će drvo rezultirati ako se 25 ubaci u sljedeće binarno stablo pretraživanja:

5 15

/ /

2 12 20

Kada umetnete x u stablo T koje još ne sadrži x, ključ x se uvijek stavlja u novi list. U vezi s tim, novo stablo će izgledati ovako:

5 15

/ /

2 12 20

Kakvu vrstu stabla biste dobili da umetnete 7 u sljedeće stablo binarnog pretraživanja?

5 15

/ /

2 12 20

Odgovor:

5 15

/ / /

2 7 12 20

Binarno stablo pretraživanja može se koristiti za pohranjivanje bilo kojeg objekta. Prednost upotrebe binarnog stabla pretraživanja umjesto povezane liste je da ako je stablo razumno izbalansirano i više liči na "puno" nego na "linearno" stablo, umetanje, pretraživanje i sve operacije brisanja mogu se implementirati za pokretanje u O(log N) vrijeme.