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–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 . 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 , onda postavi L kao novo T, gde je L po definiciji 2-3 stablo, i idi nazad na korak dva. Ako je , 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 . Postoje četiri slučaja: Ako je d jednako sa a ili sa b, onda je d u T i završili smo. Ako je , onda postavi L kao novo T i idi nazad na korak 2. Ako je , onda postavi M kao novo Ti idi nazad na korak 2. Ako je , 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)


Reference

  1. ^ Gross, R. Hernández, J. C. Lázaro, R. Dormido, S. Ros (2001). Estructura de Datos y Algoritmos. Prentice Hall. 
  2. ^ Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. , pp. 145–147
  3. ^ Cormen, Thomas (2009). Introduction to Algorithms. The MIT Press. стр. 504.