[Zk] 13.2.2014

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.
zzz

[Zk] 13.2.2014

Příspěvek od zzz »

Tentokrat som dostal cerveno-cierne stromy (neupresnil, co chce pocut).

Napisal som:
ideu (BVS, farbenie vrcholov, oprava stromu ked sa porusia pravidla v algoritme),
motivaciu preco je to dobre (mensia hlbka oproti AVL),
definiciu formalnejsie (aj definicie {2,3}-takmer cerveno-cierneho stromu a poruchy v nich),
hlbku stromu (cez pocet vrcholov - odhad zdola ked su same cierne vrcholy, zhora ked sa striedaju cierne/cervene),
algoritmy insert a delete (strucne slovne popisane pripady + obrazky s oznacenymi vrcholmi ku kazdemu).
Trvalo mi to asi 2h a vyslo to na 2 A4 husto popisane.

Potom prisiel Koubek a pytal sa co zatial mam, tak som mu povedal ze som sa este nedostal ku zlozitosti. Precital si co mam, spytal sa 2 veci (nieco s poctom ciernych vrcholov na cestach cez poruchu v 2-takmer cerveno-ciernom strome, ci su vsetky rovnake a tak a upresnenie jedneho pripadu v delete). Kupodivu za 1.

Dalsie otazky napr.: Fibonacciho haldy, Huffmanovo kodovanie, AVL stromy.
Odpovědět

Zpět na „TIN066 Datové struktury I“