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 redniej i od

ź

ś ś

-

chylenia standardowego liczby porówna u ywanych dla wyszukiwania trafionego i

ń ż

dla wyszukiwania chybionego w drzewie czerwono-czarnym, zbudowanym przez
wstawienie n losowych kluczy do pocz tkowo 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 tkowo pustego drzewa, dla n = 103, 104, 105 i 106.

ą

4. (4+1pkt) Przygotuj implementacj jednego z drzew pozycyjnych

ę

TRIE, PATRICIA,

TST. Dodatkowy punkt b dzie nale a si tym, którzy przedstawi praktyczne

ę

ż ł ę

ą

zastosowanie zaimplementowanego drzewa.