Drzewa czerwono-czarne



Pobieranie 125,53 Kb.
Data19.12.2017
Rozmiar125,53 Kb.

Drzewa czerwono-czarne

W drzewie r-b:

- Wszystkie wskazania NULL traktujemy jako wskazania na zewnętrzne węzły drzewa – liście;

- Zwyczajne węzły drzewa r-b (zawierające klucze) nazywamy wewnętrznymi węzłami drzewa;

- Przyjmuje się następujące założenia:

(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;

- 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;

- 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

- Każdy węzeł x o wysokości h(x) ma czarną wysokość bh(x) ≥ h(x) / 2.

- 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)

Wstawianie elementu:


    1. Wstaw węzeł we właściwe miejsce (z zachowaniem własności drzewa BST);

    2. Pokoloruj węzeł na czerwono (X wskazuje na nowy węzeł);

Możliwe przypadki:

0: X jest korzeniem → przekoloruj na czarno;

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

2: Poprzednik (ojciec) jest czerwony a wuj jest czarny;


ponadto X jest prawym następnikiem a ojciec lewym lub odwrotnie;

3: Poprzednik (ojciec) jest czerwony a wuj jest czarny;


ponadto X i jego ojciec są następnikami po tej samej stronie (prawymi lub lewymi);

Usuwanie elementu:

    1. Usuwanie przebiega analogicznie do operacji w drzewie BST;

    2. Korekta przy usuwaniu węzła czarnego:

Założenia:

- U – węzeł usuwany (fizycznie) w konsekwencji żądania usunięcia wskazanej wartości;

- V – węzeł, który zastępuje U;

- P – przodek węzła V;

- S – sąsiad (brat) węzła V;

- 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


    1. Usunięcie węzła czerwonego nie zmienia własności drzewa r-b

    2. Funkcja korekty jest wywoływana dla węzła z nadmiarowym kolorem czarnym
      (jest to zawsze jeden z synów fizycznie usuwanego węzła)


B-drzewa

- B-drzewa są naturalnym uogólnieniem drzew BST;

- Jeżeli węzeł wewnętrzny x w B-drzewie zawiera n(x) kluczy, to ma on n(x)+1 następników;

- Klucze w węźle x są punktami dzielącymi przedział kluczy odpowiadający węzłowi x na n(x)+1 podprzedziałów odpowiadających następnikom x;

- Podczas wyszukiwania klucza w B-drzewie decyzja o kierunku dalszego wyszukiwania, podejmowana w każdym węźle x, zależy od wyników porównań wyszukiwanego klucza z n(x) wartościami pamiętanymi w tym węźle;

- Liście mają inna strukturę niż węzły wewnętrzne i znajdują się na tym samym poziomie (tej samej głębokości);

Definicja B-drzewa:

B-drzewo T jest drzewem ukorzenionym (z korzeniem root[T]) o następujących własnościach:

1. Każdy węzeł x ma następujące pola:

- n[x] – liczba kluczy aktualnie zapisanych w węźle x;

- n[x] kluczy pamiętanych w porządku niemalejącym

key1[x] £ key2 [x] £ ... £ keyn[x] [x]

- leaf[x] – pole logiczne, którego wartością jest TRUE, jeśli x jest liściem lub FALSE, jeśli x jest węzłem wewnętrznym;

2. Każdy węzeł wewnętrzny x zawiera także n[x] + 1 wskaźników do swoich następników c1[x], c2[x], ..., cn[x]+1[x],



3. Klucze key1[x], key2[x], ..., keyn[x][x] rozdzielają przedziały kluczy pamiętane w poddrzewach: jeśli ki jest dowolnym kluczem z poddrzewa o korzeniu ci [x], to:

k1 £ key1[x] £ k2 £ key2 [x] £ ... £ keyn[x] [x] £ kn[x]+1

4. Wszystkie liście leżą na tej samej głębokości równej wysokości drzewa;
5. Istnieją dolne i górne ograniczenia na liczbę kluczy w danym węźle. Ograniczenia te są określone za pomocą ustalonej liczby całkowitej t ³ 2 nazywanej minimalnym stopniem
B-drzewa:

- każdy węzeł różny od korzenia musi mieć co najmniej t-1 kluczy; każdy węzeł wewnętrzny różny od korzenia musi mieć co najmniej t następników; jeśli drzewo jest niepuste korzeń musi mieć co najmniej jeden klucz.

- każdy węzeł może zawierać co najwyżej 2t -1 kluczy; każdy węzeł wewnętrzny może mieć co najwyżej 2t następników; węzeł jest pełny, jeśli zawiera dokładnie
2t -1 kluczy.

Właściwości:

- Najprostsze B-drzewo ma minimalny stopień t=2;

- Każdy węzeł wewnętrzny ma wtedy 2,3 lub 4 następniki



- Takie drzewo jest nazywane 2-3-4 drzewem;

- W praktyce używa się zazwyczaj dużo większych wartości t.

Wysokość B-drzewa:



Jeśli n ³ 1, to dla każdego B-drzewa o n kluczach, wysokości h oraz minimalnym stopniu t ³ 2 zachodzi:

- Liczba kluczy n spełnia nierówność:




- Zatem:



Wstawianie klucza do B-drzewa:

- Wstawianie klucza k do B-drzewa jest znacznie bardziej skomplikowane aniżeli wstawianie klucza do drzewa BST;

- Tak jak w drzewie BST najpierw szukamy pozycji w liściu do wstawienia nowego klucza;

- W B-drzewie nie możemy jednak po prostu utworzyć nowego liścia i wstawić tam klucz (dlaczego?);

- Zamiast tego wstawiamy klucz do do istniejącego liścia, jeśli nie jest on pełny;

- Jeśli taki liść jest pełny wykonujemy najpierw operację polegającą na rozbiciu pełnego węzła (mającego 2t-1 kluczy) na dwa węzły po t-1 kluczy;

- Rozbicia dokonujemy względem środkowego klucza keyi[y], który jest przesuwany do poprzednika węzła y, wyznaczając punkt podziału między dwoma nowymi poddrzewami;

- Jeśli poprzednik węzła y również jest pełny, także trzeba go rozbić itd. w górę drzewa;

- Podczas schodzenia w dół drzewa w celu znalezienia miejsca wstawienia nowego klucza rozbijamy wszystkie spotkane pełne węzły (dzięki temu wstawianie klucza k do B-drzewa o wysokości h jest wykonywane w jednym przebiegu w dół drzewa, wymagającym O(h) dostępów do dysku;

Idea algorytmu usuwania klucza z B-drzewa (B-Tree-Delete)


  1. Jeśli klucz k jest w węźle x i x jest liściem, to usuń klucz k z węzła x;

  2. Jeśli klucz k jest w węźle x i x jest węzłem wewnętrznym, to wykonaj co następuje:

    1. Niech y będzie następnikiem węzła x, który zawiera klucz k. Jeśli y ma co najmniej t kluczy, to w poddrzewie o korzeniu y wyznacz poprzednik k’ klucza k. Rekurencyjnie usuń k’ i w węźle x zastąp k przez k’.

    2. Symetrycznie, jeśli następnik z, który występuje po k w węźle x, ma co najmniej t kluczy, to wyznacz następnik k’ i zastąp k przez k’ w węźle x.

    3. Jeśli obydwa następniki y oraz z węzła x mają tylko po t-1 kluczy, to przenieś k i resztę danych z węzła z do y. Zwolnij pamięć przydzieloną dla z i usuń rekurencyjnie k z y.

  3. Jeśli klucz k nie występuje w wewnętrznym węźle x, to wyznacz korzeń ci[x] poddrzewa, w którym musi znajdować się klucz k (jeśli tylko jest w drzewie). Jeśli ci[x] ma tylko t-1 kluczy, to wykonaj krok 3a lub 3b w celu zagwarantowania, że zejście rekurencyjne następuje do węzła zawierającego co najmniej t kluczy. Następnie usuń rekurencyjnie klucz k z właściwego poddrzewa.

    1. Jeśli w węźle ci[x] jest tylko t-1 kluczy, ale jeden z jego sąsiadów (braci) ma t kluczy, to umieść w węźle ci[x] dodatkowy klucz, przesuwając odpowiedni klucz z x, a w jego miejsce przenieść klucz z lewego lub prawego brata – z tego, który zawiera t kluczy. Na koniec przesuń jeszcze z wybranego brata do ci[x] wskaźnik do odpowiedniego następnika.

    2. Jeśli węzeł ci[x] i obaj jego sąsiedni bracia maja po t-1 kluczy, to połącz węzeł ci[x] z jednym z sąsiednich braci, przesuwając odpowiedni klucz z x do nowo powstałego węzła. Przesunięty klucz jest kluczem środkowym w nowym węźle.

Przekształcenie drzewa w winorośl:

UtwórzWinorośl (root, n ) {

tmp=root;

while ( tmp != 0 )

if ( tmp ma lewy następnik) {

obróć następnik w prawo wokół tmp;

ustaw tmp na następnik, który stał się poprzednikiem;

}

else



ustaw tmp na jego prawy następnik;

}

Drzewa samonaprawiające się



Idea:

Przy sięganiu do elementu następuje korekta struktury drzewa poprzez:



    1. pojedynczą rotację (wokół poprzednika)

    2. przesunięcie elementu do korzenia

Ukosowanie

- Jest to modyfikacja strategii naprawiania drzewa poprzez przenoszenie do korzenia.

- Korekta struktury drzewa następuje poprzez stosowanie pojedynczych rotacji parami, w kolejności zależnej od powiązania dziecka, rodzica i rodzica rodzica.

- Wyróżnia się trzy przypadki (dostęp do węzła R, którego rodzicem jest Q, którego z kolei rodzicem jest P:



    1. Rodzic Q węzła R jest korzeniem.

    2. Układ jednorodny: węzeł R jest lewym dzieckiem Q, zaś Q jest lewym dzieckiem P (lub kiedy w obu relacjach chodzi o prawe dziecko).

    3. Układ niejednorodny: węzeł R jest lewym dzieckiem Q, zaś Q jest prawym dzieckiem P (lub kiedy R jest prawym dzieckiem, natomiast Q lewym).




©operacji.org 2017
wyślij wiadomość

    Strona główna