Levo poravnano drevo

Iz MaFiRaWiki

Levo poravnano drevo je lahko polno drevo ali polno drevo, pri katerem manjkajo nekateri listi na desni strani v najvišjem nivoju. Za levo poravnano drevo velja:
h + 1 ≤ n ≤ 2h + 1 - 1
in
h = |log n|
pri čemer h predstavlja višino drevesa, n pa število vozlišč.

Levo poravnano drevo
Slika1: Levo poravnano drevo

To drevo je pomembna podatkovna strukura saj omogoča preprosto shranjevanje podatkov v tabelo po sledečem pravilu (gl. tudi dvojiško drevo:

  1. oče vozla na lokaciji i, je vedno shranjen na lokaciji i/2;
  2. levi sin vozla na lokaciji i, je shranjen na lokaciji 2i;
  3. desni sin vozla na lokaciji i, pa je shranjen na lokaciji 2i + 1.
Shranjevalni prostor je optimalno izrabljen (sicer ne vedno tako kot pri polnem drevesu) hkrati pa omogoča lažje vzdrževanje saj je dodajanje in brisanje elementov enostavnejše ("cenejše").

Osebna orodja