2-3-4 стабло

Из Википедије, слободне енциклопедије

У рачунарству, 2–3–4 стабло (такође називано и 2–4 стабло) је само-балансирајућа структура података која се обично користи за имплементацију речника. Бројеви значе да се ради о стаблу где сваки чвор са децом (унутрашњи чвор) има два, три, или четири детета чвора:

  • 2-чворни садржи један податак, и ако је унутрашњи има два детета чвора;
  • 3-чворни садржи два податка, и ако је унутрашњи има три детета чвора;
  • 4-чворни садржи три податка, и ако је унутрашњи има четири детета чвора.

2–3–4 стабла су Б-стабла четвртог реда (Knuth 1998); као и Б-стабла, могу да претражују, убацују, и бришу у O (log n) времену. Једна особина 2–3–4 стабла је да су сви спољашњи чворови на истој дубини.

2–3–4 стабла су изометрија црвено-црних стабала, што значи да су еквивалентне структуре података. Другим речима, за свако 2–3–4 стабло, постоји бар једно црвено-црно стабло са подацима у истом редоследу. Штавише, операције уметања и брисања на 2–3–4 стаблима које узрокују проширења, дељења и спајања чворова су еквивалентне обртању боја и ротацијама у црвено-црним стаблима. Када се уче црвено-црна стабла, обично се науче 2-3-4 стабла прво, јер су концептуално једноставнија. 2–3–4 стабла, међутим, могу бити тешка за имплементацију у многим програмским језицима због великог броја специјалних случајева укључених у операцијама над стаблом. Црвено-црна стабла су лакша за имплементацију,[1] па имају тенденцију да буду коришћена уместо 2-3-4 стабала.

Особине[уреди]

  • Сваки чвор (лист или унутрашњи) је 2-чворни, 3-чворни или 4-чворни, и садржи један, два, или три податка, тим редом.
  • Сви листови су на истој дубини (последњи ниво).
  • Сви подаци се чувају у сортираном редоследу.

Уметање[уреди]

Да би убацили вредност, почињемо у корену 2–3–4 стабла:

  1. Ако је тренутни чвор 4-чворни:
    • Уклонимо и сачувамо средњу вредност да би добили 3-чворни.
    • Поделимо преостали 3-чворни у пар 2-чворних.
    • Ако је ово корен (који, ако је тако, нема родитеље):
      • Средња вредност постаје корен 2-чворног и висина дрвета се повећава за 1. Пењемо се у корен.
    • Иначе, гурамо средњу вредност у родитељски чвор. Пењемо се у родитељски чвор.
  2. Нађемо дете чији интервал садржи вредност која треба да буде уметнута.
  3. Ако је дете лист, уметнемо вредност у дете чвор и завршимо.
    • Иначе, спустимо се у дете и поновимо од корака 1.[2][3]

Пример[уреди]

Уметнути вредност "25" у дато 2–3–4 стабло:

2-3-4 tree insert 1.svg
  • Почињемо у корену (10, 20) и спуштамо се ка најдеснијем детету (22, 24, 29). (Његов интервал (20, ∞) садржи 25.)
  • Чвор (22, 24, 29) је 4-чворни, па његов средњи елемент 24 гурамо у родитељски чвор.
2-3-4 tree insert 2.svg
  • Преостали 3-чворни (22, 29) делимо у пар 2-чворних (22) и (29). Дижемо се назад у новог родитеља (10, 20, 24).
  • Спуштамо се ка најдеснијем детету (29). (Његов интервал (24 - 29) садржи 25.)
2-3-4 tree insert 3.svg
  • Чвор (29) нема најлевље дете. (Дете за интервал (24 - 29) је празно.) Стајемо овде и убацујемо вредност 25 у овај чвор.
2-3-4 tree insert 4.svg

Брисање[уреди]

Размотрите да само оставите елемент где јесте, обележите га “обрисан”, да би, можда, био искоришћен за неко будуће уметање.

Да би избрисали вредност из 2–3–4 стабла:

  1. Нађемо елемент за брисање.
    • Ако елемент није лист, запамтимо његову локацију и наставимо потрагу док не наићемо на лист, који садржи наследника елемента који тражимо. Наследник може да буде или највећи кључ који је мањи од оног који се брише, или најмањи кључ који је већи од оног који се брише. Најједноставније је прилагодити стабло тако да када наиђемо на лист, он не буде 2-чворни. У том случају, након размене, неће постојати празан лист.
    • Ако је елемент у 2-чворном листу, само извршити ова прилагођавања:

Извршити ова прилагођавања ако наиђемо на 2-чворни - осим корена - на путу до листа који желимо да уклонимо:

  1. Ако је брат са било које стране чвора 3-чворни или 4-чворни (па има више од једног кључа), извршити ротацију са тим братом:
    • Кључ од другог брата најближег датом чвору се помера до родитељског кључа који надгледа та два чвора.
    • Родитељски кључ се помера доле до датог чвора да формира 3-чворни.
    • Дете које је оригинално било са кључем ротираног брата је сада додатно дете овог чвора.
  2. Ако је родитељ 2-чворни и брат је такође 2-чворни, спојити сва три елемента да се формира нови 4-чворни и скрати се дрво. (Ово правило се може употребити само ако је родитељ 2-чворни корен, пошто су сви други 2-чворни since all other 2-nodes успут модификовани да не буду 2-чворни. Због овога „скрати се дрво“ овде чува баланс; Ово је такође важна претпоставка за операцију фузије.)
  3. Ако је родитељ 3-чворни или 4-чворни и сва браћа су 2-чворни, урадити операцију фузије са родитељом и суседним братом:
    • Суседни брат и родитељски кључ који надгледа два суседна чвора се спајају да формирају 4-чворни.
    • Пребацити братову децу на овај чвор.

Када је тражена вредност нађена, може бити постављена на локацију избрисане вредности без проблема, јер смо се постарали да лист има више од једног кључа.

Брисање у 2–3–4 стаблу је O(log n), ако претпоставимо да за пребацивање и фузију треба константно време ( O(1) ).[2][4]

Види још[уреди]

Референце[уреди]

  1. ^ Sedgewick, Robert (2008). „Left-Leaning Red-Black Trees“. Left-Leaning Red-Black Trees. Department of Computer Science, Purdue University. 
  2. ^ а б Ford, William; Topp, William (2002). Data Structures with C++ Using STL (2nd ed.). New Jersey: Prentice Hall. стр. 683. ISBN 978-0-13-085850-4. 
  3. ^ Goodrich, Michael T; Tamassia, Roberto; Mount, David M (2002). Data Structures and Algorithms in C++. Wiley. ISBN 978-0-471-20208-0. 
  4. ^ Grama, Ananth (2004). „(2,4) Trees“. CS251: Data Structures Lecture Notes. Department of Computer Science, Purdue University Приступљено 10. 4. 2008.. 

Литература[уреди]

Спољашње везе[уреди]