Volné stromy. Úvod do programování. Kořenové stromy a seřazené stromy. Volné stromy

7. pˇrednáška Nelineární datové struktury


Stromy Binární stromy Binární vyhledávací stromy

Volné stromy Souvislý, acyklický, neorientovaný graf nazýváme volným stromem (free tree). ˇ Casto vynecháváme adjektivum volný, a ˇríkáme jen, že daný graf je strom.

Úvod do programování Michal Krátký1 , Jiˇrí Dvorský1 1 Katedra informatiky VŠB–Technická univerzita Ostrava

Úvod do programování, 2004/2005

c 2005

Michal Krátký, Jiˇrí Dvorský

Úvod do programování

1/39



Volné stromy

1

G je volný strom.

2

Každé dva uzly v G jsou spojeny práveˇ jednou cestou.

3

G je souvislý, ale pokud odebereme libovolnou hranu, získáme nesouvislý graf.

4

6

G je acyklický, a |E| = |V | − 1.





3/39

Koˇrenové stromy a seˇrazené stromy


c 2005



c 2005





4/39



2/39

Uvažujme uzel x v koˇrenovém stromu T s koˇrenem r . Libovolný uzel y na jednoznaˇcné cesteˇ od koˇrene r do uzlu x se nazývá pˇredchudce ˚ (pˇredek) uzlu x. Jestliže y je pˇredchudce ˚ x, potom x se nazývá následovník (potomek) uzlu y . Každý uzel je pochopitelneˇ pˇredchudcem ˚ a následovníkem sama sebe. Jestliže y je pˇredchudce ˚ x a zárovenˇ x = y , potom y je vlastní pˇredchudce ˚ uzlu x a x je vlastní následovník uzlu y .

G je acyklický. Pˇridáním jediné hrany do množiny hran E bude výsledný graf obsahovat kružnici.


Koˇrenový strom (rooted tree) je volný strom, který obsahuje jeden odlišný uzel. Tento odlišný uzel se nazývá koˇren.

G je souvislý, a |E| = |V | − 1.

c 2005



Necht’ G = (V , E) je neorientovaný graf, potom následující tvrzení jsou ekvivalentní:

5

c 2005

5/39

Jestliže poslední hrana na cesteˇ z koˇrene r do uzlu x je hrana (y , x), potom se uzel y nazývá rodicˇ uzlu x a uzel x je díteˇ (pˇrímý potomek) uzlu y . Koˇren stromu je jediným uzlem ve ˇ Dva uzly mající stejného rodiˇce se nazývají stromu bez rodice. sourozenci. Uzel bez potomku˚ se nazývá externí uzel nebo-li list. Nelistový uzel se nazývá vnitˇrní uzel.

c 2005



6/39






Koˇrenové stromy a seˇrazené stromy Seˇrazený (ordered tree) je koˇrenový strom, ve kterém jsou pˇrímí potomci každého uzlu seˇrazeni. Tudíž, pokud uzel má k ˇ lze urˇcit prvního pˇrímého potomka, druhého pˇrímého detí, potomka, až k -tého pˇrímého potomka.

Poˇcet pˇrímých potomku˚ uzlu x v koˇrenovém stromu se nazývá stupenˇ uzlu x. Poznamenejme, že stupenˇ uzlu závisí na tom, zda strom T uvažujeme jako volný strom nebo jako koˇrenový strom.

ˇ je stupenˇ poˇcet sousedních uzlu. V prvním pˇrípade, ˚ ˇ – V koˇrenových stromech je stupenˇ definován jako poˇcet detí tedy rodiˇc uzlu se nebere v úvahu. Délka cesty od koˇrene ˇ k uzlu x se nazývá hloubka uzlu x ve stromu T . Nejvetší hloubka libovolného uzlu se nazývá výška stromu T .

c 2005





7/39

Binární stromy

c 2005





8/39

Binární stromy

ˇ Binární strom lze nejlépe definovat rekurzivne. Binární strom je struktura definovaná nad koneˇcnou množinou uzlu, ˚ která: neobsahuje žádný uzel je složena ze tˇrí disjunktních množin uzlu: ˚ koˇrene, binárního stromu zvaného levý podstrom a binárního stromu tzv. pravého podstromu.

c 2005





9/39

Binární stromy




10/39

Umíst’ování informace odlišující binární stromy od seˇrazených ˇ ˇ stromu, ˚ lze rozšíˇrit na stromy s více než dvema detmy uzlu. ˇ V pozicním stromu (positional tree) jsou jednotliví pˇrímí potomci oˇcíslováni kladným celým cˇ íslem.

Binární strom není jen seˇrazený strom, ve kterém má každý uzel stupenˇ nejvýše dva. Napˇríklad, v binárním stromu, jestliže uzel má pouze jednoho pˇrímého potomka, potom fakt, že pˇrímý potomek je levý nebo pravý je duležitý. ˚ V seˇrazeném stromu není u jediného pˇrímého potomka možnost rozlišit, zda je pravý nebo levý.



Binární stromy

Binární strom, který neobsahuje žádný uzel se nazývá prázdný strom. Jestliže levý podstrom je neprázdný, jeho koˇren je levým pˇrímým potomkem koˇrene celého stromu. Stejneˇ tak, koˇren neprázdného pravého podstromu se nazývá pravým pˇrímým potomkem koˇrene daného stromu.

c 2005

c 2005


ˇ Ríkáme, že i-tý pˇrímý potomek chybí, jestliže neexistuje pˇrímý potomek oznaˇcen cˇ íslem i. n-ární strom je poziˇcní strom, kde v každém uzlu, všichni pˇrímí potomci s cˇ íslem vyšším než n chybí. Proto binární strom je n-ární strom s n = 2.

11/39

c 2005



12/39




Binární stromy


Binární stromy Úplný n-ární strom je n-ární strom, ve kterém všechny listy mají stejnou hloubku a všechny vnitˇrní uzly mají stejný stupenˇ n. Koˇren stromu má n potomku˚ s hloubkou 1, z nichž každý má n potomku˚ s hloubkou 2 atd. Tedy, poˇcet listu˚ v hloubce h je nh . ˇ hloubka úplného n-árního stromu s m listy je logn m. Následne, Poˇcet interních uzlu˚ úplného n-árního stromu výšky h je 1 + n + n2 + · · · + nh−1 =

h−1 i=0

c 2005





c 2005

13/39

Binární vyhledávací stromy

ni =

nh − 1 n−1





14/39

Binární vyhledávací stromy

Binární vyhledávací strom je organizován jako binární strom. ˇ implementují pomocí Binární vyhledávací stromy se nejˇcasteji dynamických struktur. Každý uzel potom obsahuje klíˇc, na jehož doméneˇ je definováno uspoˇrádání. Dále každý uzel obsahuje ukazatele left a right na svého levého a pravého ˇ pˇrímého potomka. Jestliže nekterý pˇrímý potomek chybí, je patˇriˇcná položka nastavena na nulový ukazatel (NULL, null). Uzel samozˇrejmeˇ muže ˚ obsahovat i další data v závislosti na povaze aplikace.

c 2005





Klíˇce v binárním vyhledávacím stromu jsou vždy uspoˇrádány ˇ vlastnost binárních vyhledávacích stromu: tak, že splnují ˚ Necht’ x je uzel v binárním stromu. Jestliže y je z levého podstromu uzlu x, potom key[y ] ≤ key[x]. Jestliže y je z pravého podstromu uzlu x, potom key[x] ≤ key[y ].

c 2005

15/39

Vkládání do binárního stromu (Insert)





16/39

Vkládání do binárního stromu Mohou nastat tyto pˇrípady: 1

Vkládání do binárního vyhledávacího stromu probíhá obdobneˇ jako vyhledávání v takovém stromu. Nejprve je nutno urˇcit kam bude prvek vložen. Vzhledem k uspoˇrádání klíˇcu˚ ve stromu je ˇ Stejneˇ jako pˇri vyhledávání takové místo urˇceno jednoznaˇcne. ˇ sestupujeme rekurzivneˇ od koˇrene dolu˚ smerem k listum. ˚ Vkládaný prvek x porovnáme s koˇrenem r zkoumaného podstromu.

2

strom s koˇrenem r je prázdný (r = NULL/null), vytvoˇríme nový uzel. ˇ srovnáme klíˇc k s klíˇcem koˇrene V opaˇcném pˇrípade, práveˇ zkoumaného stromu resp. jeho podstromu r . ˇ že V pˇrípade, 1

2

3

c 2005



17/39

key(x) < key(r ): pokraˇcujeme rekurzivneˇ levým podstromem; key(x) = key(r ): prvek x byl nalezen ve stromu. Záleží na konkrétní aplikaci, jak naloží s duplicitními výskyty prvku. ˚ key(x) > key(r ): pokraˇcujeme rekurzivneˇ pravým podstromem.

c 2005



18/39




Binární stromy


BinaryTree.Insert() – Implementace 1/4 public class BinaryTreeNode { public BinaryTreeNode mLeftChild = null; public BinaryTreeNode mRightChild = null; public int mKey = -1; public BinaryTreeNode(int value) { mKey = value; } }

c 2005





19/39

BinaryTree.Insert() – Implementace 2/4

for ( ; ; ) {







20/39

if (currentNode == null) { currentNode = new BinaryTreeNode(value); if (oldNode != null) { if (rightf) { oldNode.mRightChild=currentNode;} else { oldNode.mLeftChild=currentNode; } } else { mRootNode = currentNode; } break; }

public void Insert(int value) { BinaryTreeNode currentNode = mRootNode; BinaryTreeNode oldNode = null; boolean rightf = false;




public class BinaryTree { BinaryTreeNode mRootNode = null;

c 2005

c 2005

21/39


c 2005





22/39

Vyhledávání v binárním stromu (Find)

else { if (value < currentNode.mKey) { oldNode = currentNode; currentNode = currentNode.mLeftChild; rightf = false; } else if (value > currentNode.mKey) { oldNode = currentNode; currentNode = currentNode.mRightChild; rightf = true; } else { break; } }

Vyhledání prvku, zda je cˇ i není ve stromu. Mimo tuto operaci Find lze na binárních stromech implementovat i operace ˇ Minimum a Maximum. Všechny zmínené operace pracují v cˇ ase O(h), kde h je výška stromu. Metoda vyhledání daného prvku v binárním stromu, lze ˇ nejjednodušeji realizovat, jak je u stromu˚ obvyklé, rekurzivne. ˇ Mejme dánu množinu M reprezentovanou binárním stromem ˇ a jeho koˇren r . Dále mejme dán prvek s klíˇcem k , který hledáme. Základem vyhledávací procedury je uspoˇrádaní klíˇcu˚ ve stromu. Hledání zahájíme v koˇreni stromu r .

} c 2005



23/39

c 2005



24/39




Vyhledávání v binárním stromu


Binární stromy

Potom mohou nastat tyto možnosti: Strom s koˇrenem r je prázdný (r = NULL/null), potom tento strom nemuže ˚ obsahovat prvek s klíˇcem k , k ∈ / M. V opaˇcném pˇrípadeˇ srovnáme klíˇc k s klíˇcem koˇrene práveˇ ˇ že zkoumaného stromu resp. jeho podstromu r . V pˇrípade,

1

2

1 2

3

k = key(r ): strom obsahuje prvek s klíˇcem k , k ∈ M. k < key(r ): vzhledem k vlastnostem binárních vyhledávacích stromu, ˚ jsou všechny prvky s klíˇci menšími než je klíˇc r v jeho levém podstromu, pokraˇcujeme rekurzivneˇ v levém podstromu; k > key(r ): na rozdíl od pˇredchozího pˇrípadu jsou všechny ˇ prvky s klíˇci vetšími než je klíˇc r v pravém podstromu, pokraˇcujeme pravým podstromem.

c 2005





25/39

BinaryTree.Find() – Implementace 1/1








26/39

Prvek jehož klíˇc je minimem z množiny reprezentované daným stromem, lze v binárním stromu velice lehce najít sledováním ˇ pointeru˚ left od koˇrene až k listu. Prvek v nejlevejším listu je pak hledaným minimem. Pro maximum je kód symetrický. Obeˇ funkce pracují v cˇ ase O(h), kde h je výška stromu.

while(currentNode != null) { if (value < currentNode.mKey) { currentNode=currentNode.mLeftChild; } else if (value > currentNode.mKey) { currentNode=currentNode.mRightChild; } else { ret = true; break; } } return ret; c 2005


Hledání minima a maxima

public boolean Find(int value) { BinaryTreeNode currentNode = mRootNode; boolean ret = false;

}

c 2005

Binární vyhledávací strom zaruˇcuje, že postup vyhledání minima je korektní. Jestliže uzel x nemá levý podstrom, potom ˇ nebo rovny všechny klíˇce v pravém podstromu musí být vetší než klíˇc x.

27/39

Rušení uzlu˚ v binárním stromu (Delete)

c 2005





28/39

Rušení uzlu˚ v binárním stromu Pokud má x

ˇ pomocí Rušení uzlu˚ v binárním stromu je vhodné rˇešit opet rekurze. Nejdˇríve je nutné rušený prvek nalézt ve stromu. Postupujeme obdobneˇ jako v pˇrípadeˇ vyhledávání, tj. ˇ sestupujeme rekurzivneˇ od koˇrene dolu, ˚ smerem k listum. ˚ Pokud rušený prvek ve stromu není, procedura konˇcí bez jakékoliv cˇ innosti. Jinak pˇredpokládejme, že rušíme uzel x. Naše další cˇ innost bude záviset na poˇctu pˇrímých potomku˚ uzlu x.

c 2005



ˇ – to znamená, že uzel x je list a lze jej snadno od nula detí stromu odˇríznout. ˇ jedno díteˇ – uzel x již nelze snadno od stromu oddelit, protože odˇríznutím uzlu x bychom ztratili i jeho pˇrímého potomka. Vezmeme tedy pˇrímého potomka uzlu x, pˇriˇcemž je celkem lhostejné, zda je to pˇrímý potomek levý ˇ ukazatel nebo pˇrímý potomek pravý a napojíme na nej z rodiˇce uzlu x. Jinými slovy uzel x obejdeme, cˇ ímž se ˇ bezpeˇcneˇ vypojí ze stromu a mužeme ˚ jej uvolnit z pameti.

29/39

c 2005



30/39




Binární stromy


Rušení uzlu˚ v binárním stromu Pokud má x ˇ dva pˇrímé potomky – v tomto nejsložitejším pˇrípadeˇ musíme nahradit uzel x jeho pˇredchudcem ˚ resp. následovníkem, ve smyslu uspoˇrádání klíˇcu˚ uzlu. ˚ Pˇredpokládejme, že budeme nahrazovat pˇredchudcem. ˚ Pˇredchudce ˚ uzlu x je nutno hledat v jeho levém podstromu, kde jsou uloženy všechny prvky s klíˇci menšími než je klíˇc x. Jelikož pˇredchudcem ˚ rozumíme nejbližší menší prvek než x, nejblíže prvku x bude práveˇ maximum ze všech prvku˚ v levém podstromu uzlu x. ˇ Maximum ve stromu se nalézá v jeho nejpravejším uzlu. ˇ uzel z levého Struˇcneˇ ˇreˇceno, hledáme nejpravejší podstromu uzlu x. Tímto uzlem nahradíme uzel x.

c 2005





Pruchod ˚ stromem

Rozlišujeme tˇri základní uspoˇrádání, která jsou pˇrirozeným dusledkem ˚ stromové struktury. Podobneˇ jako samotný strom se ˇ i tato uspoˇrádání dají jednoduše vyjádˇrit rekurzivne.





33/39

Pruchod ˚ stromem


c 2005

1

Pˇrímé (preorder): R, A a B — nejprve byl navštíven koˇren pak jeho podstromy.

2

Vnitˇrní (inorder): A, R a B — nejprve levý podstrom, koˇren a nakonec pravý podstrom.

3

ˇ Zpetné (postorder): A, B a R — koˇren se navštíví až po podstromech.

c 2005





34/39


Je-li R prázdný strom (tj. R = NULL/null), pak poˇcet jeho uzlu˚ je nula.


ˇ Mejme napsat funkci, která spoˇcítá uzly ve stromu. Naše úloha ˇ se výrazneˇ zjednoduší uvedomíme-li si její rekurzivní charakter a pˇredpokládáme, že aktuální uzel je R:


32/39

Pˇríklad – Poˇcet uzlu˚


Tato schémata se rekurzivneˇ aplikují na celý strom. Je napˇríklad zˇrejmé, že pokud použijeme pruchod ˚ inorder budou jednotlivé uzly navštíveny v souladu s uspoˇrádáním klíˇcu˚ ve stromu. Pruchod ˚ postorder je vhodný napˇríklad v destruktoru ˇ tˇrídy pˇri dealokaci celého stromu z pameti.

Necht’ R oznaˇcuje koˇren stromu, A a B jeho levý resp. pravý podstrom.


Pruchod ˚ stromem

ˇ Jednotlivé uzly ve stromu se budou navštevovat v urˇcitém specifickém poˇradí a je možné si pˇredstavit, jako by uzly stromu byly lineárneˇ uspoˇrádané.

c 2005

c 2005

31/39

35/39

V opaˇcném pˇrípadeˇ víme, že ve stromu urˇciteˇ jeden uzel existuje (R) a poˇcty uzlu˚ v levém a pravém podstromu se ˇ To znamená, dají urˇcit obdobným zpusobem ˚ rekurzivne. že poˇcet uzlu˚ ve stromu s koˇrenem R je 1 + pocet_uzlu(A) + pocet_uzlu(B)

c 2005



36/39




Analýza vyhledávání a vkládání

Analýza vyhledávání a vkládání

ˇ Není težké najít nejhorší pˇrípad. Pˇredpokládejme, že všechny ˇ (at’ už sestupneˇ nebo vzestupne). ˇ Každý klíˇce jsou již setˇrídeny klíˇc je pˇri budování stromu pˇripojen nalevo (resp. napravo) ke svému rodiˇci a výsledný strom bude degenerovaný, jinými ˇ lineární seznam. Vyhledávání v takovém slovy stane se z nej pˇrípadeˇ bude vyžadovat n/2 porovnání.

Starosti pˇri použití binárního stromu zpusobuje ˚ pˇredevším skuteˇcnost, že se dost dobˇre neví, jak bude strom narustat; ˚ neexistuje v podstateˇ žádná pˇresná pˇredstava o jeho tvaru. Jediné co se dá pˇredpokládat je, že to nebude dokonale ˇ vyvážený strom. Prum ˚ erný poˇcet porovnání potˇrebných pro lokalizaci klíˇce v dokonale vyváženém stromu je pˇribližneˇ ˇ h = log n. Prum ˚ erný poˇcet porovnání v našem pˇrípadeˇ bude ˇ než h. Otázkou je o kolik bude vetší. ˇ urˇciteˇ vetší

c 2005





ˇ Nyní se pokusme stanovit prum ˚ ernou délku cesty vyhledávání vzhledem ke všem n klíˇcum ˚ a všem n! stromum, ˚ které lze vygenerovat z n! permutací n klíˇcu. ˚

37/39

Analýza vyhledávání a vkládání ˇ Prum ˚ erná délka cesty: an ∼ = 2[ln(n) + γ] − 3 = 2 ln(n) − c ˇ Protože prum ˚ erná délka cesty v dokonale vyváženém stromu je pˇribližneˇ an = log(n) − 1 dostáváme vztah lim

n→∞

an 2 ln n = 2 ln 2 = 1, 386 = an log n

Budeme-li se snažit za každou cenu zkonstruovat dokonale vyvážený strom, místo náhodného, mužeme ˚ za pˇredpokladu ˇ shodné pravdepodobnosti vyhledání všech klíˇcu, ˚ oˇcekávat ˇ prum ˚ erné zlepšení vyhledávání nejvíce o 39%. Prakticky je toto ˇ zlepšení významnejší. c 2005




39/39

c 2005



38/39

Volné stromy. Úvod do programování. Kořenové stromy a seřazené stromy. Volné stromy

Recommend Documents