From Wikipedia, the free encyclopedia
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.
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 2-3 stablo ako i samo ako je ispunjen jedan ili više ovih zahteva:
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.
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:
Prosečno | Najgori slučaj | |
Prostor | ||
Pretraga | ||
Ubacivanje | ||
Brisanje |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.