Ključna razlika – binarno drevo proti binarnemu iskalnemu drevesu
Podatkovna struktura je sistematičen način organiziranja podatkov za njihovo učinkovito uporabo. Urejanje podatkov z uporabo podatkovne strukture bi moralo zmanjšati čas delovanja ali čas izvajanja. Tudi struktura podatkov mora zahtevati minimalno količino pomnilnika. Včasih je podatke mogoče urediti v drevesno strukturo. Drevo predstavlja vozlišče, povezano z robovi. Najvišje vozlišče je koren. Vsako vozlišče ima lahko največ dve vozlišči. Znani so kot podrejena vozlišča. Vozlišče na levi strani nadrejenega vozlišča je levo podrejeno vozlišče, medtem ko je vozlišče na desni strani nadrejenega vozlišča desno vozlišče. Binarno drevo in binarno iskalno drevo sta dve drevesni podatkovni strukturi. Binarno drevo je vrsta podatkovne strukture, kjer ima lahko vsako nadrejeno vozlišče največ dve podrejeni vozlišči. Binarno iskalno drevo je binarno drevo, kjer levi podrejeni vsebuje samo vozlišča z vrednostmi, ki so manjše ali enake nadrejenemu vozlišču, in kjer desni podrejeni vsebuje samo vozlišča z vrednostmi, večjimi od nadrejenega vozlišča. To je ključna razlika. Za razliko od podatkovnih struktur, kot so polja, binarno drevo in binarno iskalno drevo nimata zgornje meje za shranjevanje podatkov.
Kaj je binarno drevo?
Pri urejanju podatkov v drevesni strukturi je vozlišče na vrhu drevesa znano kot korensko vozlišče. Za celotno drevo je lahko samo ena korenina. Vsako vozlišče, razen korenskega vozlišča, ima en rob navzgor do vozlišča. Imenuje se nadrejeno vozlišče. Vozlišče pod nadrejeno kodo se imenuje njegovo podrejeno vozlišče. Vsako nadrejeno vozlišče ima lahko največ dve podrejeni vozlišči. Imenujejo se levo podrejeno vozlišče in desno podrejeno vozlišče. Vozlišče brez podrejenega vozlišča se imenuje listno vozlišče. Ni posebnega načina za urejanje podatkov v binarnem drevesu. Obstaja pot od korenskega vozlišča do vsakega vozlišča.
Slika 01: Primer binarnega drevesa
Zgoraj je primer binarnega drevesa. Element 2 na vrhu drevesa je koren. Vsako vozlišče ima največ dve vozlišči. Če drevo vsebuje kakršne koli zanke ali če eno vozlišče vsebuje več kot dve vozlišči, ga ni mogoče razvrstiti kot binarno drevo. Za prehod od enega vozlišča do drugega vedno obstaja ena pot. Podrejeni vozlišči korenskega vozlišča 2 sta 7 in 5. Možno je tudi, da vozlišče nima vozlišč. Toda nobeno vozlišče ne more imeti več kot dveh vozlišč. Desni element korena je 5. Ta element 5 je nadrejeno vozlišče za podrejeno vozlišče 9. Vozlišči 4 in 11 nimata podrejenih elementov. Zato so listna vozlišča.
Binarno drevo se uporablja za shranjevanje podatkov v hierarhičnem vrstnem redu. Podobna je datotečni strukturi računalnika. Podatkovna struktura, kot je matrika, lahko shrani določeno količino podatkov. Toda v binarnem drevesu ni zgornje omejitve števila vozlišč.
Kaj je binarno iskalno drevo?
Binarno iskalno drevo je podatkovna struktura binarnega drevesa. Podobno kot binarno drevo ima lahko tudi binarno iskalno drevo dve vozlišči. Vsako vozlišče, razen korenskega vozlišča, ima en rob navzgor do vozlišča. Imenuje se nadrejeno vozlišče. Vozlišče pod dano, povezano z robom navzdol, se imenuje njegovo podrejeno vozlišče. Vozlišče brez podrejenega vozlišča se imenuje listno vozlišče. Vsako nadrejeno vozlišče ima lahko največ dve vozlišči. Obstajajo podrejena vozlišča, ki se nanašajo na levo in desno podrejeno vozlišče. Najvišji element se imenuje korensko vozlišče. Levi podrejeni element vsebuje samo vozlišča z vrednostmi, ki so manjše ali enake nadrejenemu vozlišču. Desni podrejeni vsebuje samo vozlišča z vrednostmi, večjimi ali enakimi nadrejenemu vozlišču.
Slika 02: Primer binarnega iskalnega drevesa
Element 8 je najvišji element. Zato je korensko vozlišče. Če je 3 nadrejeno vozlišče, potem sta 1 in 6 podrejeni vozlišči. 1 je levo podrejeno vozlišče, medtem ko je 6 desno podrejeno vozlišče. Levi podrejeni element vsebuje vrednosti, ki so manjše ali enake nadrejenemu vozlišču. Ko je 3 nadrejeno vozlišče, mora leva stran vsebovati element, ki je manjši ali enak 3. V tem primeru je 1. Desni podrejeni element vsebuje samo vozlišča z vrednostmi, večjimi od nadrejenega vozlišča. Ko je 3 nadrejeno vozlišče, mora imeti desno podrejeno vozlišče višjo vrednost od 3. V tem primeru je 6. Podobno obstaja določen vrstni red za razporeditev vsakega podatkovnega elementa v binarno iskalno drevo. To je podatkovna struktura, ki zagotavlja učinkovit način za razvrščanje, pridobivanje in iskanje podatkov.
Kakšne so podobnosti med binarnim drevesom in binarnim iskalnim drevesom?
- Tako binarno drevo kot binarno iskalno drevo sta hierarhični podatkovni strukturi.
- Tako binarno drevo kot binarno iskalno drevo imata koren.
- Tako binarno drevo kot binarno iskalno drevo imata lahko največ dve podrejeni vozlišči.
Kakšna je razlika med binarnim drevesom in binarnim iskalnim drevesom?
Binarno drevo proti binarnemu iskalnemu drevesu |
|
| Binarno drevo je vrsta podatkovne strukture, kjer ima lahko vsako nadrejeno vozlišče največ dve podrejeni vozlišči. | Drevo binarnega iskanja je binarno drevo, kjer levi podrejeni vsebuje samo vozlišča z vrednostmi, ki so manjše ali enake nadrejenemu vozlišču, in kjer desni podrejeni vsebuje samo vozlišča z vrednostmi, večjimi od nadrejenega vozlišča. |
| Vrstni red urejanja podatkov | |
| Binarno drevo nima posebnega vrstnega reda za razporeditev podatkovnih elementov. | Binarno iskalno drevo ima določen vrstni red za razporeditev podatkovnih elementov. |
| Uporaba | |
| Binarno drevo se uporablja kot učinkovito iskanje podatkov in informacij v drevesni strukturi. | Binarno iskalno drevo se uporablja za vstavljanje, brisanje in iskanje podatkov. |
Povzetek – Binarno drevo proti binarnemu iskalnemu drevesu
Podatkovna struktura je način organiziranja podatkov. Včasih je podatke mogoče urediti v drevesno strukturo. Dva od njih sta binarno drevo in binarno iskalno drevo. Ta članek je obravnaval razliko med binarnim drevesom in binarnim iskalnim drevesom. Binarno drevo je vrsta podatkovne strukture, kjer ima lahko vsako nadrejeno vozlišče največ dve podrejeni vozlišči. Binarno iskalno drevo je binarno drevo, kjer levi podrejeni vsebuje samo vozlišča z vrednostmi, manjšimi ali enakimi nadrejenemu vozlišču, in kjer desni podrejeni vsebuje samo vozlišča z vrednostmi, večjimi od nadrejenega vozlišča.
Prenesite PDF dvojiškega drevesa v primerjavi z binarnim iskalnim drevesom
Različico PDF tega članka lahko prenesete in jo uporabite za namene brez povezave v skladu z opombo o citiranju. Prenesite PDF različico tukaj: Razlika med binarnim drevesom in binarnim iskalnim drevesom
