Изворни код странице 2-3 stablo

U [[Информатика|Informatici]], '''2–3 stablo''' je [[Стабло (структура података)|stablo]] kao struktura podataka, gde svaki [[Čvor (informatika)|čvor]] sa decom (''unutrašnji čvor'') ima ili dvoje dece (''2-čvor'') i nosi jedan podatak, ili ima troje dece (''3-čvor'') i nosi dva podatka. Čvorovi izvan stabla, tj. listovi, nemaju decu, a nose jedan ili dva podatka.<ref>{{cite book
  | title = Estructura de Datos y Algoritmos
  | first1 = R. Hernández, J. C. Lázaro, R. Dormido, S. Ros
  | last1 = Gross
  | publisher = Prentice Hall
  | year=2001}}
  </ref><ref>{{cite book|first1=Alfred V.|last1=Aho|first2=John E.
|last2=Hopcroft
|first3=Jeffrey D.
|last3=Ullman
|title=The Design and Analysis of Computer Algorithms
|publisher=Addison-Wesley
|year=1974}}, pp. 145–147</ref> 2−3 stabla su napravljena od strane [[Џон Хопкрофт|Džona Hopkrofta]] 1970. godine.<ref>{{Cite book|title = Introduction to Algorithms|url = https://archive.org/details/introductiontoal00corm_453|last=Cormen|first = Thomas|publisher = The MIT Press|year=2009|pages = [https://archive.org/details/introductiontoal00corm_453/page/n524 504]}}</ref>

<gallery heights="95px">
Image:2-3-4 tree 2-node.svg|2-čvor
Image:2-3-4-tree 3-node.svg|3-čvor
</gallery>

2–3 stabla su jedna izometrija '''AA stabla''', što znači da su ekvivalentne strukture podataka. Drugim rečima, za svako 2–3 stablo, postoji najmanje jedno AA stablo sa podacima u istom redosledu. 2–3 stabla su balansirana, što znači da svako desno, centralno, i levo podstablo sadrži istu ili skoro istu količinu podataka.


== Definicije ==

Kažemo da je čvor '''2-čvor''' ako i samo ako nosi ''jedan'' podatak i ima ''dvoje'' dece ako je unutrašnji čvor.

Kažemo da je čvor '''3-čvor''' ako i samo ako nosi ''dva'' podatka i ima ''troje'' dece ako je unutrašnji čvor.

Kažemo da je -{''T''}- '''2-3 stablo''' ako i samo ako je ispunjen jedan ili više ovih zahteva:
* -{''T''}- je prazno stablo. Drugim rečima, -{''T''}- nema čvorova.
* -{''T''}- je 2-čvor -{''r''}- sa podatkom -{''a''}-. Ako -{''r''}- ima levo dete -{''L''}- and desno dete -{''R''}-, onda su -{''L''}- i -{''R''}- neprazna 2-3 stabla jednake visine, podatak -{''a''}- je veći od svih ostalih podataka u -{''L''}-, i podatak -{''a''}- je manji od svih ostalih podataka u -{''R''}-.
* -{''T''}- je 3-čvor -{''r''}- sa podacima -{''a''}- i -{''b''}-, gde je <math>a < b</math>. Ako -{''r''}- ima levo dete -{''L''}-, središnje dete -{''M''}-, i desno dete -{''R''}-, onda su -{''L''}-, -{''M''}-,i -{''R''}- neprazna 2-3 stabla jednake visine, a podatak -{''a''}- je veći od svih ostalih podataka u -{''L''}- i manji od svih ostalih podataka u -{''M''}-, a podatak -{''b''}- je veći od svih ostalih podataka u -{''M''}- i manji od svih ostalih podataka u -{''R''}-.

== Osobine ==
* Svaki unutrašnji čvor je 2-čvor ili 3-čvor.
* Svi listovi su na istom nivou.
* Svi podaci su čuvani kao sortirani.

== Operacije ==
=== Pretraga ===

Traženje elementa u 2-3 stablu je slično traženju elementa u [[Binarno stablo pretrage|binarnom stablu pretrage]]. Kako su svi podaci u svakom čvoru sortirani, funkcija pretraživanja biće usmerena u odgovarajuće podstavlo i eventualno na odgovarajući čvor sa traženim podatkom.

# Recimo da je -{''T''}- 2-3 stablo i -{''d''}- je odgovarajući podatak koji treba da se pronađe. Ako je -{''T''}- prazno, onda -{''d''}- nije u -{''T''}- i završili smo.
# Recimo da je -{''r''}- koren stabla -{''T''}-.
# Pretpostavimo da je -{''r''}- list. Ako -{''d''}- nije u -{''r''}-, onda -{''d''}- nije u -{''T''}-. Inače, -{''d''}- je u -{''T''}-. U suštini, -{''d''}- može biti pronađen u čvoru koji je list. Ne trebaju nam dalji koraci jer smo završili.
# Pretpostavimo da je -{''r''}- 2-čvor sa levim detetom -{''L''}- i desnim detetom -{''R''}-. Recimo da je -{''e''}- podatak u -{''r''}-. Postoje tri slučaja: Ako je -{''d''}- jednako sa -{''e''}-, onda smo pronašli -{''d''}- u -{''T''}- i završili smo. Ako je <math>d < e</math>, onda postavi -{''L''}- kao novo -{''T''}-, gde je -{''L''}- po definiciji 2-3 stablo, i idi nazad na korak dva. Ako je <math>d > e</math>, onda postavi -{''R''}- kao novo -{''T''}-, gde je -{''R''}- po definiciji 2-3 stablo, i idi nazad na korak dva.
# Pretpostavimo da je -{''r''}- 3-čvor sa levim detetom -{''L''}-, srednjim detetom -{''M''}-, i desnim detetom -{''R''}-. Recimo da su -{''a''}- i -{''b''}- dva podatka koje nosi čvor -{''r''}-, gde je <math>a < b</math>. Postoje četiri slučaja: Ako je -{''d''}- jednako sa -{''a''}- ili sa -{''b''}-, onda je -{''d''}- u -{''T''}- i završili smo. Ako je <math>d < a</math>, onda postavi -{''L''}- kao novo -{''T''}- i idi nazad na korak 2. Ako je <math>a < d < b</math>, onda postavi -{''M''}- kao novo -{''T''}-i idi nazad na korak 2. Ako je <math>d > b</math>, onda postavi -{''R''}- kao novo -{''T''}-i idi nazad na korak 2.

=== Ubacivanje ===
Ubacivanje radi po principu traženja pogodne lokacije za ključ i dodavanja ključa na tu lokaciju. Ako čvor postane 4-čvor, onda čvor treba da se podeli na dva 2-čvora, a središnji ključ se pomeri ka roditelju. Dijagram ilustruje ceo proces.
[[Датотека:2-3 insertion.svg|оквир|без|800px|Ubacivanje broja u 2-3 stablo u tri moguća slučaja.]]

== Vremenska složenost ==

[[Субекспоненцијално време|Vremenska složenost]] u [[Велико О|notaciji velikog O]]:
{| class="wikitable"
|-
|        || '''Prosečno''' || '''Najgori slučaj'''
|-
| ''Prostor'' || -{O(n)}- || -{O(n)}- 
|-
| ''Pretraga'' || -{O(log n)}-  || -{O(log n)}- 
|-
| ''Ubacivanje'' || -{O(log n)}- || -{O(log n)}-
|-
| ''Brisanje'' || -{O(log n)}- || -{O(log n)}-
|}


== Reference ==
{{reflist|}}

{{normativna kontrola}}

[[Категорија:Стабла (структуре података)]]
[[Категорија:Стабла (теорија графова)]]