Lomljeno drevo

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vsebina

Definicija

Lomljena drevesa (splay trees) so binarna iskalna drevesa, ki se spremenijo (lomijo) ob vsaki operaciji:

  • iskanje elementa v drevesu: iskani element postane koren, če iskanega elementa ni v drevesu, potem postane koren zadnji element na poti,
  • vstavljanje elementa v drevo: element se vstavi v list drevesa; ko opravimo zaporedje transformacij postane koren drevesa,
  • brisanje elementa iz drevesa: element postane koren drevesa, nato ga po določenih postopkih odstranimo iz drevesa.

Posebnost: za izvedbo operacij na lomljenih drevesih vozlišče poleg podatka o obeh sinovih potrebuje tudi podatek o očetu.

Časovna zahtevnost posamezne operacije je v najslabšem primeru reda O(n). Če pa število operacij v zaporedju m narašča, je časovna zahtevnost izvajanja celotnega zaporedja operacij reda O(m*log n). Za posamezno operacijo pa nimamo zagotovljenega časa izvajanja, ker lahko te dolgo trajajo.

Lomljenje drevesa

Lomljenje drevesa premakne dani element v koren drevesa. Za lomljena drevesa se uporablja dvojne rotacije. Pri lomljenju lahko nastopijo štirje primeri:

  • če je iskani element v korenu, drevesa ni potrebno lomiti,
  • če je oče vozlišča z iskanim elementom koren drevesa, uporabimo enojno rotacijo nad vozliščem z iskanim elementom in očetom,
  • dvojne rotacije v isti smeri: če je oče B na isti strani kot stari oče A vozlišča z iskanim elementom X, potem z dvema zaporednima rotacijama postane vozlišče z elementom X koren poddrevesa, oče B njegov sin, stari oče A pa sin očeta.

Rotacije

Za lomljenje drevesa uporabljamo enojne in dvojne rotacije. Rotacije so postopki, ki zamenjajo vlogo sinov in očeta. Če je oče vozlišča, ki ga rotiramo koren, uporabljamo enojne rotacije. Dvojna rotacija je kombinacja dveh enojnih rotacij. Poznamo leve in desne rotacije. Leva rotacija je zrcalna desni rotaciji. Rotacije uporabljamo pri vstavljanju, brisanju in iskanju vozlišča z elementov X oziroma pri vsakem posegu v drevo.

Ločimo štiri primere:

  • če je iskani element v korenu, rotacija ni potrebna.

image:drevo1.jpg

  • če vozlišče z elementom X nima starega očeta, kar pomeni, da je oče koren drevesa, potem uporabimo enojno rotacijo in postopek je končan. Ločimo primer, ko je vozlišče z elementom X levi sin korena - desna rotacija in ko je vozlišče z elementom X desni sin korenskega vozlišča - leva rotacija.


Primer ko pride do desne rotacije. Vozlišče z elementom X postane novi koren, vozlišče z elementom P pa postane njegov desni sin. Če poddrevo označeno z b obstaja, ga pripnemo kot levo poddrevo vozlišča P.

image:drevo2.jpg

Leva rotacija je zrcalna slika desne rotacije.

  • če sta tako vozlišče z elementom X, kot tudi vozlišče z elementom P, oba leva oziroma oba desna sinova svojih očetov, izvedemo dvojno rotacijo. Dvakrat izvedemo isto enojno rotacijo (desno-desno in levo-levo rotacijo). Če sta tako vozlišče z elementom X in vozlišče z elementom P leva sinova svojih očetov, izvedemo dvojno desno-desno rotacijo. Dvojno desno-desno rotacijo izvedemo z dvema enojnima desnima zaporednima rotacijama. Prvo desno rotacijo izvedemo z vozlišči z elementoma P in G, drugo desno rotacijo pa izvedemo z vozlišči z elementoma X in P.

image:slika3.jpg

Levo-leva rotacija je zrcalna slika desno-desne rotacije.

  • če je element X na nasprotni strani očeta P, kot je oče glede na svojega očeta G, izvedemo dvojno levo-desna rotacijo, ki pride v poštev, če je vozlišče X desni sin vozlišča P, vozlišče P pa levi sin vozlišča G oziroma desno-leva rotacija v obratnem primeru. Dvojno levo-desno rotacijo izvedemo z dvema zaporednima enojnima rotacijama. Najprej izvedemo levo in nato desno rotacijo. Prvo levo rotacijo izvedemo z vozlišči X in P, drugo desno rotacijo pa izvedemo z vozlišči X in G.

image:slika4.jpg

Levo-desna rotacija je zrcalna slika desno-leve rotacije.

Primer 1:

image:Lomljenje1.JPEG

  • dvojne rotacije v različni smeri: če je element X na nasprotni strani očeta B kot je oče glede na svojega očeta A, potem najprej zarotiramo X z B, nato pa še z A. Tako postane element X oče A in B.

Primer 2:

image:Lomljenje2.JPEG

Primer 3:

Dano je iskalno drevo v katerega smo ravno vstavili vozlišče z elementom 12. To vozlišče premikamo proti korenu, dokler ne pride do korena nadaljujemo z rotacijami.

image:slika55.jpg

Vozlišče 12 ima za očeta vozlišče 13 in za starega očeta vozlišče 6. Ker je oče (vozlišče 13) desni sin starega očeta (vozlišča 6) in vozlišče 12 levi sin svojega očeta (vozlišča 13), izvedemo desno-levo rotacijo. Prvo desno rotacijo izvedemo z vozlišči 12 in 13.

image:slika5.jpg

Vozlišče 12 postane koren poddrevesa, vozlišče 13 pa njegov desni sin. Ker je vozlišče 13 desni sin svojega očeta (vozlišča 6), postane novi koren poddrevesa, vozlišče 12, desni sin vozlišča 6. nadaljujemo z levo rotacijo vozlišč 6 in 12.

image:slika6.jpg

Vozlišče 12 postane koren poddrevesa. Sedaj ima za očeta 5 in je njegov desni sin. Vozlišče 6 je postalo levi sin vozlišča 12. Tako smo zaključili desno-levo rotacijo.

image:slika7.jpg

Ker vozlišče 12 še ni v korenu drevesa nadaljujemo z rotacijami. Vozlišče 12 ima za očeta vozlišče 5 in za starega očeta vozlišče 11. Oba sinova v tej verigi sta desna sinova, zato izvedemo levo-levo rotacijo. Prvo levo rotacijo bomo izvedli z vozlišči 11 in 5.

image:slika8.jpg

Vozlišče 5 postane koren drevesa in nima več očeta (ustrezen kazalec postavimo na null). Vozlišče 11 postane levi sin vozlišča 5. Nadaljujemo z drugo levo rotacijo z vozlišči 12 in 5.

image:slika9.jpg

Vozlišče 12 postane koren drevesa (je brez očeta), vozlišče 5 pa postane njegov levi sin. Levi sin vozlišča 12, vozlišče 6, postane desni sin vozlišča 5. Vozlišče 12 je prišlo v koren drevesa in končamo z lomljenjem drevesa.

image:slika10.jpg


Iskanje elementa v drevesu

To je metoda, ki nam vrne true, če je iskalni element v drevesu, sicer false. V iskalnem drevesu iščemo po iskalni poti element, začnemo pri korenu in se premikamo proti listom.

  • če je element, ki ga iščemo enak elementu v korenu, postopek končamo
  • če je element manjši od elementa v korenu, postopek nadaljujemo v levem poddrevesu
  • če je element večjii od elementa v korenu, postopek nadaljujemo v desnem poddrevesu

Ustavimo se, ko najdemo element, ali ko pridemo do lista. Od najdenega elementa proti korenu lomimo drevo dokler ne pridemo do korena. Iskani element je v korenu transformiranega drevesa.

Primer 1:

V danem drevesu poiščimo element 19: image:Iskanje.JPEG

Primer 2:

Danjo je iskalno drevo

image:slika26.jpg

Iščemo vozlišče z elementom 4.

Ker je iskalni element (4) večji od elementa v korenu (3), gremo v desno poddrevo. Tukaj je element v korenu (10), ki je večji od iskalnega ementa (4), zato gremo levo poddrevo. Element v korenu (9) je večji od iskalnega elementa (4), iskanje nadaljujemo v levem poddrevesu. Tu v korenu najdemo vozlišče z elementom 4. Sedaj premaknemo s pomočjo lomljenja najdeno vozlišče 4 v koren drevesa.

Izvedemo desno-desno rotacijo. Prvo desno rotacijo izvedemo z vozlišči 9 in 10.

image:slika27.jpg

Nadaljujemo zopet z desno rotacijo z vozlišči 4 in 9.

image:slika28.jpg

Zaključili smo desno-desno rotacijo.

Sedaj je vozlišče 4 desni sin korena vozlišča 3 zato naredimo levo rotacijo z vozlišči 4 in 3.

image:slika29.jpg

Vozlišče 4 postane koren drevesa in končamo z lomljenjem drevesa.

Če iskalnega elementa ni v drevesu nam pomožna metoda za iskanje vrne kazalec na vozlišče z elementom, ki je bilo zadnje vozlišče na poti iskanja. Taga premaknemo v koren drevesa.


Primer 3:

Poišči vozlišče z elementom 5 v danem drevesu.

image:slika30.jpg

Tega elementa ni v drevesu. Pomožna metoda za iskanje nam vrne kazalec na vozlišče z elementom 6, ki je bilo zadnje vozlišče na poti iskanja. Taga premaknemo v koren drevesa. Vozlišče z elementom 6 ima za očeta vozlišče 10 in za starega očeta vozlišče 15. Oba sinova sta leva, zato za lomljenje uporabimo desno-desno rotacijo. Prvo desno rotacijo izvedemo z vozlišči 10 in 15.

image:slika31.jpg

Drugo desno rotacijo naredimo z vozlišči 6 in 10.

image:slika32.jpg

Vozlišče 6 postane koren drevesa in s tem končamo lomljenje.

Vstavljanje elementa v drevo

Element vedno dodamo kot nov list drevesa, tako da najprej poiščemo ustrezno mesto vstavljanja. Rekurzivno se sprehodimo po drevesu.

  • če je element, ki ga vstavljamo enak korenu drevesa smo s postopkom končali, ker v iskalnem dvojiškem drevesu ni podvojenih elementov, zato elementa ne vstavimo
  • če je element manjši od elementa v korenu , postopek nadaljujemo v levem poddrevesu
  • če je element večji od elementa v korenu postopek nadaljujemo v desnem poddrevesu.

Od korena navzdol se pomikamo do mesta kamor bomo vstavili element. Če pridemo do lista, ga vstavimo. Od tega mesta navzgor lomimo drevo dokler ne pridemo do korena. Vstavljen element je v korenu transformiranega drevesa.

Primer 1:

V drevo vstavljamo: 5, 15, 23, 19, 41, 16. image:Vstavljanje.JPEG

Primer 2:

Primer vstavljanja elementa v drevo. V začetku prazno lomljeno drevo bomo zaporedoma vstavljali elemente {5,10,2,16,7}.

1.korak: vstavimo 5, vozlišče 5 je v korenu drevesa, zato lomljenje drevesa ni potrebno.

image:slika11.jpg

2.korak: vstavimo 10, ker je element 10 večji od korena (vozlišča 5), ga vstavimo kot desni sin vozlišča 5.

image:slika12.jpg

Na vrsti je lomljenje. Vozlišče 10 ima za očeta koren (vozlišče 5) in je njegov desni sin. Uporabimo enojno levo rotacijo in postopek je končan.

image:slika13.jpg

3.korak: vstavimo 2, ker je manjši od korena (vozlišča 10) in od vozlišča 5, ga vstavimo kot levi sin vozlišča 5.

image:slika14.jpg

Vozlišče z elementom 2 ima za očeta vozlišče 5 in za starega očeta vozlišče 10. Oba sinova sta leva, zato za lomljenje uporabimo desno-desno rotacijo. Prvo desno rotacijo izvedemo z vozlišči 5 in 10.

image:slika15.jpg

Drugo desno rotacijo izvedemo z vozlišči 2 in 5. Po tej rotaciji je vozlišče v korenu drevesa in z lomljenjem drevesa končamo.

image:slika16.jpg

4.korak: vstavimo 16, vozlišče 16 je večji od korena zato nadaljujemo v desnem poddrevesu. Vstavimo ga kot desni sin vozlišča 10.

image:slika17.jpg

Vozlišče z elementom 16 ima za očeta vozlišče 10 in za starega očeta vozlišče 5. Nastopajo sami desni sinovi, zato za lomljenje uporabimo levo-levo rotacijo. Prvo levo rotacijo izvedemo z vozlišči 10 in 5.

image:slika18.jpg

Drugo levo rotacijo izvedemo z vozlišči 16 in 10.

image:slika19.jpg

Ker vozlišče 16 še ni v korenu, je pa desni sin korena (vozlišča 2), izvedemo levo rotacijo z vozlišči 16 in 2.

image:slika20.jpg

Vozlišče 16 smo pripeljali v koren drevesa, zato končamo z lomljenjem drevesa.

5.korak: vstavimo 4 kot levi sin vozlišča 5.

image:slikae.jpg


Vozlišče 4 ima za očeta vozlišče 5 in za starega očeta vozlišče 10. Vozlišči 4 in 5 sta oba leva sinova svojih očetov, zato izvedemo desno-desno rotacijo. Prvo desno rotacijo izvedemo z vozlišči 5 in 10.

image:slikaa.jpg

Drugo desno rotacijo izvedemo z vozlišči 4 in 5.

image:slikaaa.jpg

Zaključili smo desno-desno rotacijo. Vidimo, da vozlišče 4 še ni v korenu in ima za očeta vozlišče 2 in za starega očeta vozlišče 16. Ker je vozlišče 2 levi sin starega očeta vozlišča 16 in vozlišče 4 desni sin svojega očeta vozlišča 2, izvedemo levo-desno rotacijo. Prvo levo rotacijo izvedemo z vozlišči 2 in 4.

image:slikaaaa.jpg

Drugo desno rotacijo izvedemo z vozlišči 4 in 16.

image:slikaaaaa.jpg

Vozlišče 4 postane koren drevesa. Ker smo vstavili že vse elemente smo s postopkom končali.

Brisanje elementa iz drevesa

V iskalnem drevesu poiščemo element. Z lomljenjem drevesa ga postavimo v koren. Če je katero od poddreves prazno, lahko element preprosto zbrišemo sicer pa spremenimo levo poddrevo tako, da z lomljenjem dvignemo v koren maksimalni element levega poddrevesa. To dosežemo tako, da pokličemo funkcijo za iskanje elementa, ki se nahaja v korenu in ga torej ni v levem poddrevesu. Ko je levo poddrevo spremenjeno, je v korenu levega poddrevesa maksimalen element, torej nima desnega sina. Za desnega sina lahko uporabimo desno poddrevo celotnega drevesa. S tem levo poddrevo postane novo drevo in je element zbrisan.

Primer 1:

Iz danega drevesa odstranimo element 5. image:Brisanje.JPEG


Ločimo štiri primere pri brisanju elementa v drevesu:

  • drevo je prazno
  • če je levo poddrevo korena prazno, postane desni sin koren drevesa in element je izbrisan. Če pa je prazno desno poddrevo, vlogo korena dobi levi sin.

Primer 2:

Iz danega drevesa izbrišemo element 10.

image:slika33.jpg

Našli smo vozlišče z elementom 10 in ga z lomljenjem prestavili v koren drevesa.

image:slika34.jpg

Ker je levo poddrevo prazno, levi sin (vozlišče 14), postane novi koren drevesa. S tem je vozlišče 10 izbrisano iz drevesa.

image:slika35.jpg

  • če ni ne levo in ne desno poddrevo prazno, v levem poddrevesu poiščemo vozlišče z maksimalnim elementom. Tega z lomljenejm premaknemo v koren levega poddrevesa korena. V korenu drevesa imamo sedaj vozlišče, ki ga želimo izbrisati, njegov levi sin pa je vozlišče z maksimalnim elementom levega poddrevesa. V tem levem poddrevesu desnega podrevesa ni, saj je v korenu maksimalni element. Koren drevesa zbrišemo tako, da desno poddrevo korena postane desno poddrevo levega sina korena drevesa, levi sin korena pa postane novi koren drevesa.

Primer 3:

Izbrišemo element 20.

image:slika36.jpg

Poiščemo vozlišče z elementom 20 in ga premaknemo v koren drevesa.

image:slika37.jpg

Vozlišče 20 je v korenu drevesa. Ker levo poddrevo ni prazno, poiščemo maksimalni element v levem poddrevesu. To je vozlišče 15. Z lomljenjem ga premaknemo v koren levega poddrevesa.

image:slika38.jpg

Vozlišče 20, ki ga bomo izbrisali iz drevesa, je v korenu in maksimalno vozlišče levega poddrevesa je njgov levi sin. Desno poddrevo s korenom vozliščem 25 postane desno poddrevo vozlišča 15. Koren levega poddrevesa (vozlišče 15), postane novi koren in vozlišče 20 je izbrisano iz drevesa.

image:slika39.jpg

  • Iz drevesa želimo izbrisati element, ki ga ni v drevesu

Primer 4:

Dano imamo iskalno drevo, izbrišemo element 6.

image:slika40.jpg

Vozlišča z elementom 6 ni v drevesu. Zato lomimo drevo z zadnjim vozliščem na poti iskanja z vozliščem 5. Ko je vozlišče 5 v korenu končamo.

image:slika41.jpg


Aktivne povezave

Glej tudi

Osebna orodja