Back

ⓘ 2-3 stablo




2-3 stablo
                                     

ⓘ 2-3 stablo

U Informatici, 2–3 stablo je stablo kao struktura podataka, gde svaki čvor sa decom ima ili dvoje dece i nosi jedan podatak, ili ima troje dece i nosi dva podatka. Čvorovi izvan stabla, tj. listovi, nemaju decu, a nose jedan ili dva podatka. 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.

                                     

1. 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 3-čvor r sa podacima a i b, gde je a < b {\displaystyle a e {\displaystyle d> e}, onda postavi R kao novo T, gde je R po definiciji 2-3 stablo, i idi nazad na korak dva.
  • 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.
  • 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 a < b {\displaystyle a