Binarno stablo pretraživanja jedna je od različitih struktura podataka koje nam pomažu organizirati i sortirati podatke. To je učinkovit način pohranjivanja podataka u hijerarhiji i vrlo je fleksibilan.
U ovom članku pobliže ćemo pogledati kako funkcionira - zajedno s njegovim svojstvima i primjenom.
Što je binarno stablo pretraživanja?
Binarno stablo pretraživanja je struktura podataka sastavljena od čvorova—slično povezanim popisima. Mogu postojati dvije vrste čvorova: roditelj i dijete. Korijenski čvor je početna točka strukture koja se grana u dva podređena čvora, nazvana lijevi čvor i desni čvor.
Svaki čvor može referencirati samo njegov roditelj, a mi možemo prijeći čvorove stabla ovisno o smjeru. Stablo binarnog pretraživanja ima tri glavna svojstva:
- Lijevi čvor je manji od svog roditelja.
- Desni čvor je veći od svog roditelja.
- Lijevo i desno podstablo moraju biti stabla binarnog pretraživanja.
Savršeno stablo binarnog pretraživanja postiže se kada su sve razine popunjene, a svaki čvor ima lijevi i desni podređeni čvor.
Povezano: Knjižnice za znanost o podacima za Python koje bi trebao koristiti svaki znanstvenik
Osnovne operacije binarnog stabla pretraživanja
Sada imate bolju ideju o tome što je stablo binarnog pretraživanja, u nastavku možemo pogledati njegove osnovne operacije.
1. Operacija pretraživanja
Pretraživanje nam omogućuje lociranje određene vrijednosti prisutne u stablu. Možemo koristiti dvije vrste pretraživanja: pretraživanje u širinu (BFS) i pretraživanje u dubinu (DFS). Pretraživanje u širinu je algoritam pretraživanja koji počinje u korijenskom čvoru i prelazi vodoravno, sa jedne na drugu stranu, dok se ne pronađe cilj. Svaki se čvor posjećuje jednom tijekom ove pretrage.
Pretraživanje u dubinu, s druge strane, prelazi stablo okomito - počevši od korijenskog čvora i ide niz jednu granu. Ako je cilj pronađen, operacija završava. Ali ako ne, pretražuje druge čvorove.
2. Operacija umetanja
Operacija umetanja koristi operaciju pretraživanja kako bi odredila mjesto gdje treba umetnuti novi čvor. Proces počinje od korijenskog čvora, a pretraga počinje dok se ne dođe do odredišta. Postoje tri slučaja koja treba razmotriti s umetanjem.
- Slučaj 1: Kada čvor ne postoji. Čvor koji treba umetnuti postat će korijenski čvor.
- Slučaj 2: Nema djece. U ovom slučaju, čvor će se usporediti s korijenskim čvorom. Ako je veći, postat će pravo dijete; inače će postati lijevo dijete.
- Slučaj 3: Kada su prisutni korijen i njegova djeca. Novi će se čvor uspoređivati sa svakim čvorom na svom putu kako bi se odredilo koji čvor sljedeći posjećuje. Ako je čvor veći od korijenskog čvora, prelazit će niz desno podstablo ili lijevo. Slično, usporedbe se rade na svakoj razini kako bi se utvrdilo hoće li ići desno ili lijevo dok ne stigne na odredište.
3. Operacija brisanja
Operacija brisanja koristi se za uklanjanje određenog čvora unutar stabla. Brisanje se smatra lukavim jer nakon uklanjanja čvora, stablo se mora u skladu s tim ponovno organizirati. Postoje tri glavna slučaja za razmatranje:
- Slučaj 1: Brisanje lisnog čvora. Listni čvor je čvor bez djece. Ovo je najlakše ukloniti jer ne utječe ni na jedan drugi čvor; jednostavno prelazimo stablo dok ne dođemo do njega i izbrišemo ga.
- Slučaj 2: Brisanje čvora s jednim dijetetom. Brisanje roditelja s jednim čvorom dovest će do toga da će dijete zauzeti svoju poziciju, a svi sljedeći čvorovi će se pomaknuti za jednu razinu. Neće biti promjena u strukturi podstabala.
- Slučaj 3: Brisanje čvora s dvoje djece. Kada moramo ukloniti čvor s dvoje djece, prvo moramo pronaći sljedeći čvor koji može zauzeti svoju poziciju. Dva čvora mogu zamijeniti uklonjeni čvor, neredovni nasljednik ili prethodnik. Nasljednik nereda je krajnje lijevo dijete desnog podstabla, a prethodnik nereda je krajnje desno dijete lijevog podstabla. Kopiramo sadržaj nasljednika/prethodnika u čvor i brišemo nasljednika/prethodnika nereda.
Povezano: Kako izgraditi strukture podataka s JavaScript ES6 klasama
Kako prijeći stablo binarnog pretraživanja
Traversal je proces kroz koji se krećemo po binarnom stablu pretraživanja. To se radi za lociranje određene stavke ili za ispis obrisa stabla. Uvijek počinjemo od korijenskog čvora i moramo pratiti rubove da bismo došli do ostalih čvorova. Svaki čvor treba smatrati podstablom, a proces se ponavlja sve dok se ne posjete svi čvorovi.
- Prijelaz u narudžbi: Prelazak u redoslijedu će proizvesti kartu u rastućem redoslijedu. Ovom metodom počinjemo od lijevog podstabla i nastavljamo do korijenskog i desnog podstabla.
- Prijelaz prednarudžbe: U ovoj metodi prvo se posjećuje korijenski čvor, a zatim lijevo podstablo i desno podstablo.
- Prijelaz nakon narudžbe: Ovo obilaženje uključuje posljednji posjet korijenskom čvoru. Počinjemo od lijevog podstabla, zatim desnog podstabla, a zatim korijenskog čvora.
Aplikacije u stvarnom svijetu
Dakle, kako koristimo algoritme binarnog stabla pretraživanja? Kao što se može pretpostaviti, izuzetno su učinkoviti u pretraživanju i sortiranju. Najveća snaga binarnih stabala je njihova organizirana struktura. Omogućuje pretraživanje izvanrednim brzinama smanjujući količinu podataka koje trebamo analizirati za polovicu po prolazu.
Stabla binarnog pretraživanja omogućuju nam učinkovito održavanje dinamički promjenjivog skupa podataka u organiziranom obliku. Za aplikacije koje često ubacuju i uklanjaju podatke, one su vrlo korisne. Motori za videoigre koriste algoritam temeljen na stablima poznatim kao binarna particija prostora kako bi pomogli u uređenju objekata. Microsoft Excel i većina softvera za proračunske tablice koriste binarna stabla kao osnovnu strukturu podataka.
Možda ćete biti iznenađeni kada znate da Morseov kod koristi binarno stablo pretraživanja za kodiranje podataka. Još jedan istaknuti razlog zašto su stabla binarnog pretraživanja toliko korisna su njihove višestruke varijacije. Njihova fleksibilnost dovela je do stvaranja brojnih varijanti za rješavanje svih vrsta problema. Kada se pravilno koriste, stabla binarnog pretraživanja su velika prednost.
Stabla binarnog pretraživanja: savršena početna točka
Jedan od glavnih načina za procjenu stručnosti inženjera je njihovo poznavanje i primjena struktura podataka. Strukture podataka su korisne i mogu pomoći u stvaranju učinkovitijeg sustava. Stabla binarnog pretraživanja izvrstan su uvod u strukture podataka za sve programere koji počinju.
Želite razumjeti JavaScript nizove, ali ne možete se uhvatiti ukoštac s njima? Pogledajte naše primjere JavaScript polja za smjernice.
Pročitajte dalje
- Programiranje
- Programiranje
- Alati za programiranje
Maxwell je programer softvera koji u svoje slobodno vrijeme radi kao pisac. Strastveni tehnološki entuzijast koji se voli baviti svijetom umjetne inteligencije. Kad nije zauzet poslom, ne čita ili igra video igrice.
Pretplatite se na naše obavijesti
Pridružite se našem biltenu za tehničke savjete, recenzije, besplatne e-knjige i ekskluzivne ponude!
Kliknite ovdje za pretplatu