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.
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.
- 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 , 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.
- 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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/44/2-3_insertion.svg/581px-2-3_insertion.svg.png)
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
- ^ Gross, R. Hernández, J. C. Lázaro, R. Dormido, S. Ros (2001). Estructura de Datos y Algoritmos. Prentice Hall.
- ^ Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. , pp. 145–147
- ^ Cormen, Thomas (2009). Introduction to Algorithms. The MIT Press. стр. 504.