2-3-4 medis

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

2-3-4 medis - duomenų struktūra, balansuotas 2-os eilės B-medis. Pirmasis tokį medį 1970 pasiūlė Džonas Hopkoftas. Kiekviena 2-3-4 medžio viršūnė turi nuo 2 iki 4 viršūnių, taip pat kiekviena viršūnė gali saugoti 1, 2 arba tris raktus (duomenų elementus).

[taisyti] Sąvybės

  1. visi lapai yra viename lygyje
  2. kiekviena vidinė viršūnė turi 2 arba 3 vaikus
  3. kiekviena viršūnė turi 1 arba 2 reikšmes
  4. medžio gylis yra tarp \lfloor \log_2{n} \rfloor ir \lceil \log_3{n} \rceil, kur n yra viršūnių skaičius

Viršūnės gali būti 3 rūšių:

2-tipo 
viršūnėje saugomas 1 duomenų elementas ir yra 2 rodyklės į vaikus. Kaip ir binariniame paieškos medyje, viename pomedyje yra mažesni duomenų elementai, kitame - didesni.
3-tipo 
viršūnėje saugomi 2 duomenų elementai ir yra 3 rodyklės į vaikus. Viena rodyklė — vaikams su mažesniais elementais, antra — elementams esantiems tarp viršūnės elementų, trečia — vaikams su didesniais elementais
4-tipo 
viršūnėje saugomi 3 duomenų elementai ir yra 4 rodyklės į vaikus. Dvi rodyklės vaikams su mažesniais ir didesniais elementais, kitos dvi rodyklės elementams, esantiems viršūnės raktais apibrėžtuose rėžiuose.

[taisyti] Operacijos

Įterpimo operacija
Enlarge
Įterpimo operacija

2-3-4 medžiuose labai efektyvios tiek paieškos, tiek ir įterpimo bei šalinimo operacijos. Įterpiant elementą, medis auga į viršų, ne į apačią, kaip dvejetainis medis. Įterpiant 2-tipo viršūnė virsta 3-tipo viršūne, 3-tipo viršūnė virsta 4-tipo viršūne, o 4-tipo viršūnė skyla į dvi viršūnes ir vieną iš vidurinių raktų perduoda tėvinei viršūnei.


Kitomis kalbomis