2-3 stablo

U Informatici, 2–3 stablo je stablo kao struktura podataka, gde svaki č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. 2−3 stabla su napravljena od strane Džona Hopkrofta 1970. godine.

• 
  2-čvor
• 
  3-čvor

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 $a<b$. 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 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.

1. 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.
2. Recimo da je -{r}- koren stabla -{T}-.
3. 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.
4. 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 $d<e$, onda postavi -{L}- kao novo -{T}-, gde je -{L}- po definiciji 2-3 stablo, i idi nazad na korak dva. Ako je $d>e$, onda postavi -{R}- kao novo -{T}-, gde je -{R}- po definiciji 2-3 stablo, i idi nazad na korak dva.
5. 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 $a<b$. Postoje četiri slučaja: Ako je -{d}- jednako sa -{a}- ili sa -{b}-, onda je -{d}- u -{T}- i završili smo. Ako je $d<a$, onda postavi -{L}- kao novo -{T}- i idi nazad na korak 2. Ako je $a<d<b$, onda postavi -{M}- kao novo -{T}-i idi nazad na korak 2. Ako je $d>b$, 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.

Ubacivanje broja u 2-3 stablo u tri moguća slučaja.

Vremenska složenost

Vremenska složenost u notaciji velikog O:

	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)}-