Razlika med binarnim drevesom in binarnim iskalnim drevesom

Ključna razlika - Binarno drevo vs Binarno iskanje drevo
 

Struktura podatkov je sistematičen način organiziranja podatkov za njihovo učinkovito uporabo. Urejanje podatkov z uporabo podatkovne strukture bi moralo skrajšati čas delovanja ali čas izvedbe. Tudi struktura podatkov naj bi zahtevala minimalno količino pomnilnika. Včasih so podatki lahko razporejeni v drevesni strukturi. 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 otroška vozlišča. Vozlišče na levi strani nadrejenega vozlišča je levo nadrejeno vozlišče, medtem ko je vozlišče desno od nadrejenega vozlišča desno vozlišče. Binarno drevo in Binarno drevo iskanja sta dve strukturi podatkov. Binarno drevo je vrsta podatkovne strukture, kjer ima lahko vsako nadrejeno vozlišče največ dve podrejeni vozlišči. Dvojno iskalno drevo je binarno drevo, kjer levi otrok vsebuje samo vozlišča z vrednostmi, manjšimi ali enakimi matičnemu vozlišču, in kjer desni otrok vsebuje samo vozlišča z vrednostmi, večjimi od nadrejenega vozlišča. To je tisto ključna razlika. Za razliko od struktur podatkov, kot so matriki, binarno drevo in binarno drevo iskanja nimata zgornje meje za shranjevanje podatkov.

VSEBINA

1. Pregled in ključne razlike
2. Kaj je Binarno drevo
3. Kaj je binarno iskalno drevo
4. Podobnosti med binarnim drevesom in binarnim iskalnim drevesom
5. Primerjava ob strani - Binarno drevo proti Binarnemu drevesu iskanja v tabeli
6. Povzetek

Kaj je Binarno drevo?

Pri urejanju podatkov v drevesni strukturi je vozlišče na vrhu drevesa znano kot korensko vozlišče. Za celotno drevo lahko obstaja samo ena korenina. Vsako vozlišče razen korenskega vozlišča ima en rob navzgor do vozlišča. Imenuje se matično vozlišče. Vozlišče pod nadrejeno kodo imenujemo njegovo nadrejeno vozlišče. Vsako nadrejeno vozlišče ima lahko največ dve podrejeni vozlišči. Imenujemo jih kot levo otroško vozlišče in desno otroško vozlišče. Vozlišče brez katerega koli podrejenega vozlišča se imenuje a listno vozlišče. Ni posebnega načina urejanja 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 korenina. Vsako vozlišče ima največ dve vozlišči. Če drevo vsebuje zank ali če eno vozlišče vsebuje več kot dveh vozlišč, ga ni mogoče razvrstiti kot binarno drevo. Za prehod iz enega vozlišča v drugo je vedno ena pot. Otroška vozlišča korenskega vozlišča 2 sta 7 in 5. Prav tako lahko vozlišče nima vozlišč. Toda katero koli 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. V vozliščih 4 in 11 ni podrejenih elementov. Zato so listna vozlišča.

Binarno drevo se uporablja za shranjevanje podatkov v hierarhičnem vrstnem redu. Podobno je s datotečno strukturo računalnika. Struktura podatkov, kot matrika, lahko shrani določeno količino podatkov. Toda v binarnem drevesu ni zgornje meje števila vozlišč.

Kaj je Binarno iskalno drevo?

Binarno drevo iskanja je struktura podatkov 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 matično vozlišče. Vozlišče pod dano povezavo z robom navzdol se imenuje njegovo nadrejeno vozlišče. Vozlišče brez nobenega otroškega vozlišča se imenuje listno vozlišče. Vsako nadrejeno vozlišče ima lahko največ dve vozlišči. Obstajajo otroška vozlišča, ki se nanašajo na levo otroško vozlišče in desno otroško vozlišče. Zgornji element se imenuje korensko vozlišče. Levi otrok vsebuje samo vozlišča z vrednostmi, manjšimi ali enakimi matičnemu vozlišču. Pravi otrok vsebuje samo vozlišča, katerih vrednosti so večje ali enake nadrejenemu vozlišču.

Slika 02: Primer drevesa binarnega iskanja

Element 8 je zgornji element. Zato je korensko vozlišče. Če je 3 matično vozlišče, sta 1 in 6 nadrejena vozlišča. 1 je levo otroško vozlišče, medtem ko je 6 desno otroško vozlišče. Levi otrok vsebuje vrednosti, ki so manjše ali enake matičnemu vozlišču. Ko je 3 nadrejeno vozlišče, mora biti na levi strani element, ki je manjši ali enak 3. V tem primeru je 1. Pravi otrok vsebuje samo vozlišča z vrednostmi, ki so večje od nadrejenega vozlišča. Če je 3 nadrejeno vozlišče, mora imeti desno nadrejeno vozlišče višjo vrednost kot 3. V tem primeru je 6. Prav tako obstaja določen vrstni red, da se vsak podatkovni element uredi v binarno drevo iskanja. Podatkovna struktura omogoča učinkovit način razvrščanja, pridobivanja in iskanja podatkov.

Kakšne so podobnosti med binarnim drevesom in binarnim iskalnim drevesom?

• Tako Binarno drevo kot Binarno drevo iskanja sta hierarhični podatkovni strukturi.
• Tako Binarno drevo kot Binarno drevo iskanja ima korenino.
• Tako Binarno drevo kot Binarno drevo za iskanje lahko imata največ dve otroški vozlišči.

Kakšna je razlika med binarnim drevesom in binarnim iskalnim drevesom?

Binarno drevo vs Binarno drevo iskanja
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 otrok vsebuje samo vozlišča z vrednostmi, manjšimi ali enakimi matičnemu vozlišču, in kjer desni otrok vsebuje samo vozlišča z vrednostmi, ki so večje od nadrejenega vozlišča.
Naročilo urejanja podatkov
Binarno drevo nima določenega vrstnega reda za urejanje podatkovnih elementov.	Binarno drevo iskanja ima določen vrstni red za urejanje podatkovnih elementov.
Uporaba
Binarno drevo se uporablja kot učinkovito iskanje podatkov in informacij v drevesni strukturi.	Binarno drevo iskanja se uporablja za vstavljanje, brisanje in iskanje podatkov.

Povzetek - Binarno drevo vs Binarno iskanje drevo 

Struktura podatkov je način organiziranja podatkov. Včasih so podatki lahko razporejeni v drevesni strukturi. Dve izmed njih sta binarno drevo in binarno drevo iskanja. Ta članek obravnava 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. Dvojno iskalno drevo je binarno drevo, kjer levi otrok vsebuje samo vozlišča z vrednostmi, manjšimi ali enakimi matičnemu vozlišču, in kjer desni otrok vsebuje samo vozlišča z vrednostmi, ki so večje od nadrejenega vozlišča.

Prenesite PDF Binary Tree vs Binary Search Tree

Lahko prenesete PDF različico tega članka in jo uporabite za namene brez povezave, kot je navedeno v navodilu. Prenesite PDF različico tukaj: Razlika med binarnim drevesom in binarnim iskalnim drevesom

Referenca:

1.Point, Vadnice. „Drevesje podatkovnih struktur in algoritmov.“, Tutorials Point, 8. januar 2018. Na voljo tukaj
2. Razlika med binarnim drevesom in binarnim iskalnim drevesom. | javapedia.Net, Javapedia.net, 15. februarja 2017. Na voljo tukaj

Vljudnost slik:

1.'Binarno drevo'Berrick Coetzee - lastno delo, (javno ime) prek Commons Wikimedia
2.'Binarno iskalno drevo'Bi ni naveden avtomatsko berljiv avtor. (na podlagi zahtevkov glede avtorskih pravic)., (javna domena) prek Commons Wikimedia