2-3 стабло

У Информатици, 2–3 стабло је стабло као структура података, где сваки чвор са децом (унутрашњи чвор) има или двоје деце (2-чвор) и носи један податак, или има троје деце (3-чвор) и носи два податка. Чворови изван стабла, тј. листови, немају децу, а носе један или два податка. 2−3 стабла су направљена од стране Џона Хопкрофта 1970. године.

• 
  2-чвор
• 
  3-чвор

2–3 стабла су једна изометрија АА стабла, што значи да су еквивалентне структуре података. Другим речима, за свако 2–3 стабло, постоји најмање једно АА стабло са подацима у истом редоследу. 2–3 стабла су балансирана, што значи да свако десно, централно, и лево подстабло садржи исту или скоро исту количину података.

Дефиниције

Кажемо да је чвор 2-чвор ако и само ако носи један податак и има двоје деце ако је унутрашњи чвор.

Кажемо да је чвор 3-чвор ако и само ако носи два податка и има троје деце ако је унутрашњи чвор.

Кажемо да је T 2-3 стабло ако и само ако је испуњен један или више ових захтева:

• T је празно стабло. Другим речима, T нема чворова.
• T је 2-чвор r са податком a. Ако r има лево дете L анд десно дете R, онда су L и R непразна 2-3 стабла једнаке висине, податак a је већи од свих осталих података у L, и податак a је мањи од свих осталих података у R.
• T је 3-чвор r са подацима a и b, где је $a<b$. Ако r има лево дете L, средишње дете M, и десно дете R, онда су L, M,и R непразна 2-3 стабла једнаке висине, а податак a је већи од свих осталих података у L и мањи од свих осталих података у M, а податак b је већи од свих осталих података у M и мањи од свих осталих података у R.

Особине

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

Операције

Претрага

Тражење елемента у 2-3 стаблу је слично тражењу елемента у бинарном стаблу претраге. Како су сви подаци у сваком чвору сортирани, функција претраживања биће усмерена у одговарајуће подставло и евентуално на одговарајући чвор са траженим податком.

1. Рецимо да је T 2-3 стабло и d је одговарајући податак који треба да се пронађе. Ако је T празно, онда d није у T и завршили смо.
2. Рецимо да је r корен стабла T.
3. Претпоставимо да је r лист. Ако d није у r, онда d није у T. Иначе, d је у T. У суштини, d може бити пронађен у чвору који је лист. Не требају нам даљи кораци јер смо завршили.
4. Претпоставимо да је r 2-чвор са левим дететом L и десним дететом R. Рецимо да је e податак у r. Постоје три случаја: Ако је d једнако са e, онда смо пронашли d у T и завршили смо. Ако је $d<e$, онда постави L као ново T, где је L по дефиницији 2-3 стабло, и иди назад на корак два. Ако је $d>e$, онда постави R као ново T, где је R по дефиницији 2-3 стабло, и иди назад на корак два.
5. Претпоставимо да је r 3-чвор са левим дететом L, средњим дететом M, и десним дететом R. Рецимо да су a и b два податка које носи чвор r, где је $a<b$. Постоје четири случаја: Ако је d једнако са a или са b, онда је d у T и завршили смо. Ако је $d<a$, онда постави L као ново T и иди назад на корак 2. Ако је $a<d<b$, онда постави M као ново Tи иди назад на корак 2. Ако је $d>b$, онда постави R као ново Tи иди назад на корак 2.

Убацивање

Убацивање ради по принципу тражења погодне локације за кључ и додавања кључа на ту локацију. Ако чвор постане 4-чвор, онда чвор треба да се подели на два 2-чвора, а средишњи кључ се помери ка родитељу. Дијаграм илуструје цео процес.

Убацивање броја у 2-3 стабло у три могућа случаја.

Временска сложеност

Временска сложеност у нотацији великог О:

	Просечно	Најгори случај
Простор	O(n)	O(n)
Претрага	O(log n)	O(log n)
Убацивање	O(log n)	O(log n)
Брисање	O(log n)	O(log n)