====== AP15, IN15 Datové struktury a jejich implementace ======
===== Zadání =====
(seznam, zásobník, fronta, binární strom, obecný strom, vyhledávací stromy a jejich modifikace. Implementace binárních a vyhledávacích stromů a operací nad nimi)
===== Vypracování =====
==== Základní informace ====
Pro ukládání hodnot používáme v programech vedle jednoduchých proměnných různé datové struktury. Na ty se lze dívat ze dvou pohledů:
* **Z pohledu jejich vnitřní realizace** (způsobu uložení dat v paměti) rozlišujeme např. pole, záznam, množinu, řetězec...
* **Podle logiky přístupu k jednotlivým položkám dat** rozlišujeme např. strom, seznam, zásobník, frontu...
V této otázce se budeme zabývat některými základními datovými strukturami podle logiky přístupu k jednotlivým položkám dat (druhý pohled).
==== Seznam ====
Seznam je datová struktura pro ukládání údajů, která je na rozdíl od datové struktury množina tvořena posloupností prvků s pevně stanoveným pořadím. V seznamu se mohou nacházet opakovaně stejné údaje, což je jeho další důležitá odlišnost od množiny. Do seznamu chceme mít schopnost ukládat nové hodnoty, vypouštět z něj údaje, popř. i testovat, zda je daná hodnota v seznamu obsažena. Pro implementaci seznamu se nabízí několik možností:
* Implementace pomocí **dynamického pole**: Tento seznam bývá implementován pomocí dynamicky alokovaného pole, které se v případě potřeby (jakmile počet prvků překročí alokované místo) realokuje na dvojnásobek. Je tomu tak proto, že na seznam délky ''n'' připadá ''log2(n)'' realokací. Kromě toho si musíme pamatovat počet uložených prvků (velikost seznamu) a velikost alokovaného pole (kapacitu seznamu). Na rozdíl od klasického pole můžeme prvky libovolně odebírat a přidávat a nemusíme znát předem jejich počet. Výhodou je rychlý přístup k jednotlivým prvkům (O(//1//)), nevýhodou pomalé odebírání a vkládání prvků doprostřed seznamu (O(//n//)). Při tomto úkonu se všechny prvky za inkriminovaným místem musí posunout o jednu pozici doleva či doprava.
{{:home:inf:dynamic-array.png|}}
* Implementace pomocí **lineárního (jednostranného) spojového seznamu**: Základem je záznam, obsahující uloženou hodnotu a ukazatel na následující prvek. Ukazatel posledního prvku je prázdný. Přístup k prvkům je značně pomalejší (O(//n//) místo O(//1//)), ale odebírání a vkládání prvků doprostřed seznamu probíhá v konstantním čase.
{{:home:inf:singly-linked-list.png|}}
* Implementace pomocí **oboustranného spojového seznamu**: Oproti jednostrannému spojovému seznamu jeho záznam obsahuje i ukazatel na předchozí prvek. (Ukazatele prvního a posledního prvku jsou prázdné.) Umožníme tak procházení směrem od konce na začátek, musíme však v paměti udržovat dvakrát více ukazatelů.
{{:home:inf:doubly-linked-list.png|}}
Pomocí seznamu se dá lehce implementovat **zásobník** nebo **fronta**. Rozdíl je pouze v tom, do jaké části seznamu se prvky přidávají a z jaké se odebírají.
==== Zásobník ====
Zásobník je asi nejpoužívanějším typem seznamů. Je to takový seznam, u něhož jeden konec (tzv. vrchol zásobníku) slouží k přidání i odebírání prvků. Prvky se nemohou přidávat ani odebírat na druhém konci seznamu (označovaném jako **dno zásobníku**) ani nikde uprostřed. Kdykoli tedy chceme odebrat jeden prvek ze zásobníku, bude to ten, který byl do něj vložen jako poslední (je momentálně na vrcholu zásobníku). Zásobník proto bývá někdy označován jako struktura typu **LIFO** (last in - first out). Používá se např. jako základní datová struktura při řízení průchodu do hloubky, při zpracování aritmetických výrazů, při realizaci volání procedur a funkcí apod. Z hlediska obsluhy je to nejjednodušší typ seznamu.
=== Implementace zásobníku pomocí pole ===
První prvek pole vždy představuje dno zásobníku. Vedle vlastního pole dat použijeme ještě jednu proměnnou, která bude v každém okamžiku udávat index toho prvku pole, kde je momentálně vrchol zásobníku.
const Maxdelka = N; {N je číslo omezující maximální délku zásobníku}
var zasobnik : array[1..Maxdelka] of datovytyp;
vrchol : 0..Maxdelka;
procedure Vytvor;
begin
vrchol := 0;
end;
procedure Vloz(X: datovytyp);
begin
if vrchol = Maxdelka then begin {ošetření překročení maximální velikosti}
write('Pozor - zasobnik je plny.');
Halt;
end;
else begin
vrchol := vrchol + 1;
zasobnik[vrchol] := X;
end;
end;
procedure Odeber(var X: datovytyp);
begin
if vrchol = 0 then begin {ošetření prázdnosti zásobníku}
write('Pozor - zasobnik je prazdny.');
Halt;
end;
else begin
X := zasobnik[vrchol];
vrchol := vrchol - 1;
end;
end;
function Jeprazdny: boolean;
begin
if vrchol = 0 then
Jeprazdny := true;
else
Jeprazdny := false;
end;
=== Implementace zásobníku lineárním spojovým seznamem (pomocí ukazatele) ===
Vystačíme si s obyčejným jednosměrným seznamem. Je jen třeba si uvědomit, v jakém směru mají být jednotlivé prvky seznamu zřetězeny. Přidávání prvků na oba konce jednosměrného seznamu je snadné, vypouštění prvku ze začátku jednosměrného seznamu také. Protože vypuštění posledního prvku je ale o dost náročnější (bylo by třeba nalézt předposlední prvek, k čemuž je nutné projít celý seznam od začátku), programuje proto zásobník vždy tak, aby v pořadí první prvek spojového seznamu představoval vrchol zásobníku.
type spoj = ^element;
element = record
hodnota: datovytyp;
dalsi: spoj;
end;
var zasobnik : spoj;
procedure Vytvor;
begin
zasobnik := nil;
end;
procedure Vloz(X: datovytyp);
var pom: spoj;
begin
new(pom);
with pom^ do begin
hodnota := X;
dalsi := zasobnik;
end;
zasobnik := pom;
end;
procedure Odeber(var X: datovytyp);
var pom: spoj;
begin
if zasobnik = nil then begin
write('Zasobnik je prazdny.');
Halt;
end;
else begin
X := zasobnik^.hodnota;
pom := zasobnik;
zasobnik := zasobnik^.dalsi;
dispose(pom);
end;
end;
function Jeprazdny: boolean;
begin
if zasobnik = nil then
Jeprazdny := true;
else
Jeprazdny := false;
end;
==== Fronta ====
V seznamu označovaném jako fronta se pracuje s uloženými daty takovým způsobem, jaký odpovídá čekání lidí ve frontě v běžném životě. Přicházející se řadí za sebe; kdo dřív přišel, bude dříve obsloužen a odejde. Do seznamu dat typu fronta jsou proto na jednom konci ("příchod") vkládány nové prvky, zatímco z druhého konce ("odchod") jsou odebírány prvky vyřazované. V anglicky psané literatuře bývá fronta označována jako FIFO (first in - first out).
Fronta se v programech používá tehdy, pokud potřebujeme dočasně odložit nějaká data a zachovat pro další zpracování jejich původní pořadí. Slouží jako základní datová struktura pro řízení průchodu do šířky. Její programová realizace polem i dynamicky je o něco komplikovanější, než tomu bylo v případě zásobníku.
=== Implementace fronty pomocí pole ===
Frontu můžeme naprogramovat pomocí pole, pokud známe horní odhad její maximální možné délky. Budeme přitom potřebovat dvě celočíselné proměnné, které budou udávat indexy těch prvků pole, kde je uložen první prvek fronty (tj. začátek fronty, odchod) a poslední (konec fronty, příchod). Opakovanými operacemi vkládání a vypouštění prvků se budou hodnoty obou těchto proměnných stále zvyšovat, jak se bude směrem k vyšším indexům posunovat obsazená část pole. Tak by se mohlo po čase stát, že ačkoli aktuální délka fronty nikdy nepřekročí velikost pole, nebude možné vložit do fronty další údaj, neboť poslední prvek pole bude obsazen. Na toto nebezpečí existují tři základní varianty řešení:
* Intuitivní: Posouvat v poli všechny prvky fronty o jedno místo směrem k nižším indexům při každém vypuštění prvku. Díky tomu bude začátek fronty neustále udržován v prvním prvku pole. Postup je to správný a na naprogramování jednoduchý, ale dost neefektivní.
* Lepším řešením je posouvat v poli frontu pouze tehdy, když je to nutné, tj. není-li již kam vložit novou hodnotu. V takové situaci se obsah pole přemístí najednou tak, aby fronta začínala v prvním prvku pole. Proti předchozímu řešení se přesuny prvků provádějí najednou o větší vzdálenost a méně často, výpočet je proto celkově rychlejší.
* Nejlepší pak samozřejmě je data uložená v poli vůbec nepřesouvat. Představíme-li si, že pole je jakoby zatočené dokola a že po posledním prvku pole následuje opět první prvek, při vlastní programové realizaci nám pak stačí pouze přepočítávat indexy. Trochu složitějším se stane testování neprázdnostni fronty (při odebírání prvku) nebo zda by její délka přidáním dalšího prvku nepřekročila kapacitu pole. Pro tento účel je vhodné zavést ještě jednu celočíselnou proměnnou, která bude udávat počet prvků ve frontě.
=== Implementace fronty pomocí spojového seznamu ===
K naprogramování fronty pomocí lineárního spojového seznamu nám opět postačí jednosměrný seznam. Podobně jako v případě zásobníku musíme jen dobře zvolit směr zřetězení prvků v seznamu. K docílení efektivnosti je opět třeba frontu reprezentovat tak, aby její začátek (odchod) byl na začátku seznamu a její konec (příchod) na konci seznamu. Každý uzel zařazený do fronty tedy obsahuje ukazatel na svého následníka. Je to obráceně, než bývá zvykem v běžném životě (např. v čekárně u lékaře nebo u holiče), kde si lidé zpravidla pamatují svého předchůdce, tj. po kom přijdou na řadu.
=== Další typy front ===
Existují i různé modifikace fronty, jako tzv. **obousměrná fronta** (vkládat i odebírat lze na obou jejích koncích) či tzv. **prioritní fronta** (seznam, který není uspořádán v pořadí příchodu prvků, ale podle jejich priorit - každý zařazovaný prvek má svou prioritu a při vkládání není zařazován na konec fronty, ale "předbíhá" všechny prvky fronty, které mají nižší prioritu než on). Realizace prioritní fronty pomocí seznamu je však méně efektivní, proto se prioritní fronta obvykle reprezentuje binární haldou.
==== Strom ====
Pojem **strom** je v teorii grafů formálně definován jako zvláštní případ acyklického grafu. Zvláštní skupinu mezi stromy pak tvoří tzv. **zakořeněné stromy**, v nichž je jeden význačný vrchol označen jako **kořen stromu**.
V informatice se jako strom obvykle označuje útvar, který je složen z jednotlivých vrcholů a má následující tvar:
* Jeden význačný vrchol je **kořenem** stromu.
* Kořen má několik **následníků** (či "synů"), každý z nich má zase své následníky atd. Přitom každý vrchol s výjimkou kořene má právě jednoho svého **předchůdce** ("otce").
* Některé vrcholy nemají již žádné následníky, ty se nazývají **listy**.
**Výška stromu**, tj. počet jeho hladin, je pro prázdný strom rovna 0 a pro neprázdný strom je rovna počtu uzlů na jeho nejdelší větvi. V programech pracujeme pouze se stromy s konečnou výškou.
==== Binární strom ====
Zvláštním případem stromu je **strom binární**, v němž může mít každý vrchol nejvýše dva následníky. S binárním stromem se v programování setkáváme častěji než se stromem obecným. Slouží například pro reprezentaci aritmetického výrazu s binárními operátory nebo pro uložení dat do binárního vyhledávacího stromu či do haldy.
==== Vyhledávací stromy a jejich modifikace ====
Datovou strukturu strom lze výhodně použít k ukládání údajů a vyhledávání nad nimi. **Bi
nární vyhledávací strom** je (na rozdíl od předchozích trochu složitější) datová struktura používaná pro ukládání a vyhledávání údajů. Je to binární strom, v jehož uzlech jsou umístěna data. Přitom pro uspořádání hodnot uložených ve stromu platí následující pravidlo:
* Je-li ve vrcholu V uložena hodnota X, pak všechny uzly v levém podstromu vrcholu V obsahují hodnoty menší, nebo rovny X a všechny uzly v pravém podstromu vrcholu V obsahují hodnoty větší, nebo rovny X. (Hodnoty rovny X je výhodné povolit v pravém i levém podstromu z důvodu krajních případů, například když je BVS vyvážený (viz. níže) a obsahuje jen prvky jedné hodnoty)
Časová složitost operací nad vyhledávacím stromem závisí na jeho výšce. Bude-li množina uložených údajů předem pevně dána, není problém vybudovat tzv. **vyvážený vyhledávací strom**. Pokud se budou data v průběhu programu měnit, lze pro zajištění vyváženosti či další optimalizace vyhledávání obecně a v různých konkrétních případech zavést některou z modifikací vyhledávacích stromů:
* **Dokonale vyvážené stromy** mají nejlepší možné vyvážení, přičemž přesný význam tohoto označení v literatuře není ustálen. Udržování binárního stromu v dokonale vyváženém stavu je ale každopádně poměrně obtížné a vzhledem k srovnatelné časové složitosti s následujícím typem, na který jsou přitom kladeny slabší podmínky, i zbytečné.
* Binární strom se nazývá **AVL-stromem**, jestliže pro každý uzel stromu platí, že výšky jeho levého a pravého podstromu se liší nejvýše o 1. Každý dokonale vyvážený strom je současně AVL-stromem, opačné tvrzení však neplatí. V AVL-stromu je do každého uzlu přidána navíc "technická položka", která může nabývat hodnot -1, 0 nebo 1 a udává, jak se liší výška jeho levého a pravého podstromu.
* Datovou strukturou zajišťující vyváženost stromu již přímo z podstaty způsobu ukládání dat jsou **2-3-stromy**. Rozlišujeme v nich dva typy uzlů. Zvláštní význam mají uzly bez následníků, ve kterých jsou uložena pouze data, naopak všechny ostatní uzly (tzv. vnitřní uzly) slouží pouze k vytvoření vyhledávací struktury. Každý vnitřní uzel obsahuje dva klíče pro vyhledávání a tři ukazatele na následníky. Struktura 2-3-stromu je definována následujícími dvěma pravidly:
- Každý vnitřní uzel stromu má 2 nebo 3 následníky (odtud je také odvozen název struktury).
- Všechny listy stromu jsou ve stejné výšce (na stejné hladině).
Význam klíčů ve vnitřních uzlech je obdobný jako u binárních stromů: První klíč udává maximální hodnotu uloženou v levém podstromu, na nějž ukazuje první ukazatel, druhý klíč může udávat maximální hodnotu uloženou v prostředním podstromu (pokud má uzel jen dva následníky, tento klíč není definován). Pro uložení N údajů je třeba 2-3-strom o N listech. Pro mnohá N lze sestavit více ekvivalentních 2-3-stromů. Výška 2-3-stromu je logaritmicky úměrná počtu údajů N.
* **Červeno-černé stromy** (//red-black trees//) jsou vyvážené binární vyhledávací stromy, podobné AVL stromům. Narozdíl od AVL stromů nesou v uzlu místo "technické položky" informaci o barvě (černá/červená), což spolu s následujícími pravidly zaručuje, že je strom vyvážený:
- Uzel má buďto černou nebo červenou barvu.
- Kořen má černou barvu.
- Každý následník červeného uzlu má černou barvu.
- Každá větev obsahuje stejný počet černých uzlů.
Tato pravidla nám zaručují, že nejdelší cesta z kořene do nějakého listu není delší než dvojnásobek nejkratší cesty z kořene do nějakého (jiného) listu.
==== Halda ====
**Halda** (//heap//) je speciální datová struktura, která má také tvar binárního stromu, ale využívá se nejen k vyhledávání, ale např.
i třídění pomocí haldy. Halda je binární strom, pro který jsou splněny následující podmínky:((Tyto podmínky platí pro častější, tzv. minimovou haldu. Maximová halda je definována podobně, až na nerovnost v bodě 3, která je obrácená.))
- V každé hladině od první až do předposlední je maximální možný počet uzlů, tzn. v //k//-té hladině je 2//k//-1 uzlů.
- V poslední hladině jsou všechny uzly umístěny co možná nejvíce "vlevo", tj. při procházení stromu do hloubky zleva nejprve mají uzly předposlední hladiny dva následníky, pak může být jeden s jedním následníkem a zbývající takové uzly jsou pak už bez následníků.
- Pro každý uzel platí, že hodnota v něm uložená je menší než hodnota v jeho libovolném následníkovi.
==== Implementace binárních a vyhledávacích stromů a operací nad nimi ====
**Binární strom** lze v programu reprezentovat např. v následující dynamické podobě:
type Uk = ^Uzel;
Uzel = record
Info: T; {uložená informace}
L,P : Uk {levý a pravý následník}
end;
Teoreticky je možné jakýkoliv obecný strom reprezentovat stromem binárním (a tedy v této struktuře), k čemuž se využívá tzv. **kanonická reprezentace** stromu - použitý trik spočívá v tom, že v každém uzlu je uložen odkaz na prvního syna a na "bratra" tohoto uzlu. Z libovolného uzlu se tak dostaneme ke všem jeho následníkům tak, že přejdeme na prvního z nich po ukazateli na syna a a mezi následníky pak přecházíme pomocí jejich ukazatelů na bratry.
Vyhledávání vrcholu s hodnotou X v daném **binárním vyhledávacím stromě** je snadné. Začneme v kořeni stromu a postupujeme směrem k listům na základě porovnání hodnoty uložené v uzlu stromu s hodnotu X. Prohledávání končí buď nalezením uzlu s hodnotu X, nebo zjištěním, že v potřebném směru následník neexistuje a hodnota X tedy není ve stromě uložena. Počet provedených porovnání je menší nebo roven výšce stromu, u **vyvážených vyhledávacích stromů** je tedy časová složitost vyhledávání logaritmická.
Při přidávání uzlu do binárního vyhledávacího stromu se postupuje stejně jako při vyhledávání, jen je třeba si zapomatovat uzel, v němž procházení stromem skončilo a pod který je třeba zapojit nový uzel s přidávanou hodnotou. Složitost je opět logaritmická, ale ta může být narušena, jestliže stromy průběžně nevyvažujeme.
Operace vypouštění uzlu je o něco komplikovanější - je třeba do zbytku stromu správně navázat případné následníky rušeného uzlu - ale také ji lze implementovat s logaritmickou složitostí.
Implementace **AVL-stromu** spočívá v zavedení pomocné "technické položky" (zmíněné výše) a provedení vyvážovacího algoritmu po každém provedení operace nad stromem, která způsobila nevyváženost stromu. Vlastní algoritmy jsou však dosti dlouhé a komplikované a dobře jsou popsány v literatuře a je dostupná jejich implementace v mnoha programovacích jazycích.((Popis rotací v AVL-stromech naleznete např. zde: [[http://ksvi.mff.cuni.cz/~holan/]]))
Operace vyhledávání v **2-3-stromě** probíhá podobně jako v binárnéím vyhledávacím stromě, při průchodu se orientujeme podle hodnot klíčů. Trochu náročnější je vkládání nových hodnot a jejich vypouštění - příslušné algoritmy představují vždy jeden průchod od kořene k listu (vyhledání místa, kam se má připojovat nebo kde se má rušit) a poté jeden průchod zpět ke kořeni (modifikace struktury stromu a hodnot klíčů). Z důvodu závislosti počtu operací na hloubce stromu je časová složitost všech těchto operací opět logaritmická.
Vyhledávání, vkládání i rušení uzlu v **červeno-černém stromě** probíhá stejně jako v binárním vyhledávacím stromě. Vložení nebo odebrání prvku však může způsobit porušení pravidel. Proto je nutné v takovém případě strom vyvažovat. Vyvažování se provádí přebarvováním uzlů a rotací větví stromu a je dobře popsáno v literatuře((včetně materiálů Libora Škarvady ke kurzu Návrh algoritmů I)), svou komplikovaností ovšem přesahuje rozsah toto textu. Co je podstatné, je fakt, že i přes toto komplikované vyvažování mají operace operace vložení a odebrání prvku logaritmickou složitost -- . Složitost vyhledání prvku je ve stejné třídě.
==== Implementace haldy ====
Svou strukturou zajišťuje **halda** nalezení minimálního prvku v konstantním čase, provedení operací odebrání minima a přidání nového prvku pak v čase logaritmickém. Její výhodou je algoritmická jednoduchost a možnost snadné realizace v poli, známe-li horní odhad maximálního počtu prvků v haldě. Přidání nového prvku do haldy probíhá jeho připojením na první volné místo v haldě (tj. konec obsazené části pole; aby byla zachována pravidla 1 a 2 pro haldu) a provádění série výměn hodnoty v uzlu s hodnotou v jeho předchůdci, dokud je to třeba (aby bylo zachováno pravidlo 3). Vypuštění minimálního prvku probíhá dosti podobně - hodnotu z kořenu smažeme a namísto toho do kořene přesuneme hodnotu z posledního uzlu haldy, kterou pak necháme dle potřeby "probublat" na její správné místo dolů.
===== Kam dál =====
* [[http://people.ksp.sk/~kuko/bak/index.html|Super prográmek na animaci stromů]]
===== Předměty =====
* [[https://is.muni.cz/auth/predmety/predmet.pl?obdobi=3725;kod=IB002|FI:IB002]] Návrh algoritmů I (jaro 2008), RNDr. Libor Škarvada
===== Použitá literatura =====
* TÖPFER, Pavel: Algoritmy a programovací techniky. PROMETHEUS : Praha. 1995. 1. vydání. ISBN 80-85849-83-6.
===== Vypracoval =====
Marek Blahuš ICQ: 105136489 - většina textu otázky
Martin Gracík - implementace zásobníků v Pascalu
Shkodran Gerguri - červeno-černé stromy
Z mé strany je toto všechno, připomínky pište buďto do diskuze, nebo klidně i přímo upravujte, budu stránku průběžně sledovat. (Marek Blahuš)
Otázku si přečetl pan RNDr. Libor Škarvada a rámcově prošel. Jeho podněty pro doplnění textu, opravy nesrovnalostí a odstranění matoucích či k otázce se nevztahujících textů byly do otázky zaneseny. Tato kontrola je jen **rámcová**, stále se může stát, že v otázce zůstala zapomenutá chybka či nesrovnalost, vyučující za toto nenese odpovědnost, berte tuto rámcovou kontrolu jako formu pomoci od vyučujících pro studenty.
~~DISCUSSION~~