TechCodeview

Najprej bomo razumeli binarno drevo in binarno iskalno drevo ločeno, nato pa si bomo ogledali razlike med binarnim drevesom in binarnim iskalnim drevesom.

Kaj je binarno drevo?

A Binarno drevo jeKazalec na levega otroka:Shranjuje referenco levega podrejenega vozlišča.Kazalec na pravega otroka:Shranjuje referenco desnega podrejenega vozlišča.Podatkovni element:Podatkovni element je vrednost podatkov, ki jih shrani vozlišče.

Binarno drevo je mogoče predstaviti kot:

Na zgornji sliki lahko opazimo, da vsako vozlišče vsebuje največ 2 otroka. Če katero koli vozlišče ne vsebuje levega ali desnega otroka, bi bila vrednost kazalca glede na tega otroka NULL.

Osnovna terminologija, ki se uporablja v binarnem drevesu, je:

Korensko vozlišče:Korensko vozlišče je prvo ali najvišje vozlišče v binarnem drevesu.Nadrejeno vozlišče:Ko je vozlišče povezano z drugim vozliščem prek robov, je to vozlišče znano kot nadrejeno vozlišče. V binarnem drevesu ima lahko nadrejeno vozlišče največ 2 otroka.Podrejeno vozlišče:Če ima vozlišče svojega predhodnika, je to vozlišče znano kot a podrejeno vozlišče .Listni vozel:Vozlišče, ki ne vsebuje nobenega otroka, znano kot a listni vozel .Notranje vozlišče:Vozlišče, ki ima vsaj 2 otroka, znano kot an notranje vozlišče .Globina vozlišča:Razdalja od korenskega vozlišča do danega vozlišča je znana kot a globina vozlišča . Vsem vozliščem zagotovimo oznake, kot je korensko vozlišče označeno z 0, ker nima globine, otroci korenskih vozlišč so označeni z 1, otroci korenskega otroka so označeni z 2.Višina:Najdaljša razdalja od koreninskega vozlišča do listnega vozlišča je višina vozlišča .

V binarnem drevesu obstaja eno drevo, znano kot a popolno binarno drevo . Je drevo, v katerem morajo vsa notranja vozlišča vsebovati dve vozlišči, vsa listna vozlišča pa morajo biti na isti globini. V primeru popolnega binarnega drevesa se lahko skupno število vozlišč v binarnem drevesu izračuna z uporabo naslednje enačbe:

n = 2^m+1-1

kjer je n število vozlišč, m je globina vozlišča.

Kaj je binarno iskalno drevo?

A Binarno iskalno drevo je drevo, ki sledi nekemu vrstnemu redu za razporeditev elementov, medtem ko binarno drevo ne sledi nobenemu vrstnemu redu. V binarnem iskalnem drevesu mora biti vrednost levega vozlišča manjša od nadrejenega vozlišča, vrednost desnega vozlišča pa mora biti večja od nadrejenega vozlišča.

Razumejmo koncept binarnega iskalnega drevesa skozi primere.

Na zgornji sliki lahko opazimo, da je vrednost korenskega vozlišča 15, kar je večje od vrednosti vseh vozlišč v levem poddrevesu. Vrednost korenskega vozlišča je manjša od vrednosti vseh vozlišč v desnem poddrevesu. Zdaj se premaknemo na levi podrejeni del korenskega vozlišča. 10 je večje od 8 in manjše od 12; izpolnjuje tudi lastnost binarnega iskalnega drevesa. Zdaj se premaknemo na desni podrejeni del korenskega vozlišča; vrednost 20 je večja od 17 in manjša od 25; izpolnjuje tudi lastnost binarnega iskalnega drevesa. Zato lahko rečemo, da je zgoraj prikazano drevo binarno iskalno drevo.

Zdaj, če spremenimo vrednost 12 v 16 v zgornjem binarnem drevesu, moramo ugotoviti, ali je še vedno binarno iskalno drevo ali ne.

Vrednost korenskega vozlišča je 15, kar je večje od 10, vendar manjše od 16, zato ne izpolnjuje lastnosti binarnega iskalnega drevesa. Zato ni binarno iskalno drevo.

Operacije na binarnem iskalnem drevesu

Na binarnem iskalnem drevesu lahko izvajamo operacije vstavljanja, brisanja in iskanja. Razumejmo, kako poteka iskanje pri binarnem iskanju. Spodaj je prikazano binarno drevo, na katerem moramo izvesti operacijo iskanja:

Recimo, da moramo poiskati 10 v zgornjem binarnem drevesu. Za izvedbo binarnega iskanja bomo upoštevali vsa cela števila v razvrščeni matriki. Najprej ustvarimo popoln seznam v iskalnem prostoru in vse številke bodo obstajale v iskalnem prostoru. Iskalni prostor je označen z dvema kazalcema, to sta začetek in konec. Matriko zgornjega binarnega drevesa lahko predstavimo kot

Najprej bomo izračunali srednji element in ga primerjali z elementom, ki ga želimo iskati. Srednji element se izračuna z uporabo n/2. Vrednost n je 7; zato je srednji element 15. Srednji element ni enak iskanemu elementu, tj. 10.

Opomba: če je element, ki ga iščete, manjši od srednjega elementa, bo iskanje izvedeno v levi polovici; drugače bo iskanje potekalo na desni polovici. V primeru enakosti je element najden.

Ker je element, ki ga je treba iskati, manjši od srednjega elementa, bo iskanje izvedeno na levi matriki. Zdaj je iskanje zmanjšano na polovico, kot je prikazano spodaj:

Srednji element v levem nizu je 10, kar je enako iskanemu elementu.

Časovna zapletenost

V binarnem iskanju je n elementov. Če srednji element ni enak iskanemu elementu, se iskalni prostor zmanjša na n/2 in bomo nadaljevali z zmanjševanjem iskalnega prostora za n/2, dokler elementa ne najdemo. V celotnem zmanjšanju, če se premaknemo od n do n/2 do n/4 in tako naprej, bo trajalo log₂n korakov.

Razlike med binarnim drevesom in binarnim iskalnim drevesom