Abstraktní datový typ strom

Question 1

ADT typu strom

Answer 1

ADT typu strom je nelineární dynamická abstraktní datová struktura. Každý uzel stromu může mít 𝑛 potomků a zároveň má pouze jednoho předka. Nejčastější zástupci jsou obecný strom nebo 𝑛-ární strom. 𝑛-ární má maximální počet potomků rovný 𝑛,
obecný strom není počtem potomků omezen.

Skládá se z uzlů, které se pojmenovávají:
– kořen, který existuje pouze jeden (pouze ve vrcholu),
– listy (uzly bez následníků),
– vnitřní uzly (nejsou kořenem ani listem stromu).

Question 2

Binární strom

Answer 2

Binární strom je strom, který má nanejvýše dva potomky na jeden uzel. Za úplný binární strom se považuje binární strom, který se plní po úrovni hloubky z levé strany. Dokud není plně zaplněn levý potomek, nezaplní se pravý.

Question 3

Binární vyhledávací stromy

Answer 3

U těchto stromů musí platit, že levá část potomků musí být vždy menší než kořen a pravá část vždy vetší, tzn. prvky jsou seřazeny. Tyto stromy mohou být nevyvážené ale častěji se také vyvažují, aby bylo dosaženo jejich optimální složitosti O(log 𝑛). Mohl by totiž nastat případ, kdy by ze stromu vznikl pouze seznam
U vyvážených binárních stromů by rozdíl hloubky levé a pravé části měl být 0 nebo 1.

Question 4

Vyhledávání v binárních vyvážených stromech

Answer 4

Postupuje se od kořene dolů. Při každém sestupu se porovná hledaná hodnota s hodnotou listu: pokud je shodná, byl prvek
nalezen. Pokud není, algoritmus sestoupí do levého uzlu (pokud je hledaná hodnota menší než aktuání uzel) nebo do pravého uzlu (pokud je hledaná hodnota větší). Pokud je sestoupeno až k listu a hodnota neodpovídá, hledaný prvek ve stromu není.

Question 5

Vyhledávání, vložení a odstranění prvků v binárním stromu

Answer 5

Vyhledávání: Postupuje se od kořene dolů. Při každém sestupu se porovná hledaná hodnota s hodnotou listu: pokud je shodná, byl prvek nalezen. Pokud není, algoritmus sestoupí do levého uzlu (pokud je hledaná hodnota menší než aktuání uzel) nebo do pravého uzlu (pokud je hledaná hodnota větší). Pokud je sestoupeno až k listu a hodnota neodpovídá, hledaný prvek ve stromu není.

Vkládání: Porovnáváme nový klíč s hodnotou aktuálního uzlu:
pokud je menší, pokračujeme do levého podstromu,
pokud je větší, pokračujeme do pravého podstromu.
Když dorazíme na místo, kde je ukazatel null (neexistuje další podstrom), vytvoříme nový uzel a vložíme ho na toto místo. Vkládání zachovává vlastnost BST – pro každý uzel platí, že levý podstrom obsahuje menší a pravý větší hodnoty než uzel sám.

Odstranění prvků: Pokud uzel nemá žádné potomky, pouze se odstraní a z jeho rodiče se smaže jeho reference. Pokud má jehoho potomka, reference v rodiči se změní na referenci
tohoto potomka. Pokud má potomky dva, existují dvě možnosti: PL a LP.

Pro pravý prvek (PL) nalezneme uzel, který je nejvíc napravo v levém stromu a ten zaměníme za uzel, který chceme smazat: nejpravější uzel v levém stromu převezme referenci
ze mazaného uzlu a rodič mazaného uzlu změní referenci na nejpravější uzel levého stromu.
Pro levý prvek (LP) je to podobné, jen se vybírá nejlevější uzel z pravého stromu.