2-3-4 medis

2-3-4 medis – savaime susibalansuojanti duomenų struktūra, naudojama efektyviam žodyno paieškos ir kitų panašių algoritmų programavimui. Tai balansuotas 2-os eilės B-medis. Pirmasis tokį medį 1970 m. pasiūlė . 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).

2-3-4 medžio viršūnės

Savybė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 ${\displaystyle \lfloor \log _{2}{n}\rfloor }$ ir ${\displaystyle \lceil \log _{3}{n}\rceil }$, kur n yra viršūnių skaičius

Viršūnių rūšys

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.

Operacijos

Į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.

Šaltiniai

1. (1998). Sorting and Searching. . 3 (Second leid.). Addison–Wesley. ISBN .. Skyrius 6.2.4: Multiway Trees, psl. 481–491. Taip pat ir skyrius 6.2.3 (psl. 476–477)(„subalansuoti medžiai“) aptaria 2-3 medžius.