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 Ti idi nazad na korak 2. Ako je $d>b$, onda postavi R kao novo Ti 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)