Samoorganizujące się drzewa BST

MP001 - drzewa poszukiwań binarnych - BST
MP002 - drzewa AVL


Podstawową zaletą drzew BST jest złożoność O(log n) operacji wyszukiwania elementu, ale tylko wtedy, gdy drzewo jest zrównoważone. Aby zagwarantować zrównoważenie, wymyślono struktury danych z różnymi ograniczeniami (ang. constrained data structures) - np. drzewa AVL. Jednakże operacje wstawiania i usuwania elementu w drzewie AVL są dosyć skomplikowane. Dodatkowo w węzłach musimy przechowywać informację o ich zrównoważeniu. Dużo prostszą strukturą danych są samoorganizujące się drzewa BST (ang self-adjusting binary search trees), zwane czasami drzewami Splay (ang. splay trees). Wynalazcami tej struktury danych są Daniel Dominic Sleator oraz Robert Endre Tarjan. Nazwa drzew pochodzi od operacji splay(T,x) (czytaj splej), która wyszukuje w drzewie T węzeł x i umieszcza go w korzeniu drzewa. Jeśli w drzewie T nie ma węzła x, to w korzeniu jest umieszczany taki węzeł x' drzewa T, iż pomiędzy x a x' nie istnieje w tym drzewie żaden inny węzeł.

Operacja splay

Przemieszczanie węzła x w hierarchii drzewa T dokonywane jest przy pomocy rotacji, które poznaliśmy przy okazji drzew AVL. W przypadku drzew Splay operacje te upraszczają się, ponieważ nie musimy się martwić o współczynniki zrównoważenia bf, których tutaj po prostu nie ma. Istnieją trzy zasady wykonywania rotacji w drzewie Splay:

Zasada nr 1 (zig):

Jeśli rodzicem y węzła x jest korzeń drzewa T, to wykonujemy rotację pojedynczą, w której uczestniczą rodzić y oraz węzeł x. Rotacja taka kończy operację splay. Poniższy rysunek przedstawia sposób wykonania rotacji.

Zasada nr 2 (zig-zig):

Jeśli rodzic y węzła x nie jest korzeniem, a zarówno y jak i x są jednocześnie prawymi lub jednocześnie lewymi dziećmi, to wykonujemy dwie rotacje: najpierw rotacja z dziadkiem z i rodzicem y, a następnie rotacja z rodzicem y i węzłem x. Poniżej przedstawiamy sposób wykonania tych rotacji (przypadek lustrzany działa identycznie, zatem nie został uwzględniony na rysunku):

Zasada nr 3 (zig-zag):

Jeśli rodzic y nie jest korzeniem, a węzły x i y są naprzemiennie lewym i prawym dzieckiem, to najpierw wykonujemy rotację węzła y z węzłem x, a następnie rotację nowego rodzica x (jest to teraz węzeł z)  z węzłem y. Poniżej przedstawiamy sposób wykonania tych rotacji:

 

Rotacja zig oraz para rotacji zig-zig lub zig-zag nosi nazwę kroku rozchylającego (ang. splaying step). Kroki rozchylające wykonujemy dotąd, aż węzeł x znajdzie się w korzeniu drzewa.

Operacja splay(T,x) składa się zatem z dwóch faz. W pierwszej wykonujemy operację wyszukania węzła x w strukturze drzewa T. Jeśli węzeł x nie zostanie znaleziony, to za x przyjmujemy ostatni niepusty węzeł, przez który przeszła operacja wyszukiwania. W drugiej fazie wykonujemy kroki rozchylające dotąd, aż węzeł x zostanie przesunięty do korzenia drzewa T.

Algorytm operacji splay

Wejście:

root  - korzeń drzewa BST
k  - klucz węzła, który ma znaleźć się w korzeniu drzewa BST

Wyjście:

Jeśli węzeł o kluczu x znajduje się w drzewie BST, to zostaje umieszczony w korzeniu. Jeśli węzeł o kluczu x nie występuje w drzewie BST, to w korzeniu zostaje umieszczony jego bezpośredni poprzednik lub następnik.

Dane pomocnicze:

x, y  - węzły drzewa BST
key(w)  - klucz węzła w
left(w)  - lewy potomek węzła w
right(w)  - prawy potomek węzła w
p(w)  - rodzic węzła w

Lista kroków

K01: x ← root ; rozpoczynamy fazę poszukiwania węzła o kluczu k
K02: Jeśli x = NIL, zakończ ; drzewo jest puste
K03:     Jeśli key(x) = k, idź do K08 ; znaleźliśmy węzeł o kluczu k
K04:     y ← x ; zapamiętujemy bieżący węzeł
K05:     Jeśli k < key(x), to x ← left(x)
    inaczej                  x ← right(x)
; przechodzimy do potomka węzła x
K06:     Jeśli x ≠ NIL, idź do kroku K03 ; kontynuujemy wyszukiwanie
K07: x ← y ; w drzewie nie ma węzła o kluczu k, za x przyjmujemy poprzednik lub następnik
K08:     Jeśli p(x) = NIL, zakończ ; węzeł x znalazł się w korzeniu drzewa
K09:     Jeśli p(p(x)) = NIL, wykonaj rotację ZIG i zakończ ; rotacja ZIG umieszcza x w korzeniu drzewa
K10:     Jeśli left(p(p(x))) = p(x) i left(p(x)) = x
    lub right(p(p(x))) = p(x) i right(p(x)) = x,
    to wykonaj rotację ZIG-ZIG i idź do K08
; badamy odpowiednie przypadki
K11:     Wykonaj rotację ZIG-ZAG  
K12:    Idź do K08  

Strukturę węzłów drzewa BST deklarujemy następująco:

struct BSTNode
{
  BSTNode * p, * left, * right;
  int key;
}

Funkcja splay w C++ wygląda następująco:

 

Zastosowanie operacji splay

Zdefiniujemy teraz podstawowe operacje na drzewie BST wykorzystujące opisaną powyżej operację splay(T,x).

search(T, k)

Wyszukanie elementu w drzewie BST polega na wykonaniu operacji splay(T, x), a następnie sprawdzeniu, czy korzeń drzewa zawiera poszukiwany element x. Jeśli tak, operacja search zwraca jego adres, a jeśli nie, zwraca adres pusty.

Wejście:

root  - korzeń drzewa BST
k  - klucz węzła, którego poszukujemy w drzewie BST

Wyjście:

Adres węzła o kluczu k lub NIL, gdy drzewo BST nie zawiera takiego węzła.

Dane pomocnicze:

key(w)  - klucz węzła w
left(w)  - lewy potomek węzła w
right(w)  - prawy potomek węzła w
p(w)  - rodzic węzła w

Lista kroków

K01: Jeśli root = NIL, zakończ z NIL ; drzewo jest puste
K02: splay(root, k) ; rozdzielamy drzewo BST i umieszczamy w korzeniu węzeł o najbliższym kluczu k'
K03: Jeśli key(root) = k, zakończ z root
inaczej                  zakończ z NIL
; sprawdzamy, czy drzewo BST zawiera poszukiwany węzeł

Funkcja search w C++ :

 

insert(T,x)

Operacja wstawiania nowego elementu do drzewa BST wygląda następująco:

Jeśli drzewo BST jest puste, to węzeł x umieszczamy w korzeniu i kończymy operację wstawiania.

Wykonujemy operację splay(T, key(x)), która w korzeniu drzewa BST umieści element x' o kluczu będącym bezpośrednim poprzednikiem lub następnikiem klucza wstawianego elementu x. Jeśli klucz x jest taki sam jak klucz x', to element x usuwamy z pamięci - drzewo posiada już węzeł o takim kluczu.

W przeciwnym razie węzeł x wstawiamy odpowiednio jako lewe dziecko x' (gdy x' jest następnikiem x, czyli key(x) < key(x')) lub jako prawe dziecko x' (gdy x' jest poprzednikiem x, czyli key(x') < key(x)).

Wejście:

root  - korzeń drzewa BST
x  - węzeł do wstawienia w drzewie BST

Wyjście:

true - węzeł x został wstawiony do drzewa BST
false - węzeł x nie został wstawiony, węzeł usunięto z pamięci

Dane pomocnicze:

key(w)  - klucz węzła w
left(w)  - lewy potomek węzła w
right(w)  - prawy potomek węzła w
p(w)  - rodzic węzła w

Lista kroków

K01: left(x) ← NIL ; inicjujemy pola wstawianego węzła
K02: right(x) ← NIL  
K03: p(x) ← NIL  
K04: Jeśli root = NIL, root ← x i zakończ z true ; drzewo było puste, zatem x staje się korzeniem
K05: splay(root, key(x)) ; rozdzielamy drzewo
K06: Jeśli key(root) = key(x), usuń x i zakończ z false ; drzewo posiada już węzeł o takim kluczu
K07: Jeśli key(x) > key(root), idź do K12  
K08: left(x) ← left(root) ; wstawiamy x jako lewe dziecko korzenia
K09: Jeśli left(x) ≠ NIL, p(left(x)) ← x  
K10: left(root) ← x ; rodzicem x staje się korzeń drzewa
K11 Idź do K15  
K12: right(x) ← right(root) ; wstawiamy x jako prawe dziecko korzenia
K13: Jeśli right(x) ≠ NIL, p(right(x)) ← x  
K14: right(root) ← x  
K15: p(x) ← root  
K16 Zakończ z true  

Funkcja insert w C++ :

 

delete(T,k)

Operacja usunięcia węzła o kluczu k jest kilkuetapowa.

Jeśli korzeń drzewa jest pusty, kończymy zwracając NULL.

Wykonujemy operację splay(T, k).

Jeśli korzeń drzewa zawiera element o kluczu różnym od k, kończymy zwracając NULL. W drzewie BST nie ma elementu o poszukiwanym kluczu.

Odłączamy korzeń od jego dzieci zapamiętując go np. w zmiennej x. Jeśli dzieci są puste, to drzewo zawierało tylko usunięty węzeł. W korzeniu umieszczamy NULL i zwracamy zapamiętany adres w x.

W przeciwnym razie nad niepustym dzieckiem wykonujemy ponownie operację splay. Do korzenia dołączamy pozostałego potomka i zwracamy x.

Wejście:

root  - korzeń drzewa BST
k  - klucz węzła do usunięcia z drzewa BST

Wyjście:

adres usuniętego węzła lub NIL, jeśli węzeł o kluczu k nie występował w drzewie BST

Dane pomocnicze:

x, y  - węzeł drzewa
key(w)  - klucz węzła w
left(w)  - lewy potomek węzła w
right(w)  - prawy potomek węzła w
p(w)  - rodzic węzła w

Lista kroków

K01: Jeśli root = NIL, zakończ z NIL ; drzewo BST jest puste
K02: splay(root, k)  
K03: Jeśli key(root) ≠ k, zakończ z NIL ; w drzewie BST nie ma elementu o kluczu k
K04: x ← root ; zapamiętujemy znaleziony element
K05: root ← left(x);    y ← right(x) ; zastępujemy x jego lewym dzieckiem
K06: Jeśli root ≠ NIL, p(left(lroot)) ← NIL i idź do K09  
K07: root ← right(x);   y ← NIL ; zastępujemy x jego prawym dzieckiem
K08: Jeśli root ≠ NIL, p(right(root)) ← NIL  
K09: splay(root, k) ; druga operacja splay
K10: Jeśli root = NIL lub y = NIL, idź do K13 ; drzewo zawierało tylko jeden węzeł lub poddrzewo y było puste
K11 p(y) ← root ; poddrzewo y dołączamy do korzenia
K12: Jeśli key(y) < key(root), to left(root) ← y
inaczej                             right(root) ← y
 
K13: Zakończ z x  

Funkcja delete w C++ :

 

Zalety i wady samoorganizujących się drzew BST

Zbalansowane drzewa BST zostały zaprojektowane w celu zredukowania pesymistycznego czasu wykonywania operacji. Jednakże w typowych aplikacjach wykonuje się na nich nie pojedyncze operacje lecz całe serie, zatem istotne znaczenie ma czas wykonania takiej serii operacji (np. sprawdzenie poprawności ortograficznej tekstu wymaga wielu poszukiwań w drzewie BST słownika - przynajmniej tyle razy, ile wyrazów zawiera tekst). W takiej sytuacji zamiast optymalizować pojedyncze operacje na drzewie BST, lepszym celem będzie zoptymalizowanie czasu zamortyzowanego ciągu operacji, gdzie przez czas zamortyzowany (ang. amortized time) autorzy tej struktury rozumieją średni czas operacji w przypadku pesymistycznym dla ciągu operacji na drzewie BST.

Właśnie opisane powyżej samoorganizujące się drzewa BST pozwalają zoptymalizować czas zamortyzowany. Pomiędzy operacjami drzewo może znajdować się w dowolnym stanie, jednakże przy każdej operacji zostaje ono przebudowane na korzyść przyszłych operacji. Zauważ, iż dzięki operacji splay często wykorzystywane elementy wędrują w pobliże korzenia drzewa BST. Zatem kolejny dostęp do nich będzie już dużo szybszy.

Samoorganizujące się struktury danych posiadają kilka zalet w stosunku do struktur zbalansowanych o różnych ograniczeniach:

Samoorganizujące się drzewa BST posiadają jednakże dwie potencjalne wady:

  1. Wymagają więcej lokalnych regulacji, szczególnie podczas dostępu do danych. Struktury z ograniczeniami wymagają regulacji tylko przy przebudowie drzewa, a nie przy dostępie do danych.
  2. Pojedyncze operacje w ciągu mogą być kosztowne, co może się okazać wadą w rzeczywistych aplikacjach.

Test

Program testujący strukturę samoorganizujących się drzew BST.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.