— Stromy —

Stromy

Dynamické množiny

Dynamická množina: Množinu prvků, která se mění v čase.

Prvek dynamické množiny

• přístup přes ukazatel

• obsahuje: klíč, ukazatel na další prvky, příp. další data

Operace na dynamické množině

Nechť S je dynamická množina prvků, k je hodnota klíče a x je ukazatel na prvek.

Slovníkové operace:

Find(S, k) Vrací ukazatel na prvek v S s klíčem k, pokud existuje, jinak vrací nil

Insert(S, x) Do S vloží prvek, na který ukazuje x

Delete(S, x) Z S odstraní prvek, na který ukazuje x

Min(S) Vrátí ukazatel na prvek S s minimálním klíčem

Max(S) Vrátí ukazatel na prvek S s maximálním klíčem

Succ(S, x)

Vrátí ukazatel na v pořadí další prvek za x v S podle uspořádání klíčů (pokud x obsahuje max. klíč, vrátí nil)

Prec(S, x)

Vrátí ukazatel na v pořadí předchozí prvek za x v S podle uspořádání klíčů

Binární vyhledávací stromy

Dynamická datová struktura podporující všechny uvedené operace. Binární strom: Každý prvek má tři ukazatele: rodič, levý, pravý. V BVS pak pro každý prvek x platí:

(i) Každý prvek v levém podstromu má klíč ≤ klíč x (ii) Každý prvek v pravém podstromu má klíč ≥ klíč x

… implementace operací…

Červeno–černé stromy

...definice...

LEMMA 1:

Nechť x je libovolný uzel. Pak podstrom s kořenem x obsahuje alespoň 2^{bh(x)} − 1 interních uzlů.

DŮKAZ:

Indukcí podle h(x):

(i) h(x) = 0: Podstrom s kořenem x na 2^{0} − 1 = 1 − 1 = 0.

(ii) Nechť tvrzení platí pro 1, …, h(x) − 1 a h(x) > 0. x je interní (h(x) > 0), tedy x má dva syny y a z. Pak platí:

\begin{aligned}h(y) & < h(x) \\ h(z) & < h(x) \end{aligned}

Také platí:

bh(z) = bh(y) = \{ \begin{matrix}bh(x) & pokud y je červený \\ bh(x) − 1 & pokud y je černý \end{matrix}

Z indukčního předpokladu víme, že podstrom s kořenem y má alespoň 2^{bh(y)} − 1 intereních uzlů, kterých je alespoň 2^{bh(y)−1} −1. Totéž platí pro podstrom s kořenem z.

Tedy x má alespoň 2^{bh(x)−1} − 1 + 2^{bh(x)−1} − 1 + 1 = 2^{bh(x)} − 1. Q.E.D.