Levo poravnano drevo

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 20:53, 20 marec 2008
IgorPrsa (Pogovor | prispevki)

← Prejšnja različica
Različica od 12:38, 22 maj 2008
MatijaLokar (Pogovor | prispevki)

Naslednja različica →
Vrstica 1: Vrstica 1:
-{{Student|IgorPrsa|DIRI}}+Levo poravnano drevo je lahko popolnoma izravnano binarno drevo ali popolnoma izravnano drevo, pri katerem manjkajo nekateri listi na desni strani v najvišjem nivoju.
-Levo podravnano drevo je lahko popolnoma izravnano binarno drevo ali popolnoma izravnano drevo, pri katerem manjkajo nekateri listi na desni strani v najvišjem nivoju.+
Za levo poravnano drevo velja:<br /> Za levo poravnano drevo velja:<br />
'''''h + 1 &le; n &le; 2<sup>h + 1</sup> - 1''<br /> '''''h + 1 &le; n &le; 2<sup>h + 1</sup> - 1''<br />

Različica od 12:38, 22 maj 2008

Levo poravnano drevo je lahko popolnoma izravnano binarno drevo ali popolnoma izravnano 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 pomembno saj omogoča preprosto shranjevanje podatkov v tabelo po sledečem pravilu:

  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 popolnoma izravnanem drevesu) hkrati pa omogoča dinamično podatkovno strukturo.

Osebna orodja