Kaj je drevo binarnega iskanja?

Binarno iskalno drevo je ena od različnih struktur podatkov, ki nam pomagajo organizirati in razvrščati podatke. To je učinkovit način za shranjevanje podatkov v hierarhiji in je zelo prilagodljiv.

V tem članku si bomo podrobneje ogledali, kako deluje – skupaj z njegovimi lastnostmi in aplikacijami.

Kaj je drevo binarnega iskanja?

Binarno drevo iskanja je podatkovna struktura, sestavljena iz vozlišč – podobna povezanim seznamom. Obstajata lahko dve vrsti vozlišč: starševsko in otrokovo. Korensko vozlišče je začetna točka strukture, ki se razcepi na dve podrejeni vozlišči, imenovani levo in desno vozlišče.

Na vsako vozlišče se lahko sklicuje samo njegov starš, vozlišča drevesa pa lahko prečkamo glede na smer. Drevo binarnega iskanja ima tri glavne lastnosti:

1. Levo vozlišče je manjše od nadrejenega.
2. Desno vozlišče je večje od nadrejenega.
3. Levo in desno poddrevo morata biti drevesa binarnega iskanja.

Popolno drevo binarnega iskanja je doseženo, ko so vse ravni zapolnjene in ima vsako vozlišče levo in desno podrejeno vozlišče.

Povezano: Knjižnice podatkovne znanosti za Python, ki bi jih moral uporabljati vsak podatkovni znanstvenik

Osnovne operacije binarnega iskalnega drevesa

Zdaj, ko imate boljšo predstavo o tem, kaj je drevo binarnega iskanja, si lahko spodaj ogledamo njegove osnovne operacije.

1. Iskalna operacija

Iskanje nam omogoča, da najdemo določeno vrednost, ki je prisotna v drevesu. Uporabljamo lahko dve vrsti iskanja: iskanje v širino (BFS) in iskanje v globino (DFS). Iskanje v širino je iskalni algoritem, ki se začne v korenskem vozlišču in poteka vodoravno, od strani do strani, dokler ni najden cilj. Vsako vozlišče je med tem iskanjem obiskano enkrat.

Iskanje v globino po drugi strani prečka drevo navpično – začenši od koreninskega vozlišča in nadaljuje po eni veji. Če je cilj ugotovljen, se operacija konča. Če pa ne, išče druga vozlišča.

2. Operacija vstavi

Operacija vstavljanja uporablja operacijo iskanja za določitev lokacije, kamor naj se vstavi novo vozlišče. Postopek se začne od korenskega vozlišča in iskanje se začne, dokler ni dosežen cilj. Pri vstavljanju je treba upoštevati tri primere.

• Primer 1: Ko vozlišče ne obstaja. Vozlišče, ki ga je treba vstaviti, bo postalo korensko vozlišče.

• Primer 2: Ni otrok. V tem primeru bo vozlišče primerjano s korenskim vozliščem. Če bo večji, bo postal pravi otrok; drugače bo postal levi otrok.

• Primer 3: Ko so prisotni koren in njegovi otroci. Novo vozlišče bo primerjano z vsakim vozliščem na njegovi poti, da se ugotovi, katero vozlišče bo naslednje obiskalo. Če je vozlišče večje od korenskega vozlišča, bo prešlo navzdol po desnem poddrevu ali pa po levem. Podobno se opravijo primerjave na vsaki ravni, da se ugotovi, ali bo šel desno ali levo, dokler ne prispe na cilj.

3. Izbriši operacijo

Operacija brisanja se uporablja za odstranitev določenega vozlišča znotraj drevesa. Brisanje se šteje za težavno, saj je treba po odstranitvi vozlišča drevo ustrezno ponovno organizirati. Upoštevati je treba tri glavne primere:

• Primer 1: Brisanje listnega vozlišča. Listno vozlišče je vozlišče brez otrok. To je najlažje odstraniti, saj ne vpliva na nobeno drugo vozlišče; preprosto prečkamo drevo, dokler ga ne dosežemo in ga izbrišemo.

• Primer 2: Brisanje vozlišča z enim otrokom. Če izbrišete starša z enim vozliščem, bo otrok zasedel svoj položaj, vsa naslednja vozlišča pa se bodo premaknila za eno raven navzgor. V strukturi poddreves ne bo sprememb.

• Primer 3: Brisanje vozlišča z dvema otrokoma. Ko moramo odstraniti vozlišče z dvema otrokoma, moramo najprej poiskati naslednje vozlišče, ki lahko zavzame svoj položaj. Dve vozlišči lahko nadomestita odstranjeno vozlišče, naslednika v neredu ali predhodnika. Naslednik v neredu je skrajni levi otrok desnega poddrevesa, predhodnik v neredu pa je skrajni desni otrok levega poddrevesa. Vsebino naslednika/predhodnika kopiramo v vozlišče in izbrišemo nerednega naslednika/predhodnika.

Povezano: Kako zgraditi podatkovne strukture z razredi JavaScript ES6

Kako prečkati drevo binarnega iskanja

Prehod je proces, skozi katerega se premikamo po drevesu binarnega iskanja. To se naredi za iskanje določenega predmeta ali za tiskanje obrisa drevesa. Vedno začnemo od korenskega vozlišča in moramo slediti robom, da pridemo do drugih vozlišč. Vsako vozlišče je treba obravnavati kot poddrevo in postopek se ponavlja, dokler ne obiščete vseh vozlišč.

• Prehod po naročilu: Če se premikate po vrstnem redu, boste ustvarili zemljevid v naraščajočem vrstnem redu. S to metodo začnemo z levega poddrevesa in nadaljujemo do korenskega in desnega poddrevesa.

• Prehod prednaročila: Pri tej metodi se najprej obišče korensko vozlišče, nato pa levo poddrevo in desno poddrevo.

• Prehod po naročilu: Ta prehod vključuje zadnji obisk korenskega vozlišča. Začnemo z levega poddrevesa, nato desnega poddrevesa in nato korenskega vozlišča.

Aplikacije iz resničnega sveta

Kako torej uporabimo algoritme binarnega iskalnega drevesa? Kot lahko domnevamo, so izjemno učinkoviti pri iskanju in razvrščanju. Največja moč binarnih dreves je njihova organizirana struktura. Omogoča iskanje z izjemno hitrostjo, tako da zmanjša količino podatkov, ki jih moramo analizirati, za polovico na prehod.

Binarna drevesa iskanja nam omogočajo učinkovito vzdrževanje dinamično spreminjajočega se niza podatkov v organizirani obliki. Za aplikacije, ki imajo podatke pogosto vstavljene in odstranjene, so zelo koristne. Motorji za video igre uporabljajo algoritem, ki temelji na drevesih, znanih kot binarna prostorska particija, da pomagajo pri urejenem upodabljanju predmetov. Microsoft Excel in večina programske opreme za preglednice uporabljajo binarna drevesa kot svojo osnovno podatkovno strukturo.

Morda boste presenečeni, ko veste, da Morsejeva abeceda za kodiranje podatkov uporablja binarno iskalno drevo. Drug pomemben razlog, zakaj so drevesa binarnega iskanja tako uporabna, so njihove številne različice. Njihova prilagodljivost je privedla do ustvarjanja številnih različic za reševanje vseh vrst težav. Ko se pravilno uporabljajo, so drevesa binarnega iskanja odlična prednost.

Binarna iskalna drevesa: popolno izhodišče

Eden od glavnih načinov za merjenje strokovnega znanja inženirja je njihovo poznavanje in uporaba podatkovnih struktur. Podatkovne strukture so koristne in lahko pomagajo ustvariti učinkovitejši sistem. Binarna drevesa iskanja so odličen uvod v podatkovne strukture za vsakega razvijalca, ki je na začetku.

15 metod matrike JavaScript, ki bi jih morali obvladati danes

Želite razumeti polja JavaScript, vendar se jih ne morete spopasti? Za napotke si oglejte naše primere nizov JavaScript.

Preberite Naprej

O avtorju