Stromové struktury (Avl, BVS, B, Red-Black) a jejich implementace
Strom je ADT uchovávající prvky v hierarchické struktuře předcůdce-následovník. Použití v reprezentaci znalostí a stavového prostoru, popis scény při zpracování obrazu, v databázových systémech, systémech souborů, pro rozhodovací stromy, komprese dat, raytracing.
- Obecné stromy - uzly mohou mít libovolný počet následovníků. Implementace pomocí ukazatelů, ve vrcholech spojový seznam následovníku.
- N-ární stromy - uzel má nejvýše n následovníků. Implementace ukazateli, ve vrcholech pole následovníků.
- Binární stromy - uzel má nejvýše dva následovníky. Implementace ukazateli a výčtem následovníků, případne polem.
Binární strom, kde nalevo od každého prvku jsou k prvky s nižším klíčem a napravo s vyšším (příp. obráceně), je binární vyhledávací strom (BVS). Kořenem obyčejného BVS je první vložený prvek, další prvky se vkládají nalevo nebo napravo od něj. Při postupném vkládání seřazené posloupnosti ale takový strom degraduje na lineární seznam, což zvyšuje složitost vyhledávání. Proto je na místě snaha o vyvážení stromu.
[editovat] AVL
(Adelson-Velsky, Landis)
BVS zachovávající pravidlo, že podstromy každého vrcholu se mohou výškou lišit nejvýše o 1. Vyvážení kontrolováno po každém vložení a výberu. Vrchol obsahuje navíc položku informující o rozdílu výšek obou jeho podstromu (-2, -1 levá strana, 0 vyvážený, 1, 2 pravá strana). Vložení stejné jako u BVS, po vložení prepocet rozdílu výšek (v každém kořenu na cestě z vloženého prvku do kořenu stromu sledujeme, jak se jeho vyvýžení změní). Při nevyváženosti v některém vrcholu rotace v tomto vrcholu.
Rotace:
- Jednoduchá - nevyváženost způsobuje levá větev levého podstromu nebo pravá větev pravého podstromu. Kontrolujeme, zda kořen podstromu má stejné znamínko jako kořen nadstromu ???
- Dvojitá - nevyváženost způsobuje pravá vetev levého podstromu nebo levá větev pravého podstromu. Provedeme nejdříve rotaci spodní větve, a tím se dostaneme na předchozí problém.
Odebrání stejné jako u BVS - nahrazení prvku symetrickým následovníkem, po odstranění prvku prepočty rozdílu výšek kontrola vyváženosti smerem ke kořeni (od původní pozice symetrického následovníka - prvky prohozeny a zde odstraňován).
// přidat obrázek
[editovat] Red-Black
Další modifikace BVS. Vrcholy obsahují navíc položku s informací o barve (cervená nebo cerná). Pravidla: koren je vždy cerný, cesty od korene do každého listu obsahují stejný pocet cerných vrcholu (cerná výška stromu), cervený vrchol má pouze cerné následovníky.
Vkládaný vrchol je na zacátku vždy cervený, postupne od jeho pozice ke koreni kontrola pravidel a prípadná náprava
- přebarvením vrcholů: pokud je rodič červený a jeho bratr také, oba přebarvíme na černé a jejich rodiče na černé) - pokud bratr rodiče červený není, přebarvíme na černo pouze rodiče a provedeme rotace - pokud je rodič levým synem, a vkládaný také, provedeme rotaci do prava (rodič se stane kořenem) - pokud je rodič levý, ale vkládaný pravý, provedeme nejprve rotaci do leva (vkládaný se stane rodičem) a tím získáme předchozí problém, tedy přebarvíme a zarotujeme do prava podle vkládaného prvku, který se stane kořenem.
Rotace jsou stejné jako u AVL stromu. Odebrání - nahrazení symetrickým následovníkem, ten ale obarven barvou odebíraného vrcholu, a po té postupujeme stejně jako při vkládání, tedy od místa odebrání kontrola pravidel smerem ke koreni.
[editovat] B-strom
B-strom řádu m má v každém vrcholu nejvýše m následovníků.
Pravidla:
- klíčů ve vrcholu je o 1 méně než následovníků
- všechny listy jsou stejně hluboko
- všechny vrcholy mají maximálně m následovníků
- všechny vrcholy kromě kořene mají minimálně m/2 následovníků
- kořen je buď list nebo má alespoň 2 následovníky
Ve vrcholech klíce serazené, vrcholy razeny jako u BVS (menší klíce vlevo, vetší vpravo). Pri vkládání se pridávají klíce do listu, pokud je v listu prekrocen maximální pocet (pretecení stránky), je list rozdelen uprostred a prostrední klíc vložen do rodice (zde opet kontrola prekrocení poctu). Odebereme-li klíc z listu a ten má potom príliš málo podtecení stránky), muže si vypujcit od sousedu (klíc z rodice do vrcholu, klíc ze souseda do rodice), pokud sousedi mají minimální pocet, dojde ke sloucení vrcholu s jedním sousedem a klícem z rodice. Pri odebírání z vnitrních vrcholu je nutné místo vždy zaplnit - klíc od potomka. Nemají-li potomci dost klícu, sloucí se dva potomci do jednoho. Implementace ukazateli s následovníky seznamem nebo polem, prípadne pomocí dvourozmerných polí (jedno pro klíce, jedno pro indexy následovníku, index korenu).
