2-3-4 stablo

U računarstvu, 2–3–4 stablo (takođe nazivano i 2–4 stablo) je samo-balansirajuća struktura podataka koja se obično koristi za implementaciju rečnika. Brojevi znače da se radi o stablu gde svaki čvor sa decom (unutrašnji čvor) ima dva, tri, ili četiri deteta čvora:

• 2-čvorni sadrži jedan podatak, i ako je unutrašnji ima dva deteta čvora;
• 3-čvorni sadrži dva podatka, i ako je unutrašnji ima tri deteta čvora;
• 4-čvorni sadrži tri podatka, i ako je unutrašnji ima četiri deteta čvora.

• 
  2-čvorni
• 
  3-čvorni
• 
  4-čvorni

2–3–4 stabla su B-stabla četvrtog reda Knuth 1998; kao i B-stabla, mogu da pretražuju, ubacuju, i brišu u O (log n) vremenu. Jedna osobina 2–3–4 stabla je da su svi spoljašnji čvorovi na istoj dubini.

2–3–4 stabla su izometrija crveno-crnih stabala, što znači da su ekvivalentne strukture podataka. Drugim rečima, za svako 2–3–4 stablo, postoji bar jedno crveno-crno stablo sa podacima u istom redosledu. Štaviše, operacije umetanja i brisanja na 2–3–4 stablima koje uzrokuju proširenja, deljenja i spajanja čvorova su ekvivalentne obrtanju boja i rotacijama u crveno-crnim stablima. Kada se uče crveno-crna stabla, obično se nauče 2-3-4 stabla prvo, jer su konceptualno jednostavnija. 2–3–4 stabla, međutim, mogu biti teška za implementaciju u mnogim programskim jezicima zbog velikog broja specijalnih slučajeva uključenih u operacijama nad stablom. Crveno-crna stabla su lakša za implementaciju, pa imaju tendenciju da budu korišćena umesto 2-3-4 stabala.

Osobine

• Svaki čvor (list ili unutrašnji) je 2-čvorni, 3-čvorni ili 4-čvorni, i sadrži jedan, dva, ili tri podatka, tim redom.
• Svi listovi su na istoj dubini (poslednji nivo).
• Svi podaci se čuvaju u sortiranom redosledu.

Umetanje

Da bi ubacili vrednost, počinjemo u korenu 2–3–4 stabla:

1. Ako je trenutni čvor 4-čvorni:
   • Uklonimo i sačuvamo srednju vrednost da bi dobili 3-čvorni.
   • Podelimo preostali 3-čvorni u par 2-čvornih.
   • Ako je ovo koren (koji, ako je tako, nema roditelje):
     • Srednja vrednost postaje koren 2-čvornog i visina drveta se povećava za 1. Penjemo se u koren.
   • Inače, guramo srednju vrednost u roditeljski čvor. Penjemo se u roditeljski čvor.
2. Nađemo dete čiji interval sadrži vrednost koja treba da bude umetnuta.
3. Ako je dete list, umetnemo vrednost u dete čvor i završimo.
   • Inače, spustimo se u dete i ponovimo od koraka 1.

Primer

Umetnuti vrednost "25" u dato 2–3–4 stablo:

• Počinjemo u korenu (10, 20) i spuštamo se ka najdesnijem detetu (22, 24, 29). (Njegov interval (20, ∞) sadrži 25.)
• Čvor (22, 24, 29) je 4-čvorni, pa njegov srednji element 24 guramo u roditeljski čvor.

• Preostali 3-čvorni (22, 29) delimo u par 2-čvornih (22) i (29). Dižemo se nazad u novog roditelja (10, 20, 24).
• Spuštamo se ka najdesnijem detetu (29). (Njegov interval (24 - 29) sadrži 25.)

• Čvor (29) nema najlevlje dete. (Dete za interval (24 - 29) je prazno.) Stajemo ovde i ubacujemo vrednost 25 u ovaj čvor.

Brisanje

Razmotrite da samo ostavite element gde jeste, obeležite ga “obrisan”, da bi, možda, bio iskorišćen za neko buduće umetanje.

Da bi izbrisali vrednost iz 2–3–4 stabla:

1. Nađemo element za brisanje.
   • Ako element nije list, zapamtimo njegovu lokaciju i nastavimo potragu dok ne naićemo na list, koji sadrži naslednika elementa koji tražimo. Naslednik može da bude ili najveći ključ koji je manji od onog koji se briše, ili najmanji ključ koji je veći od onog koji se briše. Najjednostavnije je prilagoditi stablo tako da kada naiđemo na list, on ne bude 2-čvorni. U tom slučaju, nakon razmene, neće postojati prazan list.
   • Ako je element u 2-čvornom listu, samo izvršiti ova prilagođavanja:

Izvršiti ova prilagođavanja ako naiđemo na 2-čvorni - osim korena - na putu do lista koji želimo da uklonimo:

1. Ako je brat sa bilo koje strane čvora 3-čvorni ili 4-čvorni (pa ima više od jednog ključa), izvršiti rotaciju sa tim bratom:
   • Ključ od drugog brata najbližeg datom čvoru se pomera do roditeljskog ključa koji nadgleda ta dva čvora.
   • Roditeljski ključ se pomera dole do datog čvora da formira 3-čvorni.
   • Dete koje je originalno bilo sa ključem rotiranog brata je sada dodatno dete ovog čvora.
2. Ako je roditelj 2-čvorni i brat je takođe 2-čvorni, spojiti sva tri elementa da se formira novi 4-čvorni i skrati se drvo. (Ovo pravilo se može upotrebiti samo ako je roditelj 2-čvorni koren, pošto su svi drugi 2-čvorni since all other 2-nodes usput modifikovani da ne budu 2-čvorni. Zbog ovoga „skrati se drvo“ ovde čuva balans; Ovo je takođe važna pretpostavka za operaciju fuzije.)
3. Ako je roditelj 3-čvorni ili 4-čvorni i sva braća su 2-čvorni, uraditi operaciju fuzije sa roditeljom i susednim bratom:
   • Susedni brat i roditeljski ključ koji nadgleda dva susedna čvora se spajaju da formiraju 4-čvorni.
   • Prebaciti bratovu decu na ovaj čvor.

Kada je tražena vrednost nađena, može biti postavljena na lokaciju izbrisane vrednosti bez problema, jer smo se postarali da list ima više od jednog ključa.

Brisanje u 2–3–4 stablu je O(log n), ako pretpostavimo da za prebacivanje i fuziju treba konstantno vreme ( O(1) ).

Vidi još

• 2–3 stablo
• Crveno–crno stablo
• B stablo

Literatura

• Goodrich, Michael T; Tamassia, Roberto; Mount, David M (2002). Data Structures and Algorithms in C++. Wiley. ISBN 978-0-471-20208-0. 
• Ford, William; Topp, William (2002). Data Structures with C++ Using STL (2nd izd.). New Jersey: Prentice Hall. str. 683. ISBN 978-0-13-085850-4. 
• Knuth, Donald (1998), Sorting and Searching, The Art of Computer Programming, Volume 3 (Second izd.), Addison-Wesley, ISBN 978-0-201-89685-5 . Section 6.2.4: Multiway Trees. str. 481–491. Also. str. 476–477 of section 6.2.3 (Balanced Trees) discusses 2-3 trees.

Spoljašnje veze

• Animacija 2-3-4 stabla
• Java aplet koji pokazuje 2-3-4 stablo
• Otvorene strukture podataka – Sekcija 9.1 – 2–4 stabla