Juraj na 20:19, 16. august 2010

2010-08-16T20:19:15Z

Juraj na 14:00, 5. apríl 2010

2010-04-05T14:00:56Z

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} '''Strom''' je dynamická dátová štrukt…“

2010-03-28T17:08:32Z

Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} '''Strom''' je dynamická dátová štrukt…“

Nová stránka

[[Kategória:Študijné materiály]]
[[Kategória:Programovanie]]
[[Kategória:Informatika]]
{{Draft}}
{{Skripta programovanie}}
'''Strom''' je dynamická dátová štruktúra. Stromy sa používajú v prípade hierarchických vzťahov a rekurzívnych štruktúr objektov.
__TOC__
==Definícia==
Binárny strom je v informatike stromová dátová štruktúra, ktorej každý vrchol má najviac dvoch potomkov. Zvyčajne sa označujú ako ľavý a pravý. Jedno z bežných použití binárneho stromu je binárny vyhľadávací strom; iné je binárna halda.

Strom má hierarchickú štruktúru: Rodič - potomok

Binárny strom je usporiadaný strom v ktorom má každý vrchol najviac dvoch synov.

Z programátorského hľadiska je výhodné údajovú štruktúru strom definovať pomocou rekurzie:

'''Strom typu T je buď''' <ref>http://cec.truni.sk/stoffov/dynamicke-udajove-struktury/Cast2/</ref>
* prázdna množina alebo
* vrchol typu T spolu s konečným počtom pripojených disjunktných stromov typu T, ktoré nazývame podstromy

Každý strom je tvorený ďalšími stromami, pre ktoré platí rovnaká definícia. Zviditeľníme ju na príklade binárneho stromu:

[[Súbor:binStrom.gif|center|framed|Príklad binárneho stromu]]

Na vedľajšom obrázku je vidieť, že aj podstrom sa skladá z koreňa a dvoch ďalších podstromov (niektorý z nich môže byť aj prázdny!). Každý list (t.j. vrchol bez synov) je tiež stromom, jeho ľavý aj pravý podstrom sú však prázdne.
===Binárny vyhľadávací strom===
Hodnoty v uzloch sú usporiadané tak, že pre každý uzol stromu ''u'' platí<ref>http://sk.wikipedia.org/wiki/Bin%C3%A1rny_vyh%C4%BEad%C3%A1vac%C3%AD_strom</ref>:
* hodnota uložená v ''u'' je väčšia alebo rovná ako hodnota uložená v ľavom podstrome u
* hodnota uložená v ''u'' je menšia alebo rovná ako hodnota uložená v pravom podstrome u

Potom je možné v tomto strome jednoduchým spôsobom vyhľadať danú hodnotu h:

# nastav koreň ako aktuálny uzol (u)
# pokiaľ je v u uložená hodnota h, algoritmus končí (a vráti u)
# ak je u list, algoritmus končí (hodnota h nebola v strome nájdená)
# hodnota h sa porovná s hodnotou v u (nech je táto hodnota h')
## ak je <math>h \le h'</math>, do u sa uloží ľavý potomok u
## inak sa do u uloží pravý potomok u
# pokračuj bodom 2

==Reprezentácia binárneho stromu==
Štruktúra ''Tuzol'' binárneho stromu sa skladá z:
*hodnoty (hodnôt) uzla
*2 ukazovateľov na ďalšie uzly (vetvy)
<source lang="c">
struct TUzol
{ int data;
TUzol *lavy,*pravy;
};
</source>
V našom prípade je hodnota uzla premenná data, typu celé číslo. Premenná data môže byť ľubovoľného typu, napr. char, double, ale aj vlastne definovaných typov - štruktúra.

[[Súbor:binStrom2.png|center|framed|Usporiadanie prvkov TUzol v binárnom strome]]

Na sprístupnenie stromu potrebujeme ukazovateľ na koreň, v programe teda stačí deklarovať:
<source lang="c">
TUzol *strom;
</source>
Ak niektorý vrchol nemá syna, hodnoty príslušných ukazovateľov sú NULL
==Operácie s binárnym stromom==
V nasledujúcich prípadoch budeme pracovať s binárnym vyhľadávacím stromom.

===Vloženie hodnoty do stromu===
'''Úloha:''' vložiť do stromu nový uzol. Nový uzol treba vložiť na správne miesto tak, aby bol strom usporiadaný.

'''Analýza:'''
*Strom je prázdny. Novo vložený uzol bude koreňom stromu.
*Strom nie je prázdny. V strome je už nejaký uzol. V tomto prípade treba zistiť, na ktorú stromu stromu sa má uzol vložiť.
**Rozdhodnutie robíme podľa hodnoty dátovej časti nového uzla:
***Ak je hodnota nového uzla menšia ako hodnota existujúceho uzla, tak ho dáme vľavo,
***inak ho vložíme vpravo.
**Ak je vpravo, alebo vľavo už nejaký uzol, postupujeme rekurzívne

'''Algoritmus vloženia:'''

Definujme procedúru ''Vloz'', ktorá bude mať 2 parametre: Začiatočný uzol stromu, do ktorého budeme vkladať hodnotu. Keďže strom je rekurzívna štruktúra, algoritmus vloženia bude rekurzívny.

Procedúra ''Vloz''( Uzol U, hodnota H)
#Ak aktuálny uzol U neobsahuje žiadnu hodnotu
##do dátovej časti uzla U nastav hodnotu H
##Nastav hodnoty smerníkov ''lavy'' a ''pravy'' uzla U na hodnotu NULL
##Koniec
#Ak je hodnota H <nowiki><</nowiki> ako hodnota v uzle U
##Ak nemá uzol U ľavého potomka
###Vytvor nový uzol <math>U_n</math> a nastav mu v dátovej časti prázdnu hodnotu
##Zavolaj procedúru ''Vloz'' s parametrami: Uzol U - ľavý (novo vytvorený) potomok uzla U (<math>U_n</math>), hodnota - H
#Ak je hodnota H > ako hodnota v uzle U
##Ak nemá uzol U pravého potomka
###Vytvor nový uzol <math>U_n</math> a nastav mu v dátovej časti prázdnu hodnotu
##Zavolaj procedúru ''Vloz'' s parametrami: Uzol U - pravý (novo vytvorený) potomok uzla U (<math>U_n</math>), hodnota - H

'''Znázornenie algoritmu vloženia'''
<gallery widths=300px heights=200px perrow=2>
Image:binStrom_vlozenie1.png| Počiatočný stav. Strom reprezentuje jeden vrchol, ktorý nemá hodnotu (v našom prípade ju znázorňuje hodnota 0)
Image:binStrom_vlozenie2.png| Do stromu vkladáme hodnotu 5. V opísanom algoritme je táto situácia zachytená v kroku 1. Následne sa vykonajú kroky 1.1, 1.2 a 1.3
Image:binStrom_vlozenie3.png| Do stromu vkladáme hodnotu 3. V algoritme platí krok 2. Krok 2.1 : uzol U nemá ľavého potomka tak takéhoto potomka vytvoríme (krok 2.1.1). Zavoláme procedúru Vloz s parametrami: uzol U - lavý potomok uzla U (teda novo vytvorený uzol). Po rekurzívnom zavolaní procedúry Vloz (krok 2.2) bude platiť podmienka v kroku 1.
Image:binStrom_vlozenie4.png| Do stromu vkladáme hodnotu 4. V algoritme platí krok 3. Krok 3.1 : uzol U nemá pravého potomka tak takéhoto potomka vytvoríme (krok 3.1.1). Zavoláme procedúru Vloz s parametrami: uzol U - pravý potomok uzla U (teda novo vytvorený uzol). Po rekurzívnom zavolaní procedúry Vloz (krok 3.2) bude platiť podmienka v kroku 2. Ďalší postup je rovnaký ako pri vkladaní hodnoty 3.
</gallery>

===Prehľadávanie stromu===
Za základnú operáciu sa však považuje prehľadávanie stromu (pohyb po strome). Vzhľadom na to, že strom je výhodne definovaný ako rekurzívna údajová štruktúra, aj na prehľadávanie sa využívajú rekurzívne metódy.

Keďže strom je rekurzívna štruktúra prehľadávanie stromu bude tiež rekurzívne. Podľa toho ako budeme postupovať pri prehľadávaní stromu, rozlišujeme metódy prehľadávania na:
*preorder
*inorder
*postorder

Majme nasledujúci binárny strom:

[[Súbor:binStrom3.png|center|framed|Usporiadaný binárny strom]]

====Prehľadávanie preorder:====
Postup prehľadávanie (výpisu hodnôt) binárneho stromu:
*Vypíš hodnotu uzla
*prehľadaj ľavý podstrom
*prehľadaj pravý podstrom

Pri tomto postupe bude výpis binárneho stromu na predchádzajúcom obrázku nasledovný:
10 5 1 0 4 7 6 9 12

====Prehľadávanie inorder:====
Postup prehľadávanie (výpisu hodnôt) binárneho stromu:
*prehľadaj ľavý podstrom
*Vypíš hodnotu uzla
*prehľadaj pravý podstrom

Pomocou tohoto spôsobu prehľadávania stromu dostaneme pri výpise postupnosť usporiadaných hodnôt uzlov stromu od najmenšej po najväčšiu hodnotu.
Pri tomto postupe bude výpis binárneho stromu na predchádzajúcom obrázku nasledovný:
0 1 4 5 6 7 9 10 12

====Prehľadávanie postorder:====
Postup prehľadávanie (výpisu hodnôt) binárneho stromu:
*prehľadaj ľavý podstrom
*prehľadaj pravý podstrom
*Vypíš hodnotu uzla

Pri tomto postupe bude výpis binárneho stromu na predchádzajúcom obrázku nasledovný:
0 4 1 6 9 7 5 12 10

===Zmazanie stromu===
Princíp zmazania je podobný ako prechádzanie stromom:
*Ak nemá uzol žiadneho potomka, zmažeme uzol
*Ak má potomka
**zmažeme ľavú časť stromu
**Zmažeme pravú časť stromu

==Implementácia v jazyku C==
===Vloženie hodnoty do stromu===
<source lang="c">
void PridajUzol(TUzol *uzol, int udaj)
{
if (!uzol-> data) // ak v danom uzle nie su ziadne data- pridame novy udaj
{ uzol->data = udaj; // do uzla skopirujeme data
uzol->lavy = uzol->pravy = NULL; // nastavime pointre na lavy a pravy uzol
return;
}
if(uzol->data >= udaj) // pridavame vlavo
{ if (!uzol->lavy) // ak uzol vlavo neexisuje
{ uzol->lavy = new TUzol; // tak ho vytvorime
uzol->lavy->data=0;
}
PridajUzol(uzol->lavy, udaj); // opakujeme rekurzivne funkciu s lavym uzlom
}
else // pridavame vpravo
{ if (!uzol->pravy)
{ uzol-> pravy = new TUzol;
uzol->pravy->data=0;
}
PridajUzol(uzol-> pravy, udaj);
}
}
</source>
===Výpis stromu inorder===
<source lang="c">
void vypis(TUzol *s)
{
if(!s)
return;
else
{
vypis(s->lavy);
cout<<s->data<<endl;
vypis(s->pravy);
}
}
</source>
===Vyhľadávanie v strome (inorder)===
Funkcia ''hladaj'' bude v strome vyhľadávať uzol s hodnotou ''x''. V prípade úspechu vráti smerník na tento prvok. V opačnom prípade vráti hodnotu NULL.
<source lang="c">
TUzol* hladaj(TUzol *s, int x)
{
if(s==NULL)
return NULL;
else
{
if(x < s->data)
return hladaj(s->lavy,x);
if(s->data==x)
return s;
if(x > s->data)
return hladaj(s->pravy,x);
}
}
</source>

===Zmazanie stromu===
Princíp zmazania je podobný ako vypísania.
*Ak nemá uzol žiadneho potomka, zmažeme aktuálny uzol
*Ak má potomka
**zmažeme ľavú časť stromu
**zmažeme pravú časť stromu

<source lang="c">
void ZmazStrom(TUzol *uzol)
{
if (!uzol) return;
if (uzol->lavy) // ak existuje lavy uzol
{ ZmazStrom(uzol->lavy);
delete uzol->lavy;
}
if (uzol->pravy) // ak existuje pravy uzol
{ ZmazStrom(uzol->pravy);
delete uzol->pravy;
}
}
</source>
==Zdroje==
<references/>

← Staršia verzia		Verzia zo dňa a času 20:19, 16. august 2010
Riadok 1:		Riadok 1:
−	~~[[Kategória:Študijné materiály]]~~
−	~~[[Kategória:Programovanie]]~~
−	~~[[Kategória:Informatika]]~~
	{{Draft}}		{{Draft}}
	{{Skripta programovanie}}		{{Skripta programovanie}}

@@ Riadok 6: / Riadok 6: @@
 '''Strom''' je dynamická dátová štruktúra. Stromy sa používajú v prípade hierarchických vzťahov a rekurzívnych štruktúr objektov.
 __TOC__
 ==Definícia==
 Binárny strom je v informatike  stromová dátová štruktúra, ktorej každý vrchol má najviac dvoch potomkov. Zvyčajne sa označujú ako ľavý a pravý. Jedno z bežných použití binárneho stromu je binárny vyhľadávací strom; iné je binárna halda.

Binárny strom - História úprav

Juraj na 20:19, 16. august 2010

Juraj na 14:00, 5. apríl 2010

Juraj: Vytvorená stránka „Kategória:Študijné materiály Kategória:Programovanie Kategória:Informatika {{Draft}} {{Skripta programovanie}} '''Strom''' je dynamická dátová štrukt…“