2-3 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

2-3 drevesa so popolnoma poravnana drevesa. Imajo naslednje lastnosti:

  1. Elementi so shranjeni samo v listih drevesa.
  2. Vsako notranje vozlišče ima dva ali tri sinove ter en ali dva ključa. Prvi ključ je ključ najmanjšega elementa v poddrevesu, katerega koren je drugi sin, drugi ključ pa je ključ najmanjšega elementa v poddrevesu, katerega koren je tretji sin.
  3. Vsi listi so na istem nivoju.

Prazno drevo je tudi 2-3 drevo in isto velja za drevo z enim vozliščem - listom, ki vsebuje en element. Zaradi preprostosti bomo predpostavili, da so elementi sestavljeni samo iz ključev.

Vstavljanje elementa v 2-3 drevo

Vstavljanje v prazno drevo ali v drevo z enim elementom je preprosto. V prvem primeru dobimo en list, v drugem pa drevo z enim notranjim vozliščem in dvema sinovoma. V splošnem pa pri vstavljanju elementa poiščemo najprej očeta listov, kjer naj bi se element vstavil. Možna sta dva primera:

  1. Če ima oče samo dva sinova, vrinemo novi element na ustrezno mesto, tako da ima oče tri sinove. Ko ustrezno popravimo še ključa, je postopek končan. Ključev po drevesu navzgor ni potrebno spreminjati, saj algoritem iskanja elementa zagotavlja,da se najmanjši element v drugem in tretjem poddrevesu ne more spremeniti med vstavljanjem novega elementa.
  2. Če ima oče tri sinove, potem tvorimo novo notranje vozlišče (strica), tako da si oče in stric delita vsak po dva sina ter ustrezno popravimo ključe. Zatem rekurzivno ponovimo dodajanje vozlišča en nivo višje, tj. dodamo strica kot sina k staremu očetu (očetu od očeta). Rekurzija se izteče bodisi pri 1. točki, če ima stari oče samo dva sina, ali pa v primeru, ko starega očeta ni, tj. ko je oče koren drevesa. V tem primeru tvorimo nov koren drevesa (novega starega očeta), ki dobi za sinova očeta in strica. S tem se višina drevesa poveča za en nivo.
    • Primer vstavljanja elementa, ko ima oče dva sinove:

    • Primer vstavljanja elementa, ko ima oče tri sinove:


    Brisanje elementa iz 2-3 drevesa

    Ko element najdemo, ga izbrišemo. Imamo tri možnosti:

    1. Če je oče zbrisanega vozlišča imel prej tri sinove, premaknemo drugega dva sina tako, da postaneta prvi in drugi z leve ter ustrezno uredimo ključe po drevesu navzgor. Če pa je oče imel prej samo dva sina, potem imamo še dve možnosti:
    2. Če ima kateri od sosednjih očetovih bratov tri sinove, potem vzamemo bližnjega sina in ga priključimo na ustrezno mesto k očetu. Pri tem je potrebno ustrezno spremeniti ključe. S tem je postopek končan.

    • Če iz zgornjega drevesa odstranimo element 7 dobimo:

    • Če odstranimo element 8, pa dobimo:

  3. Če nobeden od očetovih bratov nima treh sinov, priključimo preostalega očetovega sina enemu od bratov kot tretjega sina ter očeta zbrišemo. Sedaj celi postopek rekurzivno ponovimo pri starem očetu (tj. očetovem očetu, ki smo mu zbrisali enega od sinov). Postopek se konča bodisi pri 1. ali 2. točki ali pa ostane koren drevesa z enim samim sinom. V slednjem primeru zbrišemo koren in njegov sin postane novi koren drevesa. S tem se višina drevesa zmanjša za en nivo.

  • Na zgorji sliki smo odstranili element 8, korenu ostane samo en sin, koren izbrišemo in nivo drevesa se zmnajša za ena. Dobimo drevo oblike:

Primer uporabe

  • Primer, kako poteka posamezen korak za dana števila: 11,29,41,27,17,99,1,8,40

1.korak: vstavimo 11

2.korak: vstavimo 29

3.korak: vstavimo 41

4.korak: vstavimo 27

5.korak: vstavimo 17

6.korak: vstavimo 99

7.korak: vstavimo 1

8.korak: vstavimo 8

9.korak: vstavimo 40 in dobimo končno 2-3 drevo


Glej tudi

Osebna orodja