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.^[1][2] 2−3 stabla su napravljena od strane Džona Hopkrofta 1970. godine.^[3]

• 
  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.

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 ${\displaystyle 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.

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

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 ${\displaystyle d<e}$, onda postavi L kao novo T, gde je L po definiciji 2-3 stablo, i idi nazad na korak dva. Ako je ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle d<a}$, onda postavi L kao novo T i idi nazad na korak 2. Ako je ${\displaystyle a<d<b}$, onda postavi M kao novo Ti idi nazad na korak 2. Ako je ${\displaystyle d>b}$, onda postavi R kao novo Ti idi nazad na korak 2.

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.

Vremenska složenost u notaciji velikog O: