1 Wstawianie i wyszukiwanie kluczy w tablicach i drzewach binarnychTablice nieposortowane Tablice posortowane Drzewa poszukiwań binarnych Drzewa czerwono czarne

2 Tablice nieposortowane wstawianie1 10 7 3 18 12 9 20

3 Tablice nieposortowane wyszukiwanieSzukamy liczby 9: 1 10 7 3 18 12 9 20

4 Tablice nieposortowaneWstawianie jest natychmiastowe Znalezienie klucza może wymagać przejrzenia wszystkich elementów tablicy Potrzebujemy czegoś lepszego

5 Tablice posortowane wyszukiwanie = bisekcjaSzukamy liczby 10:

6 Tablice posortowane wstawianie = przesuwanie bloków3 7 9 10 12 18 20

7 Tablice posortowane wstawianie = przesuwanie bloków1 3 7 9 10 12 18 20

8 Tablice posortowane Szybkie wyszukiwanie kluczyWstawienie może wymagać przesunięcia wszystkich elementów Potrzebujemy czegoś lepszego

9 Drzewa poszukiwań binarnych wstawianie10 12 3 11 20 7 1 9 18

10 Drzewa poszukiwań binarnych wyszukiwanieSzukamy liczby 9 10 12 3 11 20 7 1 9 18

11 Drzewa poszukiwań binarnych bywają bardzo niezrównoważone1 3 7 9 10 11 12 18 20

12 Drzewa poszukiwań binarnychCzas wyszukiwania i wstawiania zależy długości gałęzi drzewa Jeśli kolejność wstawiania jest przypadkowa możemy otrzymać krótkie gałezie Wstawiając w kolejności rosnącej otrzymujemy jedną długą gałąź Potrzebujemy czegoś lepszego

13 Drzewa czerwono-czarne definicjaSą to drzewa poszukiwań binarnych Każdy węzeł jest czerwony lub czarny Korzeń jest czarny Czerwony węzeł ma zawsze czarnego ojca Ilość czarnych węzłów na dowolnej ścieżce korzeń-NULL jest taka sama

14 Drzewa czerwono-czarne przykłady10 20

15 Drzewa czerwono-czarne przykłady10 5 20 31 2 15 12

16 Drzewa czerwono-czarne przykłady10 20 5 15 31 7 2 17 35 28 12 1 11 13 32 39

17 Drzewa czerwono-czarne rotacje10 20 Alfa Beta Gamma

18 Drzewa czerwono-czarne rotacje20 10 Alfa Beta Gamma

19 Drzewa czerwono-czarne przekolorowania20 30 10

20 Drzewa czerwono-czarne przekolorowania20 30 10

21 Drzewa czerwono-czarne

22 Drzewa czerwono-czarne1 Robimy rotację 3 Źle 10

23 Drzewa czerwono-czarne3 10 1

24 Drzewa czerwono-czarneRobimy przekolorowanie 3 10 1 9 źle

25 Drzewa czerwono-czarne3 Korzeń musi być czarny Więc go przemalujmy 10 1 9

26 Drzewa czerwono-czarne3 Robimy przekolorowanie 10 1 Źle 12 9 18

27 Drzewa czerwono-czarne3 10 1 12 9 Robimy rotację 18 Źle 19

28 Drzewa czerwono-czarne3 10 1 Robimy przekolorowanie 9 18 19 12 Źle 20

29 Drzewa czerwono-czarne3 Robimy rotację 10 1 Źle 9 18 19 12 20

30 Drzewa czerwono-czarne10 3 18 19 1 9 12 20

31 Drzewa czerwono czarneSą to drzewa poszukiwań binarnych, które same się równoważą Nie powstają długie gałęzie Wyszukiwanie i wstawianie jest szybkie To jest to!