GPS, Utorok, 10.12.2002

• Najprv link na DU

Hovoril som daco o:

• binarnych prehladavacich stromoch (Binary Search Trees), konkretne operacie Min, Max, Search, Prev (predchodca), Succ (nasledovnik), Insert, Delete. Vsetky bezia (ak ich tak napiseme) v O(H), kde H je vyska stromu.
• cerveno-cierno-cervenych a ciernych :-) stromoch (Red-Black Trees). Operacie Min, ... Succ su rovnake, lebo RB-Tree ma zachovane vlastnosti BST. Ako ste sami zistili, sranda je s Insertom, k Delete sme sa ani nedostali. Kratka intuitivna predstava, preco vyska RB-stromu je radovo O(log N): Predstavme si, ze mame RB-Tree, kde su vsetky vrcholy cierne. Z vlastnosti, ze pocet ciernych vrcholov na kazdej ceste z niektoreho vrcholu, je rovnaky, nam vravi, ze nas RB-Tree musi byt uplny, teda jeho vyska je O(log N). Teraz ta intuitivna predstava: vezmime si lubovolnu cestu z vrchola do nejakeho listu - v nasom pripade je dlzky O(log N) - a pridajme nejake cervene vrcholy. Podla jednej z vlastnosti RB-stromov, nesmu ist "dva cervene po sebe", teda ich tam mozeme pridat maximalne tolko, co bolo ciernych plus minus jedna. Teda sa vyska stromu (radovo) nezmeni ani po pridani cervenych vrcholov.

Nejake linky, kde su obe struktury vysvetlene viac-menej "po lopate" (akurat, ze po anglickej lopate :( - ale to by snad nemusel byt problem...)

• BS-Trees
• RB-Trees

A teraz domaca uloha na dalsie GPS (poslite mi to mailom do pondelka vecera 16.12.2002):

1. Vlozte prvok s klucom 36 do RB-stromu na obrazku:
   
   Riesenie poslite bud nejako na obrazku (postupne rotacie...) alebo to popiste a poslite vysledny obrazok (tvar stromu a farby vrcholov). Pomozu vam pri tom vyssie linky (su tam aj obrazky :-)
   Body: 0 - 5
2. Este na temu z minula: Vo vaznici by radi mali system, ktory im bude hovorit informacie o vaznoch. Totiz, obcas (zas nie tak zriedka) sa stane, ze pride do vaznice vazen. System by mal po zadani jeho mena vypisat, ze je NOVY a priradit mu unikatne (dosial nepriradene) cislo, alebo vypisat RECIDIVISTA a cislo, ktore mu bolo priradene. Priklad vstupu:

   JACK ROZPAROVAC
   AXEL I.
   JACK ROZPAROVAC
   JAMES BOND
   AXEL I.
   BONY A KLID
   AXEL I.
   

   A na vystupe by malo byt (napr.)
   Riesenie posielajte v .pas, alebo v .c / .cpp. Citajte a vypisujte na standardny vstup / vystup.
   Poznamka: Nemusite si pamatat vsetky requesty. Po kazdom requeste mozete vypisat rovno patricnu hlasku, teda ak citate aj vypisujete na obrazovku, tak to moze vyzerat nasledovne:

   JACK ROZPAROVAC
   NOVY 8621
   AXEL I.
   NOVY 1
   JACK ROZPAROVAC
   RECIDIVISTA 8621
   JAMES BOND
   NOVY 7
   AXEL I.
   RECIDIVISTA 1
   BONY A KLID
   NOVY 20000
   AXEL I.
   RECIDIVISTA 1
   

   Vase riesenia otestujem a pridelim body od 0 do 10 (podla toho, kolko si zasluzite). Nebude to take prisne ako na zenite...
   Poznamka 2: Je to priklad zo zbierky KSP, c. 1511 O recidivistoch. Zadania sa v podstate zhoduju az na par detailov...