Definujte binární strom. Definujte binární minimovou haldu a popište její reprezentaci pomocí pole

Binární strom

Strom

• acyklický souvislý graf

• strom nazveme binární pokud:

  1. je zakořeněný
  2. každý vrchol má nanejvýš dva potomky

Binární minimová halda

• datová struktura tvaru binárního stromu, v jehož každém vrcholu je uložen jeden klíč k(x) a struktura splňuje tyto dvě vlastnosti:

1. Tvar haldy - strom má všechny hladiny kromě poslední plně obsazené, poslední hladina je obsazena od levého kraje směrem k pravému
2. Haldové uspořádání - **** je-li v vrchol a p jeho potomek, musí platit: k(v) ≤ k(s)

→ v kořeni je tedy globální minimum ze všech klíčů

Reprezentace haldy pomocí pole:

• díky vlastnostem haldy (tvar haldy) ji lze reprezentovat v obyčejném poli P