Algoritmy a datové struktury

Úvod Pole a seznamy Stromy Binární stromy Binární vyhledávací stromy Konec

Algoritmy a datové struktury Stromy

1 / 32


Obsah přednášky

I

Pole a seznamy

I

Stromy

I

Procházení stromů

I

Binární stromy

I

Procházení BS

I

Binární vyhledávací stromy

2 / 32


Pole

I

Hledání v poli metodou půlení intervalu I

najít 18 1 5

I

8

10

12

3 15

2 18

20

22

24

Vkládání do pole I

vložit 19 19 5

8

10

12

15

18

20

22

24

3 / 32


Seznamy

I

Vyhledávání v seznamu lineárním vyhledáváním I

najít 18 1

2

5

I

3

4

5

6

10

12

15

18

8

20

22

24

Vkládání do seznamu I

vložit 19 19

5

8

10

12

15

18

x

20

22

24

4 / 32


Porovnání

I

Získat obě výhody I I

I I

rychlé vyhledávání snadné vkládání

S polem moc nadějí nemáme Vylepšit seznam I

upravit seznam tak, aby místo na sousedy ukazovaly prvky na poloviny intervalů

5

8

10

12

15

18

20

22

24

5 / 32


Finální úprava

15

8

5

20

10

18

12

22

24

6 / 32


Co je strom? I I

Strom je množina uzlů Existuje jeden startovací uzel I

I I

kořen stromu

Každý uzel kromě kořenu má rodiče Uzel může mít libovolné množství dětských uzlů I

pokud nemá děti, je to list

7 / 32


Co je strom?

I

Přirozená rekurzivní datová struktura

I

Zachycuje vztahy mezi prvky stromu Velké množství aplikací

I

I I I I I

souborový systém dědičnost v OOP hokejová extraliga rodokmen ...

8 / 32


Cesta k uzlu I

Posloupnost uzlů: kořen, u1, u2, . . . I

I

Ke každému uzlu existuje právě jedna cesta I

I

kde u1 je potomkem kořene, u2 potomkem u1, . . . kdyby ne, nebyl by to strom

Délka cesty od kořene k uzlu určuje jeho hloubku

9 / 32


Implementace I

Pomocí referencí - podobně jako seznamy I

u obecných stromů mohou být i odkazy na děti spojový seznam Hodnota

Hodnota

Hodnota

Hodnota

Hodnota

Hodnota

Hodnota

10 / 32


Procházení stromů – Pre-order I

Vypíše kořen stromu, rekurzivně pokračuje pro všechny podstromy Preorder ( uzel v ) { vypis ( v ); foreach ( detskyUzel u in v ) Preorder ( u ); }

I

Aplikace: strukturované dokumenty (XML) Kniha Kapitola 1 Podkapitola 1.1

Podkapitola 1.2

Kapitola 2

Kapitola 3

Podkapitola 2.1

11 / 32


Procházení stromů – Post-order I

Vypíše rekurzivně všechny podstromy, nakonec vypíše kořen Postorder ( uzel v ) { foreach ( detskyUzel u in v ) Postorder ( u ); vypis ( v ); }

I

Aplikace: zjištění velikosti podadresářů na disku c:\ Temp data.txt

Windows win.com

win.bmp

Program Kresleni

Psani

12 / 32


Procházení stromů – Level-order

I

Vypíše všechny uzly se stejnou hloubkou

I

Aplikace: hledání nejkratší cesty A C

D

B

B

13 / 32


Prohledávání stromů – do hloubky

I

Depth-First Search (DFS)

I

Nejprve se navštíví všechny děti, potom rodič Příklad

I

I

3 10 8 12 7 4 3 6 5 5 8 3

12 10

4

6 7

3

14 / 32


Prohledávání stromů – do šířky I

Ekvivalent level-order

I

Breadth-First Search (BFS)

I

Navštíví všechny uzly se stejnou hloubkou Příklad

I

I

5 8 12 4 6 3 10 7 3 5 8 3

12 10

4

6 7

3

15 / 32


Definice I

Rekurzivní definice I

binární strom je I I

I

prázdný strom, nebo uzel obsahující klíč, data, a levý a pravý binární podstrom

Rekurzivní přístup s výhodou využijeme i při práci se stromem

16 / 32


Příklad class BinarniUzel {

public Klic klic ; public BinarniUzel levy , pravy ; public BinarniUzel ( Klic klic ) {

this . klic = klic ; levy = null ; pravy = null ; } }

class BinarniStrom {

public BinarniUzel koren ; public BinarniStrom ( Klic klic ) {

koren = new BinarniUzel ( klic ); } } 17 / 32


Procházení stromů – In-order I

Vypíše rekurzivně všechny podstromy, nakonec vypíše kořen Inorder ( uzel v ) { Inorder ( v . levy ); vypis ( v ); Inorder ( v . pravy ); }

I

Aplikace: výpis aritmetických operací I

a · (b + c)

. a

+ b

c 18 / 32


Binární vyhledávací stromy I I

Binary Search Tree (BST) Binární strom s vlastnostmi I I I

uzly obsahují klíče, u kterých lze určit relace <,>,= klíče uzlů U ležících nalevo od kořene K jsou menší než klíč kořene K klíče uzlů U ležících napravo od kořene K jsou větší než klíč kořene K 15 8 5

20 10

18 12

22 24

19 / 32


Vyhledávání v BST I I

Začátek v kořenu stromu Porovnáme hodnotu klíče I I I

I

pokud se rovná hledané hodnotě, nalezli jsme pokud je menší, pokračujeme v levém podstromu pokud je větší, pokračujeme v pravém podstromu

Dojdeme-li do listu, který je jiný než hledaná hodnota, strom hledaný prvek neobsahuje I

Příklad I

najít 18 1 15

2

8 5

3 10

18 12

20 22 24 20 / 32


Vyhledávání v BST public BinarniUzel Najdi ( Klic klic ) { return Najdi ( koren , klic ); } public BinarniUzel Najdi ( BinarniUzel uzel , Klic klic ) { if ( uzel == null ) return null ; if ( klic < uzel . klic ) return Najdi ( uzel . levy , klic ); else if ( klic > uzel . klic ) return Najdi ( uzel . pravy , klic ); else return uzel ; } I

Složitost vyhledávání?

I

Jak se změní když zvýšíme počet dětí?

I

Jak se změní když snížíme počet dětí? 21 / 32


Nalezení nejmenšího/největšího prvku

I

Rekurzivně dojít k nejlevějšímu/nejpravějšímu uzlu stromu public BinarniUzel Min () { BinarniUzel min = null ; for ( BinarniUzel u = koren ; u != null ; u = u . levy ) { min = u ; } return min ; }

22 / 32


Vkládání prvku do BST

I

Nalezení místa vhodného pro prvek Pokud už prvek existuje pak nedělat nic Pokud neexistuje, vložit prvek na nalezené místo

I

Příklad

I I

I

vložit 9 15 8

20

5

10 9

18 12

22 24

23 / 32


Vkládání prvku do BST public void Pridej ( Klic klic ) { BinarniUzel aktualni , rodic ; aktualni = koren ; rodic = null ; while ( aktualni != null ) { rodic = aktualni ; if ( klic < rodic . klic ) aktualni = aktualni . levy ; if ( klic > rodic . klic ) aktualni = aktualni . pravy ; if ( klic == rodic . klic ) break ; } if ( rodic == null ) koren = new BinarniUzel ( klic ); if ( klic < rodic . klic ) rodic . levy = new BinarniUzel ( klic ); if ( klic > rodic . klic ) rodic . pravy = new BinarniUzel ( klic ); } 24 / 32


Mazání prvku

I

Při mazání je nutné postarat se o děti

I

Musí být zachovány vlastnosti BST Jaké situace mohou nastat?

I

I I I

I

mazaný uzel nemá žádné potomky mazaný uzel má pouze jednoho potomka mazaný uzel má oba potomky

Nebo I I I

mazaný uzel nemá levého potomka mazaný uzel nemá pravého potomka mazaný uzel má oba potomky

25 / 32


Nalezení mazaného prvku

BinarniUzel aktualni , rodic ; aktualni = koren ; rodic = null ; while (( aktualni != null )&&( aktualni . klic != klic )) { rodic = aktualni ; if ( klic < rodic . klic ) aktualni = aktualni . levy ; if ( klic > rodic . klic ) aktualni = aktualni . pravy ; if ( klic == rodic . klic ) break ; } if ( aktualni == null ) prvek_nenalezen

26 / 32


Uzel nemá levého potomka

I

Rodičovskému uzlu přiřadíme místo mazaného prvku jeho pravého potomka

if ( aktualni . levy == null ) { if ( klic < rodic . klic ) { rodic . levy = aktualni . pravy ; } else { rodic . pravy = aktualni . pravy ; } }

15 8

x 5

27 / 32


Uzel nemá pravého potomka

I

Rodičovskému uzlu přiřadíme místo mazaného prvku jeho levého potomka

else if ( aktualni . pravy == null ) { if ( klic < rodic . klic ) { rodic . levy = aktualni . levy ; } else { rodic . pravy = aktualni . levy ; } }

28 / 32


Uzel má oba potomky I

Rodičovskému uzlu přiřadíme nejlevější prvek z pravého potomka

else { BinarniUzel nejlevejsi = aktualni . pravy . levy , nejlevejsiRodic = aktualni . pravy ; while ( nejlevejsi . levy != null ) { nejlevejsiRodic = nejlevejsi ; nejlevejsi = nejlevejsi . levy ; }

15

nejlevejsiRodic . levy = nejlevejsi . pravy ; nejlevejsi . levy = aktualni . levy ; nejlevejsi . pravy = aktualni . pravy ; if ( klic < rodic . klic ) rodic . levy = nejlevejsi ; else rodic . pravy = nejlevejsi ;

x 8

9

} 29 / 32


”Líné” mazání prvku

I

Pro velké stromy může být mazání poměrně náročné

I

Místo fyzického smazání označit uzel jako neplatný, ale ponechat ho ve stromu Problémy?

I

I I

zvyšuje se hloubka stromu (nebo spíš nesnižuje se při mazání) pro velké stromy u kterých je počet smazaných prvků srovnatelný s počtem stávajících prvků to není kritické

30 / 32


Všechno funguje pěkně ale. . . I I

Co se stane když budou vrcholy vkládány v ”nešikovném” pořadí Příklad: 5 7 10 11 13 I I

jaká je složitost hledání? co se s tím dá vymyslet? 5 7 10 11 13

31 / 32


Konec

32 / 32

Algoritmy a datové struktury

Recommend Documents