Algorytmy i struktury danych lab.

lista 9

1. (1pkt) Opracuj metod

ę drukuj c

ą

ą drzewo czerwono czarne wierszami. Podpowied ź :

rozwa

ż przydatno

ść wykorzystania kolejki.

2. (3pkt) Przeprowad

ź badania empiryczne w celu obliczenia warto ci ś r

ś edniej i od-

chylenia standardowego liczby porówna ń u y

ż wanych dla wyszukiwania trafionego i dla wyszukiwania chybionego w drzewie czerwono-czarnym, zbudowanym przez wstawienie n losowych kluczy do pocz t ą kowo pustego drzewa, dla n = 103, 104, 105

i 106.

3. (2 pkt) Napisz program, który oblicza procent czarnych w z ę ó

ł w w danym czerwono-

czarnym drzewie poszukiwa

ć binarnych. Przetestuj swój program wstawiaj c ą n

losowych kluczy do pocz t

ą kowo pustego drzewa, dla n = 103, 104, 105 i 106.

4. (4+1pkt) Przygotuj implementacj ę jednego z drzew pozycyjnych TRIE, PATRICIA, TST. Dodatkowy punkt b d

ę zie nale a

ż łsi

ę tym, którzy przedstawi

ą praktyczne

zastosowanie zaimplementowanego drzewa.