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. , pp. 145–147 2−3 stabla su napravljena od strane Džona Hopkrofta 1970. godine.
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 -{T}-i idi nazad na korak 2. Ako je , 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. оквир|без|800px|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
Категорија:Стабла (структуре података) Категорија:Стабла (теорија графова)