Aisd W12

Algorytmy i struktury danych Temat: Drzewa czerwonoczarne

Drzewa czerwono – czarne (RB)

 

 

Drzewo czerwono–czarne (r-b) jest kolejnym rozwinięciem drzewa BST; Powstało w celu przyspieszenia operacji przetwarzania przez odpowiednią organizację węzłów w drzewie; Dzięki zastosowanym metodom równoważenia pesymistyczna złożoność operacji wynosi O(log2n); Drzewo r-b powstaje przez rozszerzenie węzła drzewa BST o pole koloru {czerwony, czarny};

Algorytmy i struktury danych

2

Drzewa czerwono – czarne (r-b)

W drzewie czerwono-czarnym:  wszystkie wartości NULL traktujemy jako zewnętrzne węzły drzewa – liście;  zwyczajne węzły drzewa r-b (zawierające klucze) nazywamy węzłami wewnętrznymi drzewa;

Algorytmy i struktury danych

3

Drzewa czerwono – czarne (r-b)

Własności drzewa czerwono-czarnego: (1) Każdy węzeł ma kolor czerwony lub czarny; (2) Korzeń ma kolor czarny; (3) Każdy liść (wskaźnik o wartości NULL) ma kolor czarny; (4) Jeżeli węzeł jest czerwony, to jego następniki są czarne; (5) Dla każdego węzła każda prosta ścieżka od węzła do liścia zawiera jednakową liczbę węzłów czarnych;

Algorytmy i struktury danych

4

Drzewa czerwono – czarne

Przykład drzewa czerwono-czarnego:

Ile węzłów ma powyższe drzewo? Algorytmy i struktury danych

Odp.: 25-1= 31 5

Drzewa czerwono – czarne Czy poniższe drzewo jest drzewem czerwono-czarnym?

11 14

2 1

15

7 5

Algorytmy i struktury danych

8

TAK

1.Każdy węzeł ma kolor czerwony lub czarny; 2.Korzeń ma kolor czarny; 3.Każdy liść (wskaźnik o wartości NULL) ma kolor czarny; 4.Jeżeli węzeł jest czerwony, to jego następniki są czarne; 5.Dla każdego węzła każda prosta ścieżka od węzła do liścia zawiera jednakową liczbę węzłów czarnych;

6

Drzewa czerwono – czarne Czy poniższe drzewo jest drzewem czerwono czarnym?

11 14

2 1

15

7 5

Algorytmy i struktury danych

8

NIE

1.Każdy węzeł ma kolor czerwony lub czarny; 2.Korzeń ma kolor czarny; 3.Każdy liść (wskaźnik o wartości NULL) ma kolor czarny; 4.Jeżeli węzeł jest czerwony, to jego następniki są czarne; 5.Dla każdego węzła każda prosta ścieżka od węzła do liścia zawiera jednakową liczbę węzłów czarnych;

7

Drzewa czerwono – czarne

◆

Wysokość węzła: h(x) – największa liczba węzłów na drodze prostej z węzła x do liści;

◆

Czarna wysokość węzła: bh(x) – liczba węzłów czarnych (z uwzględnieniem liścia - NULL) na drodze od tego węzła do liścia (z wykluczeniem tego węzła);

◆

Czarna wysokość drzewa r-b – czarna wysokość korzenia danego drzewa;

Algorytmy i struktury danych

8

Drzewa czerwono – czarne

bh=2 bh=2

bh=2

bh=1 bh=1 bh=0

Algorytmy i struktury danych

9

Drzewa czerwono – czarne Lemat 1 Każde poddrzewo r-b o korzeniu w dowolnym węźle x posiada co najmniej n = 2bh(x) – 1 węzłów wewnętrznych, tzn. n ≥ 2bh(x) – 1 Lemat 2 Każdy węzeł x o wysokości h(x) ma czarną wysokość bh(x), przy czym bh(x) ≥ h(x) / 2. Lemat 3 Drzewo czerwono-czarne o n węzłach wewnętrznych ma wysokość h nie większą niż 2 log2(n+1), tzn.: h ≤ 2 log2(n+1) np.:

dla dla dla dla

Algorytmy i struktury danych

n=7 n=1023 n=4095 n=16383

h h h h

≤ ≤ ≤ ≤

6 2 log21024 = 20 2 log24096 = 24 2 log216384 = 28 10

Operacje na drzewie czerwono – czarnym  Wyszukiwanie  Ponieważ struktura drzewa nie ulega zmianie operacja wyszukiwania realizowana jest tak samo jak w zwykłym drzewie BST

Algorytmy i struktury danych

11

Operacje na drzewie czerwono – czarnym  Wstawianie ◆ Wstaw węzeł we właściwe miejsce (z zachowaniem własności drzewa BST); ◆ Pokoloruj węzeł na czerwono (Z wskazuje na nowy węzeł); ◆ Jeśli trzeba wykonaj korektę drzewa, w zależności od przypadku (jednego z trzech), który wystąpił. Możliwe przypadki: Przypadek 0 Z jest korzeniem → przekoloruj nowo wstawiony węzeł na czarno;

Algorytmy i struktury danych

12

Operacje na drzewie czerwono – czarnym  Wstawianie Przypadek 1 Zarówno poprzednik (ojciec) jak i bezpośredni sąsiad poprzednika (wuj) są czerwone;

ojciec

sąsiad ojca - wuj

Z

Algorytmy i struktury danych

13

Operacje na drzewie czerwono – czarnym  Wstawianie Przypadek 2 Poprzednik (ojciec) jest czerwony a wuj jest czarny; ponadto Z i jego ojciec są następnikami po przeciwnych stronach, tj. Z jest prawym następnikiem podczas gdy ojciec lewym lub odwrotnie;

Z Algorytmy i struktury danych

14

Operacje na drzewie czerwono – czarnym  Wstawianie Przypadek 3 Poprzednik (ojciec) jest czerwony a wuj jest czarny; ponadto Z i jego ojciec są następnikami po tej samej stronie (prawymi lub lewymi);

Z Algorytmy i struktury danych

15

Operacje na drzewie czerwono – czarnym  Wstawianie - przypadek 1

Zarówno poprzednik (ojciec) jak i bezpośredni sąsiad poprzednika (wuj) są czerwone; 1. koloruj poprzednik (ojca) i jego sąsiada (wuja) na czarno; 2. koloruj poprzednika ojca (dziadka) na czerwono; 3. ustaw Z na poprzednika ojca (dziadka);

G

ojciec

P

G

sąsiad ojca - wuj

U

P

Z U

Z

Algorytmy i struktury danych

16

Operacje na drzewie czerwono – czarnym  Wstawianie - przypadek 2

Poprzednik (ojciec) jest czerwony, a wuj jest czarny; ponadto X jest prawym następnikiem a ojciec lewym lub odwrotnie; 1) podwójna rotacja: - lewa: Z wokół P, - prawa: Z wokół G; 4) przekolorowanie G i Z;

G P S

Z

Z

U P

G S

Algorytmy i struktury danych

U 17

Operacje na drzewie czerwono – czarnym  Wstawianie - przypadek 3 Poprzednik (ojciec) jest czerwony a wuj jest czarny; ponadto X i jego ojciec są następnikami po tej samej stronie (prawymi lub lewymi); 1) 2)

rotacja P wokół G; przekolorowanie P i G;

P

G P Z

S

U

Z

G S

U

Uwaga: Ten przypadek zachodzi w drugim kroku Przypadku 2 Algorytmy i struktury danych

18

Operacje na drzewie czerwono – czarnym Uwaga: Przedstawione algorytmy rozpatrywanych operacji na drzewach r-b oparte są na założeniu, ze każdy węzeł drzewa r-b ma następującą strukturę: ✦ ✦ ✦ ✦ ✦

pole pole pole pole pole

key color left right p

Algorytmy i struktury danych

// wskaźnik na lewy następnik // wskaźnik na prawy następnik // wskaźnik na poprzednik

19

Operacje na drzewie czerwono – czarnym  Wstawianie „Bottom Up” //

z - wskaźnik na dołączany węzeł

lokalizacja miejsca wstawienia węzła (nowy węzeł będzie wstawiony po węźle y)

wstawienie węzła z

// Algorytmy i struktury danych

wywołanie funkcji korekty 20

Operacje na drzewie czerwono – czarnym  Wstawianie „Bottom Up” – algorytm funkcji korekty: poprzednik z (ojciec) jest czerwony y wskazuje na sąsiada ojca (wuja)

Przypadek (1)

Przypadek (2) Przypadek (3)

Algorytmy i struktury danych

21

Operacje na drzewie czerwono – czarnym  Przykład – wstawienie węzła z wartością 4

11

4

14

2 1

7 5 Z

4

Czy otrzymane drzewo jest drzewem r-b? Algorytmy i struktury danych

15 8

✦ Każdy węzeł ma kolor czerwony lub czarny; ✦ Korzeń ma kolor czarny; ✦ Każdy liść (wskaźnik o wartości NULL) ma kolor czarny; ✦ Jeżeli węzeł jest czerwony, to jego następniki są czarne; ✦ Dla każdego węzła każda prosta ścieżka od węzła do liścia zawiera jednakową liczbę węzłów czarnych; 22

Operacje na drzewie czerwono – czarnym  Przykład (cd.)

Identyfikacja przypadku (po wstawieniu węzła 4):

11

- Zarówno poprzednik (ojciec) jak i bezpośredni sąsiad poprzednika (wuj) są czerwone;

14

2 1

15

7 5

8

- Zachodzi Przypadek 1; Korekta: ✦

koloruj poprzednik (ojca) i jego sąsiada (wuja) na czarno;

✦

koloruj poprzednika ojca (dziadka) na czerwono;

✦

ustaw Z na poprzednika ojca (dziadka);

Z 4

Algorytmy i struktury danych

23

Operacje na drzewie czerwono – czarnym  Przykład (cd.) - Ponownie węzeł Z i jego przodek są koloru czerwonego; - Wuj Y węzła Z jest czarny a Z jest prawym synem, podczas gdy ojciec lewym; - Zachodzi Przypadek 2;

Korekta:  wykonaj rotację Z w lewo wokół ojca (2);  wykonaj rotację Z w prawo wokół dziadka (11);  koloruj dziadka (11) na czerwono;  koloruj Z na czarno;

11 Y 14

2 1

15

Z 7 5

8

4

Jak wygląda drzewo po wykonaniu tych operacji? Algorytmy i struktury danych

24

Operacje na drzewie czerwono – czarnym  Przykład (cd.) - Po wykonaniu lewej rotacji Z względem 2;

11

11 Y 14

2 1

15

Z7 5 4

8

Y 14

Z 7

15

2 1

8 5

4 Algorytmy i struktury danych

25

Operacje na drzewie czerwono – czarnym  Przykład (cd.)

Z

- Po wykonaniu prawej rotacji Z względem 11;

2 1

1 Y 14

8

11

2

11 Z7

7

15

5 4

8

Y 14 15

5 4

Algorytmy i struktury danych

26

Operacje na drzewie czerwono – czarnym Z

 Przykład (cd.) - Po przekolorowaniu Z i 11;

Algorytmy i struktury danych

11

2 1

- Drzewo teraz jest poprawnym drzewem r-b; 1.Każdy węzeł ma kolor czerwony lub czarny; 2.Korzeń ma kolor czarny; 3.Każdy liść (wskaźnik o wartości NULL) ma kolor czarny; 4.Jeżeli węzeł jest czerwony, to jego następniki są czarne; 5.Dla każdego węzła każda prosta ścieżka od węzła do liścia zawiera jednakową liczbę węzłów czarnych;

7 Y 14

5 8

15

4 Z

7 11

2 1

5

8

Y 14

4

15

Czy rzeczywiście otrzymaliśmy drzewo czerwono-czarne? 27

Operacje na drzewie czerwono– czarnym  Usuwanie ◆

Jakie zmiany wywołuje usunięcie węzła z drzewa?

◆

Czerwonego:

◆

✦

Czarne wysokości węzłów nie zmieniają się;

✦

Ponadto usuwany węzeł nie mógł być korzeniem, bo byłby koloru czarnego;

Czarnego: ✦

Ścieżki na których leżał usunięty węzeł mają o jeden czarny węzeł mniej: złamanie założeń 4 i 5;

✦

Jeżeli usuwany węzeł był korzeniem, może zastąpić go węzeł koloru czerwonego: złamanie zasady 2;

Algorytmy i struktury danych

28

Operacje na drzewie czerwono – czarnym 

Usuwanie „Bottom-Up” 1. Usuwanie przebiega analogicznie do operacji w drzewie BST; 2. Korekta przy usuwaniu węzła czarnego: ✦ Założenia: • Y – węzeł usuwany (fizycznie) w konsekwencji żądania usunięcia wskazanej wartości; • X – węzeł, który zastępuje Y; • P – przodek węzła Y; • S – sąsiad (brat) węzła X; • X wskazuje węzeł z nadmiarowym kolorem czarnym; ✦ Przypadki: (1) S jest koloru czerwonego; (2) S jest koloru czarnego oraz ma dwóch czarnych potomków; (3) S jest koloru czarnego, a jego prawy potomek koloru czerwonego; (4) S jest koloru czarnego, jego prawy potomek koloru czarnego, a lewy koloru czerwonego; Uwagi 4. Usunięcie węzła czerwonego nie zmienia własności drzewa r-b 5. Funkcja korekty jest wywoływana dla węzła z nadmiarowym kolorem czarnym (jest to zawsze jeden z następników fizycznie usuwanego węzła)

Algorytmy i struktury danych

29

Operacje na drzewie czerwono – czarnym Przypadek 1 S jest koloru czerwonego;

P X

Algorytmy i struktury danych

S

30

Operacje na drzewie czerwono – czarnym Przypadek 2 S jest koloru czarnego oraz ma dwóch czarnych potomków;

Czerwony lub czarny

P X

Algorytmy i struktury danych

S

31

Operacje na drzewie czerwono – czarnym Przypadek 3 S jest koloru czarnego, a jego prawy potomek koloru czerwonego;

P S X

Algorytmy i struktury danych

32

Operacje na drzewie czerwono – czarnym Przypadek 4 S jest koloru czarnego, jego prawy potomek koloru czarnego, a lewy koloru czerwonego;

P S X

Algorytmy i struktury danych

33

Operacje na drzewie czerwono – czarnym  Przypadek 1 (S jest koloru czerwonego) ✦Rotacja

S wokół P; ✦Przekolorowanie S i P;

P

S

rotacja

P

S X

S P X

Algorytmy i struktury danych

X przekolorowanie Uwaga – to nie jest stan końcowy: wystąpi jeden z przypadków 2 – 4; 34

Operacje na drzewie czerwono – czarnym  Przypadek 2 S jest koloru czarnego oraz ma dwóch czarnych potomków; ✦ ✦ ✦

Przekolorowanie S na czerwono; Jeżeli P jest koloru czerwonego – bez zmian; Jeżeli P jest czarne – kolor musi być propagowany w drzewie w kierunku korzenia;

Czerwony lub czarny

przekolorowanie

P S

X P S

X Jeżeli czarny – propagacja koloru w górę;

Algorytmy i struktury danych

35

Operacje na drzewie czerwono – czarnym  Przypadek 3 S jest koloru czarnego a prawy potomek koloru czerwonego; ✦ Rotacja S wokół P; ✦ Zamiana kolorów S i P; ✦ Przekolorowanie prawego potomka S na czarno;

P

rotacja

S X Uwaga Rozpatrywany przypadek jest przypadkiem końcowym!

Algorytmy i struktury danych

S

P

S P

przekolorowanie 36

Operacje na drzewie czerwono – czarnym  Przypadek 4

P

S jest koloru czarnego, prawy potomek koloru czarnego a lewy koloru czerwonego; ✦ Rotacja lewego potomka S wokół S; ✦ Zamiana kolorów S i lewego potomka S;

P

S

P

X rotacja

Algorytmy i struktury danych

X

X

S

S

przekolorowanie

37

Operacje na drzewie czerwono – czarnym  Przypomnienie Usunięcie węzła z drzewa BST prowadzi do jednego z trzech przypadków: Przypadek 1

7

7 11

2 1

Algorytmy i struktury danych

Y

5

8

11

2 1

8

38

Operacje na drzewie czerwono – czarnym Przypadek 2

7 11

2 1

5

Algorytmy i struktury danych

8

7

Y

X

2 1

5

8

39

Operacje na drzewie czerwono – czarnym Przypadek 3

7

8 11

2 1

5

8

Y

11

2 1

5

Uwaga: Węzłem fizycznie usuniętym jest węzeł z wartością 8 Algorytmy i struktury danych

40

Operacje na drzewie czerwono – czarnym  Usuwanie: wyznaczenie węzła y, który zostanie fizycznie usunięty z drzewa

usunięcie z drzewa węzła y

przepisanie y do z wywołanie funkcji korekty

Algorytmy i struktury danych

41

Operacje na drzewie czerwono – czarnym  Usuwanie „Bottom-Up” – algorytm korekty: Funkcja korekty jest wywoływana dla lewego lub prawego syna suwanego węzła y

Przypadek 1

Przypadek 2 Przypadek 3 Przypadek 4

Algorytmy i struktury danych

42

Operacje na drzewie czerwono – czarnym Przykład 1 – usunięcie węzła z Postępowanie: wartością 11

7

Usuwamy węzeł zgodnie z procedurą dla drzewa BST

11

2 1

5 4

8

14 Y 15 X

7 14

2 1

5

8

P

15 X

S

4 Algorytmy i struktury danych

43

Operacje na drzewie czerwono – czarnym Przykład – usunięcie węzła z wartością 11 (cd.)  Z którym przypadkiem mamy do czynienia? Przypadek 2

7 14

2 1

5

8

S

(S jest koloru czarnego oraz ma dwóch czarnych potomków) ✦ Przekolorowanie S na czerwono; ✦ Jeżeli P jest koloru czerwonego – bez zmian; P ✦ Jeżeli P jest czarne – kolor musi być propagowany w drzewie w kierunku korzenia;

7

15 X

14 X

2

4 1

5

8

15

4 Algorytmy i struktury danych

44

Operacje na drzewie czerwono – czarnym Przykład 2 – usunięcie węzła z Postępowanie: wartością 2

7

11

2 1

5 Y

Usuwamy węzeł zgodnie z procedurą dla drzewa BST

4

8

14 15

7 11

4

Co dalej?

1

5

8

Ponieważ usunięty węzeł był czerwony własności drzewa czerwonoczarnego nie uległy zmianie – korekta nie jest potrzebna Algorytmy i struktury danych

14 15 45

Operacje na drzewie czerwono – czarnym Przykład 3 – usunięcie węzła z Postępowanie: wartością 7

7

Usuwamy węzeł zgodnie z procedurą dla drzewa BST

11

2 1

5

8

14

Y

8

15

4

11

2 1

5 4

Algorytmy i struktury danych

14 15 46

Algorytmy i struktury danych

47