MFF Notebook > Datové struktury

Datové struktury

Datové struktury.

Halda

  • Je binární vyhledávací strom.
  • Každý uzel má vyšší hodnotu, než jeho děti.

Vložení prvku do haldy se provede tak, že nový prvek umístí do patra s listy. Pokud je plné, vloží se doleva pod něj. Potom se na rodiče právě vloženého prvku zavolá operace heapify. Ta se provádí nad jedním uzlem, přičemž se prohodí hodnota se synem, pokud má vyšší hodnotu. Po dokončení se rekurzivně volá ta samá operace na rodiče.

Binomiální halda

  • Množina binomiálních stromů. Každý řád je zastoupen pouze jedním stromem.
  • Binomiální strom Bk:
    • Obsauje právě 2k uzlů.
    • Má výšku k.
    • Má právě (k nad i) vrcholů v hloubce i (i ∈ <0,k>).
    • Jeho kořen má k synů, přičemž i-tý syn zprava je kořenem podstromu Bi (i ∈ <0,k-1>).

Červeno-černý strom

  • Je binární vyhledávací strom.
  • Každý uzel je buď červený, nebo černý.
  • Každý list je černý a nenese hodnotu.
  • Pokud je vrchol červený, jsou oba potomci černí.
  • Každá cesta z vrcholu do listu obsauje stejný počet černých vrcholů.

AVL strom

Binární vyhledávací strom je vyváženým AVL stromem právě tehdy, když ∀ uzel x ve stromě platí, že |h(left(x)) - h(right(x))| ≤ 1, kde h(x) je výška (pod)stromu.

B-stromy

Jsou vyvážené vyhledávací stromy. Uzel x s n(x) klíči má n(x) + 1 dětí.

Creative Commons License