Jak se jmenuje strom, ve kterém je každý uzel?

Strom je abstraktní datová struktura, jejíž hierarchie je podobná stromu. Skládá se z připojených uzlů, z nichž jeden je „kořen“. Každý uzel může mít jednoho předka a/nebo jednoho či více potomků. Strom je souvislý graf bez cyklů.

Kořen stromu je nejvyšší uzel.

Strom lze rekurzivně definovat jako množinu uzlů, z nichž jeden je kořen a každý uzel je datová struktura obsahující určitou hodnotu a také odkazy na další (dětské) uzly, za předpokladu, že neexistuje žádná vazba na kořenový uzel, ale ke zbytku jsou uzly právě na jednom odkazu.

List je uzel, který nemá žádné potomky (potomky).

Vnitřní uzel je uzel stromu, který má potomky.

Hloubka stromu je nejdelší cesta od kořene stromu k jeho listu.

Strom, ve kterém má každý uzel nejvýše dva potomky, se nazývá binární strom.

Procházení uzlů stromu

Procházení stromem do hloubky: procházení všemi potomky každého uzlu. Je vhodné implementovat rekurzivně:

Postup Procházení stromu do hloubky

Procházení podstromem do hloubky

Konec procedury

Postup Procházení podstromem do hloubky

Cyklus pro každého uzel potomek node.childs provést

Procházení podstromem do hloubky

Konec cyklu

Konec procedury

Procházení stromem do šířky: postupné procházení uzlů stejné úrovně, postupný pohyb z horní do nižší úrovně. Pořadí navštěvujících uzlů je vhodné uspořádat pomocí fronty

Postup Přecházení stromu na šířku

Node_queue.set je prázdný

Cyklus zatím node_queue.non-empty provést

node_queue.take prvek z fronty do

Cyklus pro každého uzel potomek node.childs provést

Prvek Node_queue.add na konec fronty

Konec cyklu

Konec procedury

Binární halda

Binární halda (pyramida, třídící strom) je binární strom, který splňuje následující podmínky:

1) Hodnota v každém uzlu stromu není menší než hodnota v žádném z potomků tohoto uzlu;

2) Každý list má hloubku d nebo d-1, kde d je hloubka stromu;

3) Nejhlubší vrstva je vyplněna bez mezer.

Je vhodné ukládat hodnoty obsažené v binárních uzlech haldy v poli vrstvu po vrstvě, počínaje horní částí stromu. Kořen stromu je uložen v Array[0], jeho levé dítě je v Array[1], jeho pravé dítě je v Array[2] atd. Děti Array[i] jsou v Array[2*i+ 1] a Pole[2 *i+2].

ČTĚTE VÍCE

Kde by měla květina anthurium stát?

Při číslování stromových vrstev shora dolů a uzlů vrstev zleva doprava je i-tý uzel v j-té vrstvě uložen ve vektorovém prvku s indexem i+2 j -1 (při indexování vektorových prvků od 0) .

Příklad 1: Následující pole ukládá obsah binární haldy zobrazené na obrázku:

Jak přeměnit pole na binární haldu?

Jakékoli pole může být reprezentováno jako binární strom, který splňuje vlastnosti 2) a 3). Zbývá pouze přesunout hodnoty prvků uvnitř pole tak, aby splňovaly vlastnost 1).

Použijeme iterační metodu, půjdeme odspodu stromu nahoru, projdeme všemi vnitřními uzly (to znamená uzly, které nejsou listy) zprava doleva, přičemž každý strom zakořeněný v aktuálním uzlu změníme na binární hromadu.

S tímto pořadím procházení budou pro každý aktuální uzel oba podstromy již procházeny, to znamená, že se změní na binární hromadu. Stačí je zkombinovat s aktuálním uzlem tak, aby výsledkem byla také binární halda.

Následující postup (heapify) implementuje popsaný algoritmus:

Postup nahromadit se

! Je dáno: pole ar, N – velikost pole

! Potřebné: pole ar obsahuje binární haldu velikosti N

! Algoritmus: přeměňte „ocas“ pole na binární hromadu,

! postupné posunutí začátku „ocasu“ na začátek pole

začátek := rodič(N-1) ! start : = index posledního interního uzlu

Cyklus zatím začátek >= 0 provést

siftDown(ar, start, N-1) ! Prosít: v případě potřeby obsah přemístit

! zakořenit, takže strom se stane binární hromadou

start = start – 1 ! Přejděte na předchozí vnitřní uzel

Konec cyklu

Konec procedury

Postup rodič

! Vrátí index nadřazeného uzlu

odpověď: = (n – 1) / 2

Konec procedury

Procedura siftDown je založena na skutečnosti, že oba dceřiné podstromy určitého uzlu jsou již binárními hromadami a nyní potřebujeme udělat z celého stromu zakořeněného v tomto uzlu binární hromadu. Pokud je hodnota V v příslušném uzlu větší než hodnoty v obou jeho podřízených uzlech, je vše v pořádku; podle definice je strom již binární hromadou.

V opačném případě budeme muset posunout V po stromu dolů. K pohybu dochází výměnou hodnot dvou uzlů – nadřazeného a podřízeného: větší hodnota stoupá, menší hodnota klesá. Proces připomíná bublinové třídění, jen zde bublina neprochází celým polem, ale pouze podél jedné větve stromu, čímž se výrazně zkracuje její dráha: z O(N) do O(log N).

ČTĚTE VÍCE

Je možné lepit tapety na desky s perem a drážkou?

Takže pokud je V náhodou menší než hodnota v jeho podřízeném uzlu, vyměníme hodnotu V s největší z hodnot v jeho dvou podřízených uzlech. Stejný postup provedeme znovu s uzlem, kde se V pohyboval a tak dále.

Postup siftDown

! Opravte haldu, jejíž kořen je u prvku s indexem r oot,

! za předpokladu, že oba podřízené podstromy jsou binární hromady

! end – index posledního uzlu stromu

! Pokud má kořenový uzel podřízený uzel s hodnotou větší, než je hodnota v kořenu

! Pokud je hodnota v levém podřízeném uzlu větší než hodnota v pravém podřízeném uzlu

Jestliže (rightChild(root) > end) nebo (ar[leftChild(root)] > ar[rightChild(root)]) že

swap(root, leftChild(root)) ! Vyměňte hodnoty kořenového a levého podřízeného uzlu

root := leftChild(root)

Jinak

swap(root, rightChild(root)) ! Vyměňte hodnoty kořenového a pravého podřízeného uzlu

root := rightChild(root)