Preden izvemo o razlikah med binarnim iskalnim drevesom in drevesom AVL, bi morali vedeti o binarnem iskalnem drevesu in drevesu AVL ločeno.
Kaj je binarno iskalno drevo?
The binarno iskalno drevo je drevo binarno drevo. Kot vemo, ima lahko to drevo 'n' število otrok, medtem ko; binarno drevo lahko vsebuje največ dva otroka. Torej omejitvi binarnega drevesa sledi tudi binarno iskalno drevo. Vsako vozlišče v binarnem iskalnem drevesu mora imeti največ dva otroka; z drugimi besedami, lahko rečemo, da je binarno iskalno drevo različica binarnega drevesa.
Binarno iskalno drevo prav tako sledi lastnostim binarnega iskanja. Pri binarnem iskanju morajo biti vsi elementi v matriki razvrščeni. Srednji element izračunamo pri binarnem iskanju, pri katerem levi del srednjega elementa vsebuje vrednost, manjšo od srednje vrednosti, desni del srednjega elementa pa vsebuje vrednosti, večje od srednje vrednosti.
V binarnem iskalnem drevesu srednji element postane korensko vozlišče, desni del postane desno poddrevo, levi del pa levo poddrevo. Zato lahko rečemo, da je binarno iskalno drevo kombinacija a binarno drevo in binarno iskanje .
Opomba: Binarno iskalno drevo je mogoče definirati kot binarno drevo, v katerem so vsi elementi levega poddrevesa manjši od korenskega vozlišča, vsi elementi desnega poddrevesa pa so večji od korenskega vozlišča.
Časovna kompleksnost v binarnem iskalnem drevesu
Če je binarno iskalno drevo skoraj uravnoteženo drevo, bodo imele vse operacije časovno zapletenost O (prijava) ker je iskanje razdeljeno na levo ali desno poddrevo.
dinamično polje java
Če je binarno iskalno drevo nagnjeno levo ali desno, bodo imele vse operacije časovno zapletenost O(n) ker moramo prečkati do n elementov.
Kaj je drevo AVL?
An AVL drevo je samouravnoteženo binarno iskalno drevo, kjer razlika med višino levega in desnega poddrevesa ne sme biti večja od ena. Ta razlika je znana kot faktor ravnovesja. V drevesu AVL so lahko vrednosti faktorja ravnotežja -1, 0 ali 1.
Kako poteka samouravnoteženje binarnega iskalnega drevesa?
Kot vemo, je drevo AVL samouravnotežno binarno iskalno drevo. Če binarno iskalno drevo ni uravnoteženo, se lahko samouravnoteži z nekaterimi preureditvami. Te preureditve je mogoče izvesti z nekaj rotacijami.
Razumejmo samouravnoteženje na primeru.
Recimo, da želimo vstaviti 10, 20, 30 v drevesu AVL.
Sledijo načini vstavljanja 10, 20, 30 v drevo AVL:
Korak 1: Najprej ustvarimo binarno iskalno drevo, kot je prikazano spodaj:
2. korak: Na zgornji sliki lahko opazimo, da je drevo neuravnoteženo, ker je faktor ravnovesja vozlišča 30 2. Da bi bilo drevo AVL, moramo izvesti nekaj rotacij. Če na vozlišču 20 izvedemo pravo rotacijo, se bo vozlišče 30 premaknilo navzdol, vozlišče 20 pa navzgor, kot je prikazano spodaj:
Kot lahko opazimo, končno drevo sledi lastnostim drevesa binarnega iskanja in uravnoteženega drevesa; torej je drevo AVL.
arraylist v java sort
V primeru je bilo drevo levo neuravnoteženo drevo, tako izvedemo pravo rotacijo na vozlu.
Korak 1: Najprej ustvarimo binarno iskalno drevo, kot je prikazano spodaj:
2. korak: Na zgornji sliki lahko opazimo, da je drevo neuravnoteženo, ker je faktor ravnovesja vozlišča 10 -2. Da bi bilo drevo AVL, moramo izvesti nekaj rotacij. Gre za desno neuravnoteženo drevo, zato bomo izvedli levo rotacijo. Če na vozlišču 20 izvedemo levo rotacijo, se bo vozlišče 20 premaknilo navzgor, vozlišče 10 pa navzdol, kot je prikazano spodaj:
Kot lahko opazimo, končno drevo sledi lastnostim Binarno iskalno drevo in a uravnoteženo drevo ; torej je drevo AVL.
Korak 1: Najprej ustvarimo drevo binarnega iskanja, kot je prikazano spodaj:
2. korak: Na zgornji sliki lahko opazimo, da je drevo neuravnoteženo, ker je faktor ravnovesja korenskega vozlišča 2. Da bi bilo drevo AVL, moramo izvesti nekaj rotacij. Zgornji scenarij je levo-desno neuravnotežen, saj je eno vozlišče levo od nadrejenega vozlišča, drugo pa desno od nadrejenega vozlišča. Najprej bomo izvedli levo rotacijo, rotacija pa se zgodi med vozliščema 10 in 20. Po levi rotaciji se bo 20 premaknilo navzgor, 10 pa navzdol, kot je prikazano spodaj:
kako naj ugotovim velikost svojega monitorja
Kljub temu je drevo neuravnoteženo, zato na drevesu izvajamo pravilno rotacijo. Ko se na drevesu izvede pravilna rotacija, bo drevo želelo, kot je prikazano spodaj:
Kot lahko opazimo v zgornjem drevesu, drevo sledi lastnostim drevesa binarnega iskanja in uravnoteženega drevesa; torej je drevo AVL.
Korak 1: Najprej ustvarimo drevo binarnega iskanja, kot je prikazano spodaj:
2. korak: Na zgornji sliki lahko opazimo, da je drevo neuravnoteženo, ker je faktor ravnotežja korenskega vozlišča 2. Da bi bilo drevo AVL, moramo izvesti nekaj rotacij. Zgornji scenarij je desno-levo neuravnotežen, saj je eno vozlišče desno od nadrejenega vozlišča, drugo vozlišče pa levo od nadrejenega vozlišča. Najprej bomo izvedli desno rotacijo, ki se zgodi med vozliščema 30 in 20. Po desni rotaciji se bo 20 premaknilo navzgor, 30 pa navzdol, kot je prikazano spodaj:
Kljub temu je zgornje drevo neuravnoteženo, zato moramo na vozlišču izvesti levo rotacijo. Ko se izvede vrtenje v levo, se bo vozlišče 20 premaknilo navzgor, vozlišče 10 pa navzdol, kot je prikazano spodaj:
Kot lahko opazimo v zgornjem drevesu, drevo sledi lastnostim drevesa binarnega iskanja in uravnoteženega drevesa; torej je drevo AVL.
Razlike med binarnim iskalnim drevesom in drevesom AVL
| Binarno iskalno drevo | AVL drevo |
|---|---|
| Vsako binarno iskalno drevo je binarno drevo, ker obe drevesi vsebujeta največ dva otroka. | Vsako drevo AVL je tudi binarno drevo, ker ima drevo AVL tudi največ dva otroka. |
| V BST ne obstaja izraz, kot je faktor ravnovesja. | V drevesu AVL vsako vozlišče vsebuje faktor ravnotežja, vrednost faktorja ravnovesja pa mora biti -1, 0 ali 1. |
| Vsako drevo binarnega iskanja ni drevo AVL, ker je BST lahko uravnoteženo ali neuravnoteženo drevo. | Vsako drevo AVL je binarno iskalno drevo, ker drevo AVL sledi lastnostim BST. |
| Vsako vozlišče v drevesu binarnega iskanja je sestavljeno iz treh polj, tj. levega poddrevesa, vrednosti vozlišča in desnega poddrevesa. | Vsako vozlišče v drevesu AVL je sestavljeno iz štirih polj, tj. levega poddrevesa, vrednosti vozlišča, desnega poddrevesa in faktorja ravnovesja. |
| V primeru drevesa binarnega iskanja, če želimo v drevo vstaviti katero koli vozlišče, primerjamo vrednost vozlišča s korensko vrednostjo; če je vrednost vozlišča večja od vrednosti korenskega vozlišča, se vozlišče vstavi v desno poddrevo, sicer pa se vozlišče vstavi v levo poddrevo. Ko je vozlišče vstavljeno, ni treba preverjati faktorja višinskega ravnovesja, da bi bilo vstavljanje dokončano. | V primeru drevesa AVL bomo najprej našli primerno mesto za vstavljanje vozlišča. Ko je vozlišče vstavljeno, bomo izračunali faktor ravnovesja vsakega vozlišča. Če je faktor uravnoteženosti vsakega vozlišča izpolnjen, je vstavljanje končano. Če je faktor ravnotežja večji od 1, potem moramo izvesti nekaj rotacij, da uravnotežimo drevo. |
| V drevesu binarnega iskanja je višina ali globina drevesa O(n), kjer je n število vozlišč v drevesu binarnega iskanja. | V drevesu AVL je višina ali globina drevesa O(logn). |
| Izvedba je preprosta, saj moramo slediti lastnostim binarnega iskanja, da vstavimo vozlišče. | Zapleteno je za implementacijo, ker moramo v drevesu AVL najprej zgraditi drevo AVL, nato pa moramo preveriti višinsko ravnotežje. Če je višina neuravnotežena, moramo izvesti nekaj vrtljajev, da uravnotežimo drevo. |
| BST ni uravnoteženo drevo, ker ne sledi konceptu faktorja ravnovesja. | Drevo AVL je višinsko uravnoteženo drevo, ker sledi konceptu faktorja ravnovesja. |
| Iskanje je v BST neučinkovito, če je v drevesu na voljo veliko število vozlišč, ker višina ni uravnotežena. | Iskanje je v drevesu AVL učinkovito, tudi če je v drevesu veliko vozlišč, ker je višina uravnotežena. |