sÚloha 1a.

 

Do následujícího kódu doplňte chybějící konstantu v podmínce tak, aby byla procedura xyz() volána právě 2100 krát.

 

for (i=0; i < 70; i++) {

  j = 0;

  do {

    if (j > ___ ) xyz();

    j++;

  } while (j < 90);

}

 

Řešení

Vnější cyklus probíhá od 0 do 69, celkem 70 krát. Musíme proto zajistit, aby ve vnitřním cyklu byla procedura xyz() volána právě 2100/70 = 30 krát. Toho docílíme pro hodnoty řídící proměnné j: 60, 61, ..., 88, 89. Chybějící konstanta je tedy 59.

 

 

Úloha 1b.

 

Do následujícího kódu doplňte chybějící konstantu v podmínce tak, aby byla procedura xyz() volána právě 2000 krát.

 

i = 50;

do {

  for (j=0; j < 70; j++)

    if (j > ___ ) xyz();

  i++;

} while (i < 150);

 

 

Řešení

Vnější cyklus probíhá od 50 do 149, celkem 100 krát. Musíme proto zajistit, aby ve vnitřním cyklu byla procedura xyz() volána právě 2000/100 = 20 krát. Toho docílíme pro hodnoty řídící proměnné j: 50, 51, ..., 68, 69. Chybějící konstanta je tedy 49.

 

 

Úloha 2a.

 

Do následujícího kódu doplňte chybějící výraz v podmínce tak, aby byla procedura uvw() volána právě 49 krát.

 

for (i = 0; i < 7; i++) {

  j = i;

  while (j < ___) {

    uvw();

    j++;

  }

}

 

Řešení

Vnější cyklus probíhá celkem 7 krát. Musíme proto zajistit, aby ve vnitřním cyklu byla procedura uvw() volána právě 49/7 = 7 krát.  Protože počítání ve vnitřním cyklu začíná pokaždé od aktuální hodnoty i, stačí do podmínky doplnit výraz i+7.

 

 

Úloha 2b.

 

Do následujícího kódu doplňte chybějící konstantu v podmínce tak, aby byla procedura uvw() volána právě 85 krát.

 

i = 0;

while (i < 10) {

  for (j = i; j < ___; i++)

    uvw();

  i++;

}

 

Řešení

Označme hledanou konstantu k. Při prvním průchodu vnějšího cyklu proběhne vnitřní cyklus k krát. Při druhém průchodu vnějšího cyklu proběhne vnitřní cyklus k-1 krát. Při třetím průchodu vnějšího cyklu proběhne vnitřní cyklus k-2 krát, atd. Protože vnější cyklus proběhne celkem 10 krát, platí rovnost:

k + (k-1) + (k-2) + (k-3) + ... + (k-8) + (k-9) = 85

Odstraněním závorek získáme :

10k - 1 - 2 - 3 - ... - 8 - 9 = 85

10k - 45 = 85

10k = 130

k = 13.

 

 

Úloha 3.

 

Metoda A potřebuje k vyřešení úlohy n2 + 17 operací, Metoda B potřebuje 2n + 80 operací, přičemž celé číslo n popisuje rozsah vstupních dat. Pro jaká n je výhodnější použít metodu A?

 

Řešení:

Metoda A je výhonější pro taková n, pro která platí n2 + 17 < 2n + 80, to jest, taková n, která splňují nerovnici

n2 – 2n – 63 < 0.

Kořeny příslušné kvadratické rovnice

n2 – 2n – 63 = 0

jsou

n1 = –7,

n2 = 9.

Pro n z intervalu (–7, 9) má tedy výraz n2 – 2n – 63 zápornou hodnotu, a proto je metoda A

výhodnější pro n < 9.

 

 

Úloha 4a.

 

V následujících vztazích doplňte na prázdná místa (........) symboly O nebo Q nebo W tak, aby vznikla pravdivá tvrzení. Je-li možností více, uveďte je všechny, nehodí‑li se ani jeden symbol, prázdné místo proškrtněte.

 

a) x2 ·2x Î ........((ln(x2))2 + 2x)

b) (ln(x2))2 + 2x Î ........(x2 + ln(x2) )

c) 2x · (ln(x)) -1 Ď ........(2x · (ln(x2))-1)

 

Řešení:

 

a) funkce  nalevo zřejmě roste rychleji než funkce napravo, neboť obě funkce obsahují výraz  2x, který je však nalevo vynásoben výrazem x2, jenž roste asymptoticky rychleji než (pouze!) aditivní výraz (ln(x2))2 napravo. Jediná správná možnost je proto

x2 ·2x Î W((ln(x2))2 + 2x).

 

b) funkce nalevo obsahuje člen 2x, funkce napravo je součtem dvou členů, které oba zřejmě rostou asymptoticky pomaleji než 2x. Funkce nalevo tedy roste asymptoticky rychleji, takže jediná správná možnost je

(ln(x2))2 + 2x Î W(x2 + ln(x2)).

 

c) funkci napravo lze napsat jako

2x · (ln(x2))-1 = 2x · (2·ln(x))-1 = 2-1 · 2x · (ln(x))-1

Tato funkce se od funkce nalevo liší jen o multiplikativní konstantu, takže obě funkce rostou asymptoticky stejně rychle. Platí tudíž všechny tři možnosti:

2x · (ln(x)) -1 Î O(2x · (ln(x2))-1)

2x · (ln(x)) -1 Î Q (2x · (ln(x2))-1)

2x · (ln(x)) -1 Î W (2x · (ln(x2))-1),

takže situace (se škrtnutým symbolem náležení) v zadání nemůže nastat, tudíž je nutno prázdné místo proškrtnout.

 

 

Úloha 4b.

 

V následujících vztazích doplňte na prázdná místa (........) symboly O nebo Q nebo W tak, aby vznikla pravdivá tvrzení. Je-li možností více, uveďte je všechny, nehodí‑li se ani jeden symbol, prázdné místo proškrtněte.

a) x2 · ln(x2) Î ........(x2 + ln(x))

b) x3 + ln(x2) Î ........(x3 + 2x)

c) x3 · ln(x2) Ď ........(ln(x2) + 2x)

 

Řešení:

a) funkce na pravé straně je součtem dvou funkcí, z nichž druhá -- ln(x) -- roste asymptoticky pomaleji než první -- x2. Celkem tedy funkce na pravé straně roste asymptoticky stejně rychle jako x2. Funkce na levé straně však díky multiplikativnímu členu ln(x2) roste asymptoticky rychleji než x2.

Tudíž platí právě

x2 · ln(x2) Î W(x2 + ln(x)).

 

b) funkce na pravé straně obsahuje exponenciální člen, funkce na levé straně jen člen polynomiální a logaritmický, jež vesměs rostou asymptoticky pomaleji než exponenciála, takže funkce na pravé straně roste asymptoticky rychleji, platí tedy právě:

x3 + ln(x2) Î O(x3 + 2x).

 

c) podle podobné úvahy jako v b) roste funkce na pravé straně asymptoticky rychleji než funkce na levé straně. Tudíž funkce na levé straně neroste ani asymptoticky stejně rychle ani neroste asymptoticky rychleji. Formálně vyjádřeno:

x3 · ln(x2) Ď Q(ln(x2) + 2x),

x3 · ln(x2) Ď W(ln(x2) + 2x).

 

 

Úloha 5a.

 

Uveďte příklad tří rostoucích funkcí reálné proměnné  f(x), g(x) a h(x), pro které současně platí všechny tři následující vztahy:

f(x) Ď O(g(x)),  g(x) Ď Q(h(x)),  h(x) Ď W(f(x))

 

Pokud taková trojice funkcí nemůže existovat, napište krátké zdůvodnění, proč.

 

Řešení.

První vztah říká, že f(x) musí růst asymptoticky rychleji než g(x), třetí vztah říká, že f(x) musí růst asymptoticky rychleji než h(x). Druhý vztah říká, že asymptotická rychlost růstu g(x) a h(x) není stejná. Můžeme tedy volit např.:

f(x)  = x2

g(x)  = x

h(x) = ln(x).

 

 

Úloha 5b.

 

Uveďte příklad tří rostoucích funkcí reálné proměnné  f(x), g(x) a h(x), pro které současně platí všechny tři následující vztahy:

f(x) Ď O(g(x)),  g(x) Ď W(h(x)),  h(x) Ď Q(f(x))

Pokud taková trojice funkcí nemůže existovat, napište krátké zdůvodnění, proč.

 

Řešení:

První vztah říká, že f(x) roste asymptoticky rychleji než g(x), druhý vztah říká, že g(x) roste asymptoticky pomaleji než h(x), celkem tedy g(x) roste asymptoticky pomaleji než f(x) i h(x). Poslední vztah pak říká, že f(x) a h(x) nerostou asymptoticky stejně rychle. Můžeme tedy volit např.:

f(x)  = x2

g(x)  = ln(x)

h(x) = x.

 

 

Úloha 6a.

 

V poli velikosti n mají všechny prvky stejnou hodnotu kromě posledního, který je menší.

Zatrhněte všechny možnosti, které pravdivě charakterizují asymptotickou složitost Insert Sortu (třídění vkládáním) pracujícího nad tímto konkrétním polem.

O(n)         W(n)          Q(n)         O(n2)            W(n2)             Q(n2)

 

Řešení:

Insert Sort postupuje od začátku pole a každý prvek zařadí do již seřazeného počátečního úseku pole. protože ale jsou všechny prvky stejně velké, zařazení každého prvku se redukuje na to, že bude ponechán na místě. To je operaces konstantní časovou složitostí, takže prvních n–1 prvků bude zpracováno v čase Q(n). Poslední prvek v poli je sice menší, takže patrně nebude zpracován v konstantním čase. Zpracování každého jednotlivého prvku při řazení Insert Sort-em má však složitost O(n), takže celková složitost řazení bude Q(n) + O(n) = Q(n). V zadání je tedy nutno zatrhnout možnosti O(n), W(n), Q(n), O(n2).          

 

 

Úloha 6b.

 

Pole n různých prvků je uspořádáno od druhého prvku sestupně, první prvek má nejmenší hodnotu ze všech prvků v poli.

Zatrhněte všechny možnosti, které pravdivě charakterizují asymptotickou složitost Select Sortu (třídění výběrem) pracujícího nad tímto konkrétním polem.

O(n)         W(n)          Q(n)         O(n2)            W(n2)             Q(n2)

 

Řešení:

Pro výběr aktuálního minima musí Select Sort pokaždé zkontrolovat všechny prvky od aktuálního až do konce pole, takže jeho složitost je je vždy právě Q(n2) nezávisle na datech v poli. V zadání je tedy nutno zatrhnout možnosti W(n), O(n2),  W(n2),  Q(n2)

 

 

Úloha 7.

 

Proveďte (v mysli nebo na papíře)  jeden průchod uvedeným polem, který v Quick Sortu rozdělí prvky na „malé“ a „velké“. Jako pivotní hodnotu zvolte hodnotu posledního prvku v poli. Napište, v jakém pořadí budou po tomto průchodu prvky v poli uloženy, a vyznačte, kde bude pole rozděleno na „malé“ a „velké“. 

6        10        8        5        7        2        3        9        1        4

 

Řešení:

4   1   3    2    |    7    5    8    9    10    6

 

 

Úloha 8a.

 

Následující posloupnost čísel představuje haldu uloženou v poli. Proveďte první krok fáze řazení v Heap Sortu (třídění haldou), tj. a) zařaďte nejmenší prvek haldy na jeho definitivní místo v seřazené posloupnosti a b) opravte zbytek tak, aby opět tvořil haldu.

 

   4   8  11  12   9  18  13  17  21  25

 

Řešení:

a) prohodíme první prvek s posledním:

   25   8  11  12   9  18  13  17  21  4

b) Prvek 25 necháme „propadnout“ („probublat“) haldou na odpovídající mu místo:

    8   9   11  12   25  18  13  17  21  4

 

 

Úloha 8b.

 

Následující posloupnost čísel představuje haldu uloženou v poli. Proveďte první krok fáze řazení v Heap Sortu (třídění haldou), tj. a) zařaďte nejmenší prvek haldy na jeho definitivní místo v seřazené posloupnosti a b) opravte zbytek tak, aby opět tvořil haldu.

 

   1   5   2  17  13  24   9  19  23  22

 

Řešení:

a) prohodíme první prvek s posledním:

   22   5   2  17  13  24   9  19  23  1

b) Prvek 22 necháme „propadnout“ („probublat“) haldou na odpovídající mu místo:

    2  5  9  17  13 24  22 19 23 1

 

 

Úloha 9.

 

V určitém problému je velikost zpracovávaného pole s daty rovna rovna 2n-2, kde n charakterizuje velikost problému. Pole se řadí pomocí Merge Sort-u (řazení sléváním).  

S použitím Q/O/W symboliky vyjádřete asymptotickou složitost tohoto algoritmu nad uvedeným polem v závislosti na hodnotě n. Výsledný vztah předložte v co nejjednodušší podobě.

 

Řešení:

Pole velikosti m řadí Merge Sort pokaždé v čase Q(m·log(m)).V našem případě je

m = 2n-2. I kdyby pole mělo velikost právě 2n (tedy ještě větší), byla by asymptotická složitost rovna

Q(2n·log(2n)) = Q(n·log(2n)) = Q(n· (log(2) + log(n))) = Q(n· log(2) + n · log(n)).

Protože výraz  n· log(2) roste asymptoticky pomaleji než n · log(n) můžeme dále psát:

Q(n· log(2) + n · log(n)) = Q(n · log(n)).

Závěr tedy je: Protože jak pole velikosti n, tak i pole velikosti 2n seřadí Merge Sort v asymptoticky stejném čase Q(n · log(n)), seřadí i pole velikosti 2n-2 v témž čase

Q(n · log(n)).

 

 

Úloha 10.

 

Následující posloupnost řetězců je nutno seřadit pomocí Radix Sortu (přihrádkového řazení). Proveďte první průchod (z celkových čtyř průchodů) algoritmu danými daty a napište, jak budou po tomto prvním průchodu seřazena.

 

IIYI  PIYY  YIII  YPPP  YYYI  PYPP  PIPI  PPYI

 

Řešení:

K dispozici budou tři „přihrádky“ označené symboly I, P a Y. První průchod pracuje s posledním symbolem v každém řetězci, takže obsah „přihrádek“ bude:

I :   IIYI  YIII  YYYI  PIPI  PPYI

P:   YPPP  PYPP

Y:   PIYY

 

 

 

Úloha 11a.

 

Vypište obsah jednotlivých uzlů daného stromu při průchodu v pořadí

a)      preorder

b)      postorder

 

 

 

 

 

 

Řešení:

a) preorder nejprve zpracuje (=vypíše) kořen aktuálního stromu a pak zpracuje levý a pak pravý podstrom tohoto kořene. Výpis pro daný strom tedy bude:

G D E A F C A B H I J K 

b) postorder nejprve zpracuje levý, pak pravý podstrom kořene aktuálního stromu a nakonec zpracuje (=vypíše) kořen. Výpis pro daný strom tedy bude:

A F E A B C D J K I H G 

 

 

Úloha 11b.

 

Vypište obsah jednotlivých uzlů daného stromu při průchodu v pořadí

c)      preorder

d)      postorder

 

 

 

 

 

 

 

Řešení:

a) preorder nejprve zpracuje (=vypíše) kořen aktuálního stromu a pak zpracuje levý a pak pravý podstrom tohoto kořene. Výpis pro daný strom tedy bude:

B O H M R L K J A E D V 

b) postorder nejprve zpracuje levý, pak pravý podstrom kořene aktuálního stromu a nakonec zpracuje (=vypíše) kořen. Výpis pro daný strom tedy bude:

M R H K L O E A V D J B

 

 

Úloha 12a.

 

Vypočtěte, kolik celkem času zabere jedno zavolání funkce rekur(4); za předpokladu, že provedení přikazu xyz(); trvá vždy jednu milisekundu a že dobu trvání všech ostatních akcí zanedbáme.

 

void rekur(int x) {

  if (x < 1) return;

  rekur(x-1);

  xyz();

  rekur(x-1);

}

 

Řešení:

Strom rekurzivního volání funkce rekur je binární vyvážený strom. při volání rekur(4) bude mít tento strom hloubku 5, uzly posledního (=nejhlubšího) „patra“ však budou odpovídat pouze provedení řádku if (x < 1) return;  a příkaz xyz() se tu neprovede.

V každém uzlu stromu rekurzivního volání do hloubky 4  bude tedy jednou proveden příkaz xyz(). Počet těchto uzlů je 1 + 2 + 4 + 8 = 15. Stejněkrát bude proveden i příkaz xyz().

 

 

Úloha 12b.

 

Určete, jakou hodnotu vypíše program po vykonání příkazu print(rekur(4));, když rekurzivní funkce rekur()  je definována takto:

int rekur(int x) {

  if (x < 1) return 2;

  return (rekur(x-1)+rekur(x-1));

}

Nedokážete-li výsledek přímo zapsat jako přirozené číslo, stačí jednoduchý výraz pro jeho výpočet.

 

Řešení:

Rekurzivní volání rekur(x-1)+rekur(x-1) můžeme zapsat jako 2*rekur(x-1) a potom máme:

rekur(4) = 2*rekur(3) = 2*2*rekur(2) = 2*2*2*rekur(1) =

= 2*2*2*2*rekur(0) = 2*2*2*2*2 = 32.

 

 

**************************************************************************************************************************************

Další řešené úlohy z DSA

 

Úloha 13

 

Pro kterou/které z následujících datových struktur:

 

1)         pole

2)         fronta

3)         zásobník

4)         tabulka

5)         seznam

6)         strom

7)         množina

 

a)  platí, že má předem daný počet prvků?

 

Řešení:

            Musí to být statická struktura. Čili  pole, nebo statická tabulka.

 

b) platí, že kdykoliv lze jednou operací přečíst kterýkoliv prvek?

 

Řešení:

            pole      - přečtu prvek pro libovolný index

            tabulka - přečtu prvek pro libovolný klíč

            množina - pro libovolný prvek zjistím, zda v množině je, nebo není. 

 

d) platí, že kdykoliv lze maximálně dvěma operacemi přečíst první prvek?

 

Řešení:

            pole        - get( pole, lower( pole ) )

                             lower vrátí dolní mez indexů a get přečte prvek s timto indexem

            fronta      - jednou operací front(pole) Přečtu prvek v čele fronty, který je "první" na řadě

            seznam  - Použiji operace "First" (přesune ukazovátko na začátek seznamu)

                            a pak "Read" (přečte prvek, na který ukazovátko ukazuje)

 

 

e) platí, že kdykoliv lze maximálně třemi operacemi přečíst poslední prvek?

 

Řešení:

            zásobník- jednou operací POP přečtu poslední prvek ve smyslu "naposledy vložený"

 

            seznam - last, prev, read - presneji read( prev( last( S ) ) ),

kde S je proměnná typu seznam

                          last     - přesune ukazovátko za poslední prvek seznamu

                          prev    - přesune ukazovátko na poslední prvek seznamu

                          read    - přečte poslední prvek, protože na něj ukazuje ukazovátko

                          

            pole      - get( pole, max( pole ) )

                          max    - vrátí horní mez indexů

                          get     - přečte prvek s maximálním indexem    

Úloha 14a

 

Napište mapovací funkci pro pole o šesti sloupcích a třech řádcích. Adresa prvního prvku je uložena v proměnné zacatek. Pole je uloženo po sloupcích. Sloupcové indexy mají rozsah 3,4,5,6,7,8. Řádkové indexy nabývají hodnot 5,6,7

 

Řešení:

 

 

 

 

 

 

 

 


 

m(i,j) = zacatek + ( i – 5 ) + ( j – 3 ) * 3

 

 

Úloha 14b

 

Napište mapovací funkci pro pole o šesti sloupcích a třech řádcích. Adresa prvního prvku je uložena v proměnné zacatek. Pole je uloženo po řádcích. Sloupcové indexy mají rozsah 13,14,15,16,17,18. Řádkové indexy nabývají hodnot 7,8,9

 

 

 

 

 

 

 

 


 

m(i,j) = zacatek + ( i – 7 ) * 6 + ( j – 13 )

 

Úloha 14c

 

Je dán datový typ Prvek s konstantami a:->Prvek, b:->Prvek, ….z->Prvek. Dále  je dán datový typ seznam, který je neformálně popsán následovně.

 

init: -> List       

prázdný seznam

insert(_,_): Elem, List -> List  

vložení prvku před ukazovátko. Ukazovátko zůstane ukazovat na prvek, na který ukazovalo před vložením

read(_): List -> Elem

přečtení prvku na který ukazuje ukazovátko

delete(_):List -> List

smazání prvku na místě ukazovátka, posun ukazovátka na následující prvek

first(_), last(_):List -> List

posun na první, za poslední prvek

next(_), prev(_):List -> List

posun na další, předcházející prvek

length(_): List -> Nat0

Vrátí délku (počet prvků) seznamu

 

Sestavte výraz, který popisuje následující seznam:

 

a b c d     ukazovátko ukazuje na c

 

Řešení:

Např:       prev( prev( insert(d, insert(c, insert(b, insert(a,init))))))

Nebo:      insert(b, insert(a, prev( prev( insert(d, insert(c, init))))))

V prázdném seznamu (výsledku operace init) ukazuje ukazovátko „za seznam“. Operace insert vkládá před ukazovátko. Proto musíme prvky vkládat pozpátku. Na závěr přesuneme ukazovátko na požadovaný prvek. Úloha má více řešení – v podstatě nekonečně mnoho, protože výraz může obsahovat libovolný počet párů operací insert a delete, které se vzájemně vyruší.

 

 

Úloha 14d

Zadání jako v předchozí úloze, jen výra má vypadat takto:

 

   a b c d     ukazovátko ukazuje na b

 

Řešení např:     

prev( prev( prev( insert(d, insert(c, insert(b, insert(a,init)))))))

 

 

Úloha 15a

 

Jsou dány prvky s klíči A-G. Pravděpodobnost dotazu na jednotlivé konkrétní klíče je dána níže uvedenou tabulkou. Metodou dynamického programování sestrojte optimální strom z hlediska operace FIND, tj, najděte takový strom, v němž průměrný počet dotazů na hodnotu klíče během jedné operace FIND je nejmenší (Předpokládáme, že obsah stromu se dlouhodobě nemění). Napište, jak vypadá tabulka ohodnocení optimálních podstromů a tabulka jejich kořenů a výsledný strom namalujte.

 

A: 0.10

B: 0.10

C: 0.25

D: 0.35

E: 0.10

F: 0.05

G: 0.05

 

Řešení:

Nejlepší je se podívat do přednášky, kde je vše pěkně popsáno a definováno. Zde jen několik „praktických“ poznámek.

 

 

Tabulka ohodnocení optimálních podstromů t

               

-          Má stejný počet řádek, jako je počet uzlů. Řádkový index odpovídá počátečnímu uzlu L z intervalu uzlů L..R,

-          má o jeden sloupec více, než je uzlů. Sloupcový index odpovídá koncovému uzlu R z intervalu uzlů L..R,.

-          je dobré si uvědomit, že uzly mají pevně dané pořadí (jejich klíče jsou uspořádány)

-          má tedy pod diagonálou samé nuly, protože podstrom s L < R nemá smysl,

-          vše pod diagonálou chápeme jako prázdný podstrom,

-          na diagonále jsou hodnoty „jednouzlových“ podstromů, tedy přímo pravděpodobnost dotazu (1-krát, neboť hloubka je 1. V předchozích přednáškách byla hloubka stromu s jedním uzlem definována jako rovna nule. Uváděním hloubky od jedné vznikl trochu zmatek. Konzistentnější by bylo ponechat hloubku stromu s jedním uzlem rovnu nule a uvádět, že hodnotu pravděpodobnosti dotazu uzlu vynásobíme hloubkou uzlu zvětšenou o 1.),

 


 

 

-          Při vyplňování tabulky musíme do políčka o souřadnicích t[L,R] vyzkoušet všechny možné polohy kořene v rámci intervalu L..R. Pro L=A a L = C jsou možnosti následující:

 

Opt B,C znamená optimální podstrom sestávající z uzlů B a C, tj. výsledek předchozího kroku dynamického programování. Je to ten, jehož ohodnocení bylo menší, v našem případě podstrom s kořenem C.

 

 

 

 

A

B

C

D

E

F

G

 

 

 

A

B

C

D

E

F

G

 A

0

0.1

0.3

0.75

1.45

1.75

1.9

2.1

 

A

-

A

AB

C

C

CD

D

D

B

0

0

0.1

0.45

1.15

2.03

1.5

1.7

 

B

-

-

B

C

CD

D

D

D

C

0

0

 

0.25

0.85

1.05

1.2

1.4

 

C

-

-

 

C

D

D

D

D

D

0

0

 

 

0.35

0.55

0.7

0.9

 

D

-

-

 

 

D

D

D

D

E

0

0

 

 

 

0.1

0.2

0.35

 

E

-

-

 

 

 

E

E

EFG

F

0

0

 

 

 

 

0.05

0.15

 

F

-

-

 

 

 

 

F

FG

G

0

0

0

 

 

 

 

0.05

 

G

-

-

 

 

 

 

 

G

  Zažlucená políčka jsou nejednoznačná, protože vyjde stejná hodnota pro více různých kořenů.

 

Např. hodnota pro podstrom BCD na pozici t[B,D] se vypočítá jako:

0.1+0.25+0.35 + min(0+0.85, 0.1+0.35, 0.45+0)  = 0.7 + min( 0.85,  0.450.45) = 1.15

Výsledný strom tedy může vypadat například takto:

 

 

 

*****************************************************

 

Úloha 16

Čísla ze zadané posloupnosti postupně vkládejte do prázdného binárního vyhledávacího stromu (BVS), který nevyvažujte. Jak bude vypadat takto vytvořený BVS?

Poté postupně odstraňte první tři prvky. Jak bude vypadat výsledný BVS?

 

Řešení

Při vytváření BVS je potřeba dodržet jednoduché pravidlo: v levém podstromu každého vnitřního uzlu BVS (kořeni podstromu)  jsou klíče s menší hodnotou, v pravém podstromu zase klíče s větší hodnotou, než má kořen podstromu.

Nový prvek vkládáme vždy odshora. Začneme porovnáním s kořenem stromu a podle výše zmíněného pravidla postupujeme vlevo, když je klíč vkládaného prvku menší, nebo vpravo, když je větší, než klíč kořene. To opakujeme tak dlouho, dokud je ve zvoleném směru nějaký uzel. V okamžiku, když už nemůžeme dál pokračovat, vložíme nový uzel tam, kam by vedl další postup. Pamatujte si, že nově vkládaný prvek je vždy listem.

 

Odstranění prvku z BVS není už tak jednoduché. Zatímco při vkládání vznikne vždy list, odebírání se týká všech uzlů BVS. V případě, že je rušený prvek uvnitř stromu, musíme jeho podstromy znovu „zapojit“ do BVS tak, aby výsledkem byl zase BVS.

 

1.    Odstranění prvku na pozici listu je jednoduché. Prostě jej vypustíme.

2.    Pokud má odstraňovaný prvek jeden podstrom, stačí podstrom napojit na rodiče rušeného prvku.

3.    Nejtěžší případ nastane při rušení prvku, který má oba podstromy. Místo manipulace s podstromy nahradíme rušený prvek vhodným kandidátem vybraným z jednoho z podstromů. Vzhledem k tomu, že i po zrušení prvku musí být strom stále BVS, je potřeba zajistit, aby nově vložený prvek byl větší, než zbylé prvky levého podstromu a menší, než zbylé prvky pravého podstromu. Tuto podmínku splňují 2 kandidáti: největší prvek z levého podstromu, nebo nejmenší prvek z pravého podstromu. Je jedno, který z nich si vybereme.

1.    Najdeme největší prvek v levém podstromu. U toho je zaručeno, že určitě sám nemá pravý podstrom (jinak by nebyl největší) a proto nebude problém jej pomocí postupu z bodů 1, nebo 2 odstranit.

2.    Hodnotu z tohoto prvku vložíme do rušeného uzlu.

 

 

Posloupnost a)

            14 24 5 13 1 3 22 10 19 11


 

 


 


 


 

 

 

 

 

Posloupnost b)

            10 16 5 17 4 15 3 1 23 13 2 11


 


 


 


 

 

Posloupnost c)

            17 4 15 2 5 9 1 12 3 19 16 18


 


 


 


 

 

 

Úloha č. 17

Napište proceduru popisující XX rotaci binárního stromu. Nemusíte testovat nenulovost ukazatelů.

 

Při psaní této procedury je důležité si uvědomit, v jakém pořadí se mají jednotlivá přiřazení provádět. Špatné pořadí může způsobit rozpojení struktury BVS.

 

Procedury používají následující datovou strukturu pro uzel BVS:

typedef struct _uzel {

       int klic; //hodnota klice, ktera bude ulozena v uzlu;

       _uzel *l; //ukazatel na levy podstrom

       _uzel *p; //ukazatel na pravy podstrom

       _uzel *r; //ukazatel na rodice

} uzel;

 

XX=Levá rotace

 

uzel* Lrotace(uzel *k) //vstupem je koren podstromu, ve kterem se rotuje. Vystupem je novy koren

{

 uzel *p;

 

 p = k->p; //do p se ulozi koren praveho podstromu

 k->p = p->l; //p se stane novym korenem, takze je potreba jeho levy podstrom presunout. Stane se pravym podstromem puvodniho korene.

 p->l = k; //puvodni koren se posune do leveho podstromu

//nyni je potreba spravne nastavit ukazatele na rodice

 p->r = k->r;

 

//potrebujeme zjistit, jestli byl puvodni koren v levem, nebo pravem podstromu rodice a podle toho upravit odkaz na novy koren

 if( p->r->l->klic == k->klic )

        p->r->l = p;

       else

        p->r->p = p;

 k->r = p; //puvodni koren je pod p, takze se p stava jeho rodicem

 return p;

}

 

 

XX=LR rotace (dvojitá)

 

uzel* LRrotace(uzel* k)

{

 uzel *p1,*p2;

 

 p1 = k->l;

 p2 = p1->p;  //p2 bude novym korenem

 p1->p = p2->l;

 p2->l = p1;

 k->l = p2->p;

 p2->p = k;

 

 //nyni je potreba spravne nastavit reference na rodice

 p1->r = p2;

 p2->r = k->r;

 k->r = p2;

 

//potrebujeme zjistit, jestli byl puvodni koren v levem, nebo pravem podstromu rodice a podle toho upravit odkaz na novy koren

 if( p2->r->l->klic == k->klic )

        p2->r->l = p2;

       else

        p2->r->p = p2;

 

 return p2;

}

 

Všechny přesuny během rotací musí zachovat relativní pozici všech uzlů. Pokud byl uzel A vlevo od uzlu B (třeba i nepřímo tak, že byl součástí levého podstromu B), musí zůstat vlevo od B i po rotaci. Pokud by se A dostal v BVS po provedení rotace nad B, musí být B v pravém podstromu A.