2-3-4 (ali 2-4) drevo je primer iskalnega drevesa (ne dvojiškega):

2-3-4 drevo je tudi B - drevo, reda 4. Torej ima vsako vozlišče lahko 2, 3 ali 4 sinove in en element manj kot ima sinov.

Podobno kot pri B – drevesu, tudi pri 2-3-4 lahko elemente iščemo, brišemo ali vstavimo. Vse te operacije pa se izvedejo v času, ki je lahko največ reda O(logn), kjer je n število vozlišč v drevesu.

2-3-4 drevo je prazno ali pa izpolnjuje naslednje pogoje:

• v vsakem vozlišču so lahko največ trije elementi,
• vsako vozlišče lahko ima najmanj dva in največ štiri sinove,

• naj bosta sinL in sinD sinova vozlišča z enim elementom, ki ga označimo z A. Vsi elementi v poddrevesu z očetom sinL so manjši od A in vsi elementi v poddrevesu z očetom sinD so večji od A,

  

• naj bodo sinL, sinS in sinD trije sinovi vozlišča z dvema elementoma, in sicer A in B. Vsi elementi v poddrevesu z očetom sinL, so manjši od A. Za vse elemente v poddrevesu z očetom sinS velja, da so manjši od B in večji od A. Ter vsi elementi, ki so v poddrevesu z očetom sinR, so večji od B,

  

• podobno za primer vozlišča s tremi elementi,

  
• vsi listi so na istem nivoju.

Iskanje elementa v 2-3-4 drevesu je zelo podobno iskanju elementa v dvojiškem iskalnem drevesu. Z iskanjem začnemo v korenu drevesa. Razlika je samo v tem, da pri dvojiškem drevesu primerjamo samo z enim elementom, pri 2-3-4 drevesu pa zaporedoma primerjamo z elementi, ki so v danem vozlišču. Če iskalni element ni v trenutnem vozlišču, določimo pot (po katerem sinu) po kateri nadaljujemo z iskanjem. Za to je dovolj, da najdemo dva elementa v vozlišču, ki označujeta območje v katerem se nahaja iskalni element. Po pripetem sinu med tema dvema elementoma, nadaljujemo pot iskanja. Če v drevesu ni sina z območjem, to drevo ne vsebuje iskalnega elementa.

Primer:
V danem 2-3-4 drevesu poišči elementa 57 in 75.

• Z iskanjem elementa 57 začnemu v korenu danega drevesa. Pogledamo element, ker je ta večji kot 26, z iskanjem nadaljujemo v desnem poddrevesu, kjer so vsi elementi večji od 26. Pogledamo elemente v naslednjem vozlišču. Ker se iskalni element nahaja med 33 in 67 nadaljujemo z iskanjem v sredinskem vozlišču. Pogledamo to vozlišče in pridemo do iskalnega elementa.
• Podobno začnemo z iskanjem elementa 75. Ko pridemo do vozlišča z elementoma 70 in 90, bi nadaljevali z iskanjem v sredinskem vozlišču. Vendar je to vozlišče prazno, zato se iskalni element ne nahaja v danem drevesu.

Podobno kot pri operaciji iskanje, začnemo v korenu drevesa.

1. Če trenutno vozlišče vsebuje tri elemente:

• sredinski element vstavimo v očeta, ostala dva elementa pa razpadeta v dve vozlišči. Prvi element postane levi sin, drugi element pa desni z ustreznima poddrevesoma,
• če je trenutno vozlišče koren drevesa, sredinski element postane nov koren drevesa. S tem višina drevesa naraste za ena. Sicer (če trenutno vozlišče ni koren) pa sredinski element vstavimo v očeta trenutnega vozlišča.

2. Poiščemo sina, kateri ustreza intervalu števila, ki ga želimo vstaviti.

3. Če je sin vozlišča iz 2. točke prazno vozlišče, vstavimo element v trenutno vozlišče. Sicer pa nadaljujemo na naslednjem ustreznem sinu in ponovimo vse od 1. točke.

Najprej v prazno drevo vstavimo element 8. Dobimo vozlišče z enim elementom. Potem temu elementu na ustrezno mesto dodamo element 3. Vstavljanje elementa 3 je preprosto, saj vozlišče vsebuje manj kot tri elemente. Podobno vstavimo tudi element 15.

Ko pa želimo vstaviti element 21, pa trenutno vozlišče (ki je hkrati tudi koren) vsebuje tri elemente. Torej sredinski element (t.j. 8) postane nov koren drevesa. Element 3 postane njegov levi sin, element 15 pa desni. Sedaj poiščemo sina, ki ustreza intervalu števila 21. Ustrezen je desni sin, ker je 21 večje od 15. Ker je sin vozlišča z elementom 15 prazen, element 21 vstavimo v to vozlišče.

Recimo da želimo vstaviti še element 16. Začnemo v korenu drevesa. Ker ta ne vsebuje tri elemente, poiščemo ustreznega sina. To je desni sin, ker je element 16 večji od 8. Ker ta sin vsebuje dva elementa, element 16 preprosto dodamo na ustrezno mesto.

V dano 2-3-4 drevo želimo vstaviti element 75. Začnemo v korenu drevesa. Ker že ta vsebuje tri elemente, sredinski element postane nov koren drevesa. Njegov levi sin je vozlišče z elementom 30, ki dobi levo in desno poddrevo. V levem poddrevesu so elementi, ki so manjši od 30, v desnem pa elementi, ki so med 30 in 35. Desni sin vozlišča z elementom 35, pa je vozlišče z elementom 67, ki ima tudi ustrezni poddrevesi (podobno kot levi sin).

Ker je element 75 večji od 67, nadaljujemo z vstavljanjem v desnem sinu tega vozlišča. Ker ta spet vsebuje tri elemente, naredimo podoben postopek kot prej. Sredinski element 80 vstavimo v koren tega vozlišča. Ker koren obstaja, ga preprosto dodamo. Vozlišče z elementoma 67 in 80 pa razpade na dve vozlišči. Ker je sedaj element 75 med 67 in 80 nadaljujemo v sredinskem sinu. Ker to vozlišče nima več sinov, element 75 preprosto dodamo.

Operacija brisanje je težja kot operaciji iskanje in vstavljanje.

Najprej element, ki ga želimo zbrisati, poiščemo. Element, ki ga želimo izbrisati se mora nahajati v listu drevesa. Sedaj ločimo dva primera:

• Če se element, ki ga želimo izbrisati, nahaja v vozlišču z dvema ali tremi elementi, ga preprosto zbrišemo in postopek je končan,

• Če pa je element, ki ga želimo izbrisati, edini v vozlišču, pa nastopi ena izmed naslednjih dveh možnosti:

1. Vsaj eden izmed bratov vsebuje najmanj 2 elementa. Najprej element, ki ga želimo zbrisati, zbrišemo in tako dobimo prazno vozlišče. Potem vzamemo ustrezen element iz očeta tega vozlišča in ga vstavimo v prazno vozlišče. Nato pa iz sosednjega brata vzamemo ustrezen element in ga vstavimo v očeta.

2. Noben od bratov nima vsaj dveh elementov. Potem ustrezen element odstranimo. Tako dobimo prazno vozlišče, v katerega pa shranimo utrezni element iz očeta. Potem pa to vozlišče združimo z ustreznim bratom.

V primeru, da se element, ki ga želimo zbrisati ne nahaja v listu drevesa, ga nadomestimo z maksimalnim elementom ustreznega levega poddrevesa.

Po vseh teh zamenjavah elementov in združevanju vozlišč, drevo še vedno ostane iskalno.

Iz danega 2-3-4 želimo izbrisati element 20. Ker se ta nahaja v listu drevesa, ga preprosto odstranimo. Tako dobimo prazno vozlišče. Potem pa pogledamo brata tega vozišča. Ker ta vsebuje tri elemente, bomo element 10 zapisali v koren drevesa. Element v korenu (t.j. 12), pa zapišemo v prazno vozlišče. Potem preverimo, če je dobljeno drevo iskalno. Pogledamo element v korenu drevesa. Ta je enak 10. Ker sta v levem sinu elementa manjša od 10, v desnem pa je elment večji, je to drevo še vedno iskalno.

Iz danega drevesa želimo izbrisati element 3. Ker se ta spet nahaja v listu drevesa, ga odstranimo in tako dobimo prazno vozlišče. Potem pogledamo brata tega vozlišča. Ker ta vsebuje samo en element, ne moremo vzeti element iz korena, ker potem dobimo preveč otrok. V tem primeru vzamemo ustrezen element iz korena (t.j. 8), in ga vstavimo v prazno vozlišče. Potem pa to vozlišče združimo z bratom. Spet preverimo, če je dobljeno drevo iskalno. Ker so v levem vozlišču elementi manjši od elementa v korenu in v desnem večji, je drevo še vedno iskalno.

Iz danega 2-3-4 drevesa želimo izbrisati element 94. Najprej vozlišče z elementom 94 poiščemo.

Ker se element nahaja v listu drevesa, ga odstranimo. Dobimo prazno vozlišče v katerega prenesemo element iz korena tega vozlišča (t.j. 89).

Potem pogledamo brata tega vozlišča. Ker ima ta samo en element, bomo združili ti dve vozlišči. Oče združenega vozlišča je prazen.

Ker je sedaj oče združenega vozlišča prazen, ponovimo postopek. Torej prenesemo element v korenu tega vozlišča v prazno vozlišče.

Sedaj pa moramo združiti brata s tremi elementi in vozlišče v katerega smo prenesli element 67. Ker brat vsebuje že tri elemente, četrtega ne morema dodati. Zato sredinski element v bratu prenesemo v koren drevesa, element 45 pa dodamo vozlišču z elementom 67. Dobimo spodaj prikazano drevo.

Podobno kot v prejšnjih dveh primerih bi preverili, če je dobljeno drevo iskalno.

V danem 2-3-4 drevesu želimo izbrisati element 25. Ker se ta ne nahaja v listu drevesa, ga nadomestimo z maksimalnim elementom v ustreznem levem poddrevesu. Ustrezno levo poddrevo tega vozlišča, je drugo vozlišče z elementoma 17 in 20 (ker gledamo levo poddrevo elementa 25).

Maksimalen element v drugem vozlišču je element 20. Tega zapišemo v koren namesto elementa 25. Tako smo element 25 izbrisali. Ker vozlišče iz katerega smo prenesli element, ni prazno je postopek končan.

Recimo da želimo odstraniti še element 16. Ker se ta spet nahaja v korenu drevesa, ga nadomestimo z maksimalnim elementom ustreznega levega podrevesa.

To ustrezno levo poddrevo je vozlišče z elementom 13. Ker je ta en sam, je to hkrati maksimalni element. Nadomestimo ga z elementom 16. Ker je sedaj eno vozlišče prazno, moramo to vozlišče združiti z njegovim bratom. To naredimo tako, da prenesemo ustrezen element iz korena (t.j. 13) in ga združimo z 17. Na koncu še preverimo če je dobljeno drevo iskalno.

Če imamo dano 2-3-4 drevo in bi rajši delali z rdeče - črnimi drevesi, lahko naredimo naslednjo preslikavo:

1. vozlišče s tremi elementi preslikamo v tri vozlišča. Črno (ki kot podatek vsebuje srednji element) je oče rdečima sinovoma. Ta imata za poddrevesi vsak po dve prvotni poddrevesi.

   

2. vozlišče z dvema elementoma preslikamo v dve vozlišči. Črno, v katerega damo en element iz prvotnega vozlišča. Ta je oče rdečemu sinu, v katerega damo preostali element iz prvotnega vozlišča, in enemu prvotnemu poddrevesu. Rdeči sin ima za poddrevesi ustrezni prvotni poddrevesi.

   
3. vozlišče z enim elementom (ki je lahko samo koren), preslikamo v črno vozlišče s prvotnima poddrevesoma

S tem postopkom dobimo vsaj eno rdeče - črno drevo. Obratno pa preslikava ni enolična.

Pogoj rdeče – črnih dreves:

• koren drevesa je črno vozlišče,
• rdeče vozlišče ima lahko samo črna sinova,
• za vsako zunanje vozlišče mora veljati, da pot od tega vozlišča do korena vsebuje enako število črnih vozlišč.

Več o rdeče - črnih drevesih: //en.wikipedia.org/wiki/Red-black_tree

2-3-4 drevo je

Če se pri operaciji brisanje element, ki ga želimo izbrisati, ne nahaja na zadnjem nivoju, ga nadomestimo z:

Katera od naslednjih trditev je pravilna?

Preveri

• Igor Kononenko, Marko Robnik Šikonja: Algoritmi in podatkovne strukture, Ljubljana 2003
• //en.wikipedia.org/wiki/2-3-4_tree
• //www.scribd.com/doc/23817352/2-3-4-and-Red-Black-Tree
• //ultrastudio.org/en/2-3-4_tree
• //www.worldlingo.com/ma/multilingual_archive.html
• //www.cs.purdue.edu/homes/ayg/CS251/slides/chap13b.pdf
• //www.cs.princeton.edu/~rs/AlgsDS07/09BalancedTrees.pdf
• //www.serc.iisc.ernet.in/~viren/Courses/2010/SE286/Lecture16.pdf