8. Drzewa binarne

8.1. Drzewa, drzewa binarne i drzewa poszukiwań binarnych

Listy dają zwykle programiście większą elastyczność niż tablice, ale są strukturami liniowymi i trudno wykorzystać je do tworzenia hierarchicznej reprezentacji obiektów. Wprawdzie stosy i kolejki odzwierciedlają pewną hierarchię, są one jednak ograniczone do jednego tylko wymiaru. Aby przezwyciężyć to ograniczenie, utworzymy nowy typ danych, zwany drzewem, składający się z wierzchołków (węzłów) i krawędzi. Inaczej niż zwykłe drzewa, te rysuje się odwrotnie, z korzeniem na górze, a liśćmi na dole. Korzeń jest węzłem, który nie ma ojca (poprzednika), może jedynie mieć synów (następniki). Z kolei liście to węzły, które nie mają synów. Drzewo można zdefiniować rekurencyjnie w następujący sposób:
1. Pusta struktura jest drzewem pustym.
2. Jeśli t_1, ..., t_k są drzewami rozłącznymi, to struktura, w której synami korzenia są korzenie t_1, ..., t_k jest także drzewem.
3. Drzewami są jedynie struktury definiowane za pomocą reguł 1 i 2.
Na rysunku 8.1 widać przykłady drzew. Każdy wierzchołek musi być osiągalny z korzenia poprzez wyznaczony jednoznacznie ciąg krawędzi, zwany ścieżką. Liczba krawędzi na ścieżce jest nazywana jej długością. Poziom węzła to długość ścieżki od korzenia do węzła plus jeden, co stanowi liczbę węzłów na ścieżce. Wysokość niepustego drzewa to największy z poziomów węzłów w drzewie. Drzewo puste jest jak najbardziej poprawnym drzewem o wysokości 0 (z definicji), a pojedynczy węzeł jest drzewem o wysokości 1. Jest to jedyny przypadek, kiedy węzeł jest jednocześnie korzeniem i liściem. Głębokość (numer poziomu) węzła musi być liczbą zawartą między jedynką (poziomem korzenia) a wysokością drzewa (która w skrajnym przypadku jest poziomem jedynego liścia w zdegenerowanym drzewie przypominającym kształtem listę).
#169
Rys. 8.1. Przykłady drzew

Na rysunku 8.2 widać drzewo odzwierciedlające hierarchię uniwersytetu. Innymi przykładami drzew są drzewa genealogiczne, drzewa oddające gramatyczną strukturę zdań oraz drzewa ilustrujące taksonomiczną hierarchię organizmów, roślin czy osobowości. Niemal wszystkie dziedziny nauki wykorzystują drzewa do reprezentacji struktur hierarchicznych.

Rys. 8.2. Hierarchiczna struktura uniwersytetu przedstawiona w formie drzewa

Definicja drzewa nie narzuca żadnych warunków na liczbę synów danego węzła. Wielkość ta może zmieniać się od 0 do dowolnej liczby naturalnej. Dla drzew hierarchicznych jest to własność pożądana. Uniwersytet na przykład ma tylko dwie filie, ale
#170
każda z nich może mieć inną liczbę wydziałów. Drzewa tego typu są stosowane w systemach obsługi baz danych, zwłaszcza w modelu hierarchicznym. Reprezentowanie hierarchii nie jest jednak jedynym przeznaczeniem drzew. Co więcej, w dalszych rozważaniach ten aspekt zastosowań drzew zostanie potraktowany dość pobieżnie, głównie przy omawianiu drzew wyrażeń. W tym rozdziale skoncentrujemy się na operacjach na drzewach, które umożliwiają przyspieszenie procesu wyszukiwania.
Rozważmy n-elementową listę. Aby odnaleźć element, poszukiwanie trzeba rozpocząć od początku listy i przeglądać ją aż do znalezienia elementu lub osiągnięcia końca listy. Nawet jeśli lista jest uporządkowana, to przeszukiwanie zawsze musi zaczynać się od pierwszego rekordu. Jeśli zatem lista ma 10000 elementów, a należy dotrzeć do informacji w ostatnim rekordzie, to trzeba przejść wszystkich jego 9999 poprzedników, co stanowi oczywistą niedogodność. Jeśli wszystkie elementy przechowujemy w drzewie uporządkowanym, a więc takim, w którym elementy są umieszczane zgodnie z pewnym określonym wcześniej kryterium porządku, to liczba sprawdzeń może być znacząco zmniejszona, nawet kiedy szukamy najdalszego elementu. Na przykład listę z rysunku 8.3a można przekształcić w drzewo z rysunku 8.3b.

Rys. 8.3. Przekształcenie listy (a) w drzewo (b)

Czy przy konstrukcji tego drzewa użyto rozsądnego kryterium uporządkowania? Aby sprawdzić, czy liczba 31 jest na liście, trzeba wykonać osiem porównań. Czy liczbę porównań można zmniejszyć, jeśli te same elementy uporządkujemy w drzewie od góry do dołu i od lewej do prawej? Jaki algorytm umożliwiłby nam wykonanie tylko trzech sprawdzeń: jednego dla korzenia - 2, jednego dla jego środkowego syna - 12 i jednego dla jedynego syna tego węzła - 31? Liczba 31 mogła być umieszczona na tym samym poziomie co 12 albo mogła być synem węzła 10. Takie uporządkowanie drzewa nie wnosi nic naprawdę interesującego, jeśli idzie o wyszukiwanie. (Podejście to wykorzystuje algorytm sortowania za pomocą kopca, omawiany w dalszej części tego rozdziału). Musimy zatem wybrać lepsze kryterium.
#171
Dotychczas dopuszczaliśmy drzewa, w których każdy węzeł może mieć dowolną liczbę synów. Istnieją algorytmy opracowane dla drzew z odpowiednio dobraną liczbą synów w węźle (zob. następny rozdział), jednak w tym rozdziale będziemy zajmować się tylko drzewami binarnymi. Drzewo binarne to drzewo (być może puste), w którym każdy węzeł ma co najwyżej dwóch synów, a każdy syn jest opisany jako lewy albo prawy. Drzewa na rysunku 8.4 są przykładami drzew binarnych, podczas gdy drzewo struktury uniwersytetu z rysunku 8.2 - nie. Ważną właściwością drzew binarnych, którą wykorzystamy później przy szacowaniu oczekiwanej złożoności algorytmów sortowania, jest liczba liści.

Rys. 8.4. Przykłady drzew binarnych

Poziom węzła to liczba krawędzi od korzenia do tego węzła plus jeden. W myśl tej definicji korzeń jest na poziomie 1, jego synowie - na poziomie 2 itd. Jeśli wszystkie węzły na wszystkich poziomach, oprócz ostatniego, miałyby po dwóch synów, to mielibyśmy 1 =2^0 węzłów na poziomie 1, 2 = 2^1 węzłów na poziomie 2, 4 = 2^2 węzłów na poziomie 3 i, ogólnie, 2^i węzłów na poziomie i+1. Drzewo spełniające ten warunek będziemy nazywać pełnym drzewem binarnym. W drzewie tym wszystkie węzły wewnętrzne mają obydwu swoich synów, a wszystkie liście znajdują się na tym samym poziomie. Z powyższych uwag wynika, że każde drzewo binarne ma co najwyżej 2^i węzłów na poziomie i+1. W rozdziale 11 obliczymy liczbę liści w drzewie decyzyjnym, które jest drzewem binarnym o węzłach mających albo zero, albo dwóch synów. Ponieważ liście mogą być rozsiane po całym drzewie decyzyjnym i mogą pojawiać się na każdym poziomie oprócz poziomu 1, więc nie można podać ogólnego wzoru na liczbę węzłów, gdyż jest ona zmienna. Można go jednak przybliżyć, zauważając że w dowolnym niepustym drzewie binarnym, którego węzły wewnętrzne mają dokładnie po dwóch synów, liczba liści m jest większa od liczby węzłów wewnętrznych k, dokładniej m = k+1.
Jeśli drzewo składa się z samego korzenia, to obserwacja ta jest w oczywisty sposób prawdziwa. Jeśli jest ona prawdziwa dla jakiegoś drzewa, to dołączenie dwóch liści do jednego z już istniejących liści powoduje jego zamianę w węzeł wewnętrzny, a więc zmniejszenie moli zwiększenie k o 1. Ponieważ jednak do drzewa przybyły dwa nowe liście, m zwiększa się o 2. Po tych poprawkach otrzymujemy równanie
#172
(m-1) + 2 = (k+1)+1, czyli m = k+1, a więc dokładnie to, co chcieliśmy (zob. rys. 8.5). Wynika stąd, że i+1-poziomowe pełne drzewo decyzyjne ma 2^i liści, a na podstawie powyższej obserwacji ma również 2^i-1 węzłów wewnętrznych, co czyni łącznie
2^i + 2^i - 1 = 2^(i+1) - 1 węzłów.

Rys. 8.5. Dodanie liścia do drzewa (a), przy zachowaniu relacji między liczbą liści a liczbą węzłów wewnętrznych

W rozdziale tym szczególną uwagę poświęcimy drzewom poszukiwań binarnych (ang. binary search trees - BST). Drzewo poszukiwań binarnych ma następującą własność: jeśli jakiś jego węzeł n zawiera wartość v, to wszystkie wartości przechowywane w jego lewym poddrzewie (drzewie, którego korzeń jest lewym synem n) są mniejsze od v, a wszystkie wartości przechowywane w prawym poddrzewie są większe od v. Z powodów, o których wspomnimy później, będziemy unikać umieszczania wielu kopii tej samej wartości w jednym drzewie. Próba dokonania tego może zostać potraktowana jako błąd. Znaczenie pojęć "mniejszy" i "większy" zależy od typu wartości przechowywanych w drzewie. Zazwyczaj używa się oznaczeń "<" i ">", jeśli w drzewie są przechowywane liczby. Dla tekstów stosuje się porządek alfabetyczny (leksykograficzny). Drzewa na rysunku 8.6 są drzewami poszukiwań binarnych.
Zwróćmy uwagę, że na rysunku 8.6c jest przedstawione drzewo z tymi samymi danymi, które zawierała lista, poszukiwania na której mieliśmy usprawnić. Algorytm znajdowania elementu w tym drzewie jest dosyć prosty. W każdym węźle porównujemy przechowywaną w nim wartość z kluczem, którego szukamy. Jeśli klucz jest mniejszy niż ta wartość, to przechodzimy do lewego poddrzewa i próbujemy dalej. Jeśli jest większy, to próbujemy w prawym poddrzewie. Jeśli jest taki sam, to poszukiwanie można oczywiście przerwać. Przerywamy je także, kiedy nie ma dokąd iść, co oznacza, że klucza nie ma w drzewie. Aby na przykład znaleźć liczbę 31, wystarczy wykonać tylko trzy sprawdzenia: najpierw sprawdzamy, czy szukana liczba
#173
Rys. 8.6. Przykłady drzew poszukiwań binarnych

znajduje się w korzeniu. Następnie, ponieważ 31 jest większe niż 13, sprawdzamy prawego syna korzenia, zawierającego wartość 25. W końcu, ponieważ liczba 31 jest znowu większa niż wartość w bieżącym węźle, przechodzimy do prawego syna i odnajdujemy wartość 31.
Najgorsze dla tego drzewa binarnego są przypadki poszukiwania liczb 26, 27, 28 lub 30, ponieważ w każdym z nich potrzebujemy czterech sprawdzeń (dlaczego?). Dla wszystkich innych wartości liczba sprawdzeń jest mniejsza niż cztery. Teraz widać, dlaczego element powinien występować w drzewie tylko raz. Jeśli może pojawiać się wielokrotnie, to możliwe są dwa podejścia. W pierwszym odnajdujemy pierwsze wystąpienie elementu, a pozostałe ignorujemy. Wtedy drzewo zawiera zbędne węzły, same z siebie nigdy nie używane; dochodzimy do nich jedynie przy szukaniu innych kluczy. W drugim podejściu możemy chcieć odnaleźć wszystkie wystąpienia danego elementu. Takie poszukiwanie musiałoby się zawsze kończyć w liściu. Aby na przykład odnaleźć w drzewie wszystkie wystąpienia liczby 13, trzeba sprawdzić korzeń 13, następnie jego prawego syna 25(Jeśli przyjmiemy konwencję, że klucze w prawym poddrzewie są większe bądź równe, a w lewym - mniejsze niż klucz w danym węźle (przyp. tłum.)) i w końcu węzeł 20. Poszukiwanie odbywałoby się zgodnie ze scenariuszem najgorszego przypadku: trzeba dojść aż do liścia w nadziei (lub w obawie), że natrafi się jeszcze na jakieś wystąpienia szukanego elementu.
Zanim zaimplementujemy algorytm przeglądania drzewa poszukiwań binarnych, musimy wybrać sposób implementacji drzew binarnych.

8.2. Realizacja drzew binarnych

Drzewa binarne można zaimplementować na co najmniej dwa sposoby: jako tablicę lub strukturę wiązaną. Aby zaimplementować drzewo jako tablicę, deklarujemy węzeł jako strukturę z polem przeznaczonym na dane i dwoma polami "wskaźnikowymi". Pola te będą zawierały indeksy komórek tablicy, w których umieszczeni są lewy syn i prawy syn węzła, jeśli istnieją. Na przykład drzewo z rysunku 8.6c może reprezentować
#174
tablica widoczna na rysunku 8.7. Korzeń może zawsze mieścić się w pierwszej komórce (o numerze 0), a -1 może oznaczać brak odpowiedniego syna. W tej reprezentacji dwóch synów węzła 13 znajduje się na pozycjach 4 i 2, a prawy syn węzła 31 nie istnieje.

Rys. 8.7. Tablica reprezentująca drzewo z rysunku 8.6c

Indeks; Info; Lewy; Prawy
0; 13; 4; 2
1; 31; 6; -1;
2; 25; 7; 1
3; 12; -1; -1
4; 10; 5; 3
5; 2; -1; -1;
6; 29; -1; -1
7; 20; -1; -1

Rys. 8.7. Tablica reprezentująca drzewo z rysunku 8.6c

Ta implementacja może jednak być niedogodna, zwłaszcza przy statycznym przydziale pamięci, ponieważ rozmiar tablicy staje się częścią programu i musi być znany zawczasu. Jest to kłopotliwe, gdyż dane mogą nie zmieścić się w tablicy, jeśli przeznaczymy na nią za mało miejsca, albo zmarnujemy pamięć, jeśli przydzielimy jej za dużo. Problem jest niebagatelny, ponieważ rozmiary drzew często są zmienne i może być niełatwo przewidzieć, ile węzłów zostanie utworzonych podczas wykonania programu. Zdarza się czasami, że tablicowa implementacja drzew bywa dogodna i zalecana. Zastosujemy ją przy omawianiu sortowania za pomocą kopca, chociaż użyjemy tam tablicy danych, a nie rekordów. Zazwyczaj jednak dynamiczna struktura danych jest efektywniejszym sposobem reprezentacji drzewa. W przykładach z tego rozdziału będziemy wykorzystywać dynamiczne struktury danych.
Każdy węzeł jest strukturą składającą się z pola przeznaczonego na informację i dwóch pól wskaźnikowych, tym razem jednak będą to prawdziwe wskaźniki, a nie indeksy innych elementów tablicy. Poniższy kod stanowi definicję węzła:

struct node_rec {
eltype key;
struct node_rec *left, *right;
};
typedef struct node_rec *tree_type;

8.3. Wyszukiwanie w drzewie poszukiwań binarnych

Drzewa poszukiwań binarnych, jak sama nazwa wskazuje, zostały stworzone głównie w celu przyspieszenia procesu wyszukiwania. Przy użyciu reprezentacji wskaźnikowej procedura wyszukiwania w drzewie BST może wyglądać następująco:
#175
tree_type search1(tree_type node, eltype key)
{
while (node)
/* Niezmiennik: jeśli klucz key w ogóle jest w drzewie, to znajduje się w poddrzewie o korzeniu node. */
if (key == node->key)
return node;
else if (key < node->key)
node = node->left;
else node = node->right ;
return NULL;
}

Pętli while możemy się pozbyć, stosując rekurencyjną implementację procedury wyszukiwania:

tree_type search2(tree_type node, eltype key)
{
if (node)
if (key == node->key)
return node;
else if (key < node- >key)
return search2(node->left, key);
else return search2(node->right, key);
else return NULL;
}

W tym przykładzie wersja iteracyjna wydaje się być prostsza i czytelniejsza niż implementacja rekurencyjna. Ponieważ jest także szybsza niż jej rekurencyjny odpowiednik, lepiej używać funkcji search1().
Złożoność wyszukiwania mierzy się liczbą porównań wykonanych podczas tego procesu. Liczba ta zależy od liczby węzłów na ścieżce od korzenia do poszukiwanego wierzchołka. Ściślej mówiąc, złożoność to długość ścieżki wiodącej do węzła plus 1. Zależy ona od kształtu drzewa i pozycji wierzchołka w drzewie.
Łączna długość ścieżek (oznaczymy ją IPL - od ang. internat path length) to suma długości ścieżek od korzenia do wszystkich węzłów, którą obliczamy, sumując Sigma(i-1)l_i po wszystkich poziomach i, gdzie l_i, jest liczbą węzłów na poziomie i. Pozycja węzła w drzewie jest wyznaczona przez długość ścieżki. Przeciętna odległość węzła od korzenia, zwana średnią długością ścieżki, dana jest wzorem IPL/n i zależy od kształtu drzewa. W najgorszym przypadku, kiedy drzewo staje się listą, wielkość ta wynosi 1/n Sigma_i=1;^n(i-1)=(n-1)/2=O(n), a wyszukiwanie zakończone niepowodzeniem zajmuje zawsze n jednostek czasu.
#176
Najlepszy przypadek zachodzi, kiedy wszystkie liście w drzewie wysokości h są na co najwyżej dwóch poziomach, a jedynie węzły z przedostatniego poziomu mogą mieć jednego syna. Dla uproszczenia obliczeń przybliżymy średnią długość ścieżki dla takiego drzewa, oznaczoną jako path^.,, przez średnią długość ścieżki w pełnym drzewie binarnym tej samej wysokości.
Patrząc na proste przykłady, przekonujemy się, że dla pełnego drzewa binarnego wysokości h mamy IPL = Sigma_i = 1;^h-1(i2^i). Z tego oraz z faktu, że Sigma_i=1;^h-1(i2^i) = 2^h-2, wynika iż

IPL=2IPL-IPL=(h-1)2^h-Sigma_i=1;^h-1(i2^i) = (h-2)2^h+2

Jak już ustaliliśmy, liczba węzłów w pełnym drzewie binarnym wynosi n = 2^h-1 zatem

path_best=IPL/n=((h-2)2^h+2)/(2^h-1) w przyb.=h-2

co zgadza się z faktem, że w drzewie tym połowa węzłów leży na poziomie liści ze ścieżką długości h - 1. Wysokość
h = lg(n + 1 ), więc path_best=lg(n + 1 ) - 2; średnia długość ścieżki w idealnie zrównoważonym drzewie binarnym to
[lg(n + 1 )]=O(lg n), gdzie [x] oznacza najmniejszą liczbę całkowitą nie mniejszą niż x.
Przeciętny przypadek przeciętnego drzewa mieści się gdzieś między -(n+1)/2 a lg(n+1)-2. Czy złożoność poszukiwania węzła leżącego na przeciętnej pozycji w drzewie o przeciętnym kształcie jest bliższa O(n), czy O(lg n)? Najpierw należy matematycznie zamodelować pojęcie przeciętnego kształtu drzewa.
Korzeń drzewa binarnego może mieć lewe poddrzewo puste, a prawe zawierające wszystkie n - 1 węzłów. Może mieć także jeden węzeł w lewym poddrzewie, a n - 2 w prawym i tak dalej. Może wreszcie mieć puste prawe poddrzewo, a wszystkie pozostałe węzły w lewym. To samo rozumowanie można zastosować do obu pod-drzew korzenia, do ich poddrzew i tak dalej aż do liści. Średnia długość ścieżki będzie średnią z wszystkich tych rozmaicie ukształtowanych drzew.
Załóżmy, że drzewo zawiera węzły od 1 do n. Jeśli / jest korzeniem, to jego lewe poddrzewo zawiera i- 1 węzłów, a prawe n- i węzłów. Jeśli path_i-1 oraz path_n-i, są średnimi długościami ścieżek w tych poddrzewach, to średnią długością ścieżki w całym drzewie jest
path_n(i) = [(n-1)(path_(i-1)+1)+(n-i)(path_(n-i)+1)]/n

Jeśli przyjmiemy, że elementy trafiają do drzewa losowo, korzeniem może być z jednakowym prawdopodobieństwem każda liczba
i, 1#177
path_n =1/n Sigma_i=1;^n(path_n(i))=1/n^2 Sigma_i=1;^n((i-1)(path(_i-1)+1))+(n-i)(path(_i-i)+1)=
2/n^2 Sigma_i=1;n-1(i(path_(i)+1))

z którego oraz z tego, że path_1=O, otrzymujemy 2ln n = 2ln 2lg n= 1,386lg n jako przybliżenie pathn (zob. dodatek A.4). Jest to przybliżenie średniej liczby porównań w przeciętnym drzewie. Wielkość ta wynosi O(lg n), a więc bliższa jest najlepszemu niż najgorszemu przypadkowi. Pokazuje ona też, że niewiele można tu ulepszyć, ponieważ pathb_es/path_n w przyb.=0,7215, czyli średnia długość ścieżki w najlepszym przypadku różni się jedynie o 27,85% od oczekiwanej długości ścieżki w przypadku średnim. Wyszukiwanie w drzewie binarnym jest zatem przeważnie bardzo efektywne, nawet bez równoważenia drzewa. Jest to jednak prawdą tylko dla losowo utworzonych drzew, ponieważ w mocno niezrównoważonych i wydłużonych drzewach, przypominających kształtem listy, czas wyszukiwania wynosi O(n), co jest nie do zaakceptowania, skoro można osiągnąć złożoność logarytmiczną.

8.4. Przechodzenie drzewa

Przechodzenie drzewa to proces odwiedzania każdego węzła w drzewie dokładnie raz. Można je interpretować jako umieszczenie wszystkich węzłów w jednej linii, czyli linearyzację drzewa.
Definicja przechodzenia narzuca tylko jeden warunek - odwiedzenie każdego węzła 1-krotnie - ale nie określa kolejności, w jakiej węzły mają być odwiedzane. Jest więc tyle sposobów przejścia drzewa, ile permutacji węzłów; dla drzewa o n węzłach jest n! takich marszrut. Większość z nich jednak jest dość chaotyczna i nieregularna, więc ich implementacji brakowałoby waloru ogólności: dla każdego n trzeba by implementować osobny zbiór procedur przechodzenia, a tylko niektórych z nich można by użyć dla innych danych. Na przykład dwa spośród możliwych sposobów przejścia drzewa z rysunku 8.6c, które mogłyby mieć jakieś zastosowanie, określają ciągi 2, 10, 12, 20, 13, 25, 29, 31 oraz 29, 31, 20, 12, 2, 25, 10, 13. Pierwszy zawiera najpierw liczby parzyste, a potem nieparzyste, w porządku rosnącym. Drugi ciąg składa się z liczb wypisanych od prawej do lewej według poziomów, zaczynając od poziomu najniższego, a kończąc na korzeniu. Ciąg 13, 31, 12, 2, 10, 29, 20, 25 nie wykazuje żadnej regularności ani w uporządkowaniu liczb, ani w kolejności odwiedzanych węzłów w drzewie. Występuje tu po prostu losowe przechodzenie od węzła do węzła i najprawdopodobniej ciąg ten do niczego się nie może przydać. Jednakże wszystkie powyższe ciągi są wynikami trzech spośród 8! =40320 równoprawnych sposobów przejścia drzewa. Wobec takiej obfitości sposobów obejścia drzewa i ewidentnej bezużyteczności większości z nich ograniczymy naszą uwagę do dwóch tylko klas, a mianowicie przechodzenia wszerz i w głąb.
#178

8.4.1. Przechodzenie wszerz

Przechodzenie wszerz (ang. breadth-first traveral) polega na odwiedzaniu każdego węzła, poczynając od korzenia i przesuwając się w dół poziom za poziomem, odwiedzając węzły na każdym poziomie od strony lewej do prawej. Jeśli drzewo z rysunku 8.6c przejdziemy wszerz, to w wyniku otrzymamy ciąg 13, 10, 25, 2, 12, 20, 31, 29.
Implementacja tej metody jest stosunkowo prosta, jeśli użyjemy kolejki. Po odwiedzeniu węzła jego synowie, jeśli istnieją, są umieszczani na końcu kolejki, a następnie jest odwiedzany węzeł z początku kolejki. Jeśli rozważymy węzeł z poziomu n, to jego synowie są na poziomie n+1, skoro więc umieszczamy ich na końcu kolejki, zostaną odwiedzeni dopiero po wszystkich węzłach z poziomu n. Zatem ograniczenie, że wszystkie węzły z poziomu n muszą być odwiedzone, zanim odwiedzimy którykolwiek węzeł z poziomu n+ 1, jest zachowane.
Implementacja stosownej procedury jest pokazana na rysunku 8.8. W przykładzie tym zakładamy, że funkcje enq() i deq() zostały już zaimplementowane oraz że zadeklarowano zmienną queue, będącą dwuelementową tablicą do przekazania jako parametr. Pierwsza komórka tablicy przechowuje początek, a druga - koniec kolejki.

void breadth_first(tree_type node)
{
if (node) {
enq(node,queue);
while (!emptyq(queue)) {
node = deq(queue);
visit(node);
if (node->left)
enq(node->left, queue);
if (node->right)
enq(node->right, queue);
}
}
}

Rys. 8.8. Implementacja przechodzenia drzewa wszerz

8.4.2. Przechodzenie w głąb

Podczas przechodzenia w głąb (ang. depth-first traversal) wędrujemy najdalej jak się da w lewo (w prawo), potem cofamy się do najbliższego rozgałęzienia, robimy jeden krok w prawo (w lewo) i znowu idziemy jak najdalej w lewo (w prawo). Powtarzamy ten proces dopóty, dopóki nie zostaną odwiedzone wszystkie węzły. Definicja ta
#179
jednak nie określa wyraźnie, kiedy węzły zostają odwiedzone: przed kontynuacją marszu w dół drzewa, czy też po powrocie? Istnieje więc kilka wariantów metody przechodzenia wszerz.
W metodzie tej można wyróżnić trzy istotne zadania:

V - odwiedzenie węzła
L - przejście lewego poddrzewa
R - przejście prawego poddrzewa

W systematycznym sposobie przejścia zadania te są wykonywane w tej samej kolejności dla każdego węzła. Trzy zadania można uszeregować na 3!-6 sposobów, więc istnieje sześć możliwych wariantów przechodzenia:

VLR VRL
LVR RVL
LRV RLV

Jeśli liczba sposobów przechodzenia nadal wydaje się duża, to można ją zredukować do trzech, w których poruszamy się zawsze od strony lewej do prawej, i skoncentrować się na pierwszej kolumnie. Te trzy sposoby przechodzenia drzewa binarnego mają swoje standardowe nazwy:

VLR - preorder
LVR - inorder
LRV - postorder

Opierając się bezpośrednio na symbolicznych opisach powyższych trzech sposobów przechodzenia drzewa, można zaimplementować realizujące je krótkie i eleganckie procedury, co widać na rysunku 8.9.
Funkcje te mogą wydawać się aż zbyt proste, jednak ich prawdziwa siła leży w rekursji, w rzeczywistości w rekursji podwójnej. Faktyczna praca jest wykonywana przez system na stosie roboczym. Upraszcza to kodowanie, ale nakłada duży ciężar na system. Aby ułatwić zrozumienie tego procesu, omówimy bardziej szczegółowo przechodzenie drzewa w porządku inorder.
W metodzie inorder najpierw jest odwiedzane lewe poddrzewo bieżącego węzła, potem on sam, a na końcu prawe poddrzewo. Wszystko to oczywiście zachodzi, jeśli drzewo jest niepuste. Zanim odsłonimy tajemnicę działania procedury, analizując zmiany zachodzące na stosie programu, określmy efekt tego działania, odwołując się do rysunku 8.10. Następujące kroki odpowiadają poszczególnym przypadkom oznaczonym jako (a)-(e) na tym rysunku:
(a) Węzeł 15 jest korzeniem, dla niego zatem funkcja inorder () jest wywołana po raz pierwszy. Funkcja wywołuje teraz samą siebie dla jego lewego syna, węzła 4.
#180
(b) Węzeł 4 nie jest równy NULL, więc wywołuje się inorder () dla węzła 1. Ponieważ węzeł 1 jest liściem, to znaczy oba jego poddrzewa są puste, wywołania inorder () dla tych poddrzew nie spowodują dalszych wywołań rekurencyjnych, bo warunek w instrukcji if nie jest spełniony. Odwiedzony zostaje węzeł 1, a następnie węzeł 4. Węzeł 4 nie ma prawego poddrzewa, więc inorder () zostanie wywołane jedynie po to, aby to sprawdzić, a zaraz potem zostanie odwiedzony węzeł 15.
(c) Węzeł 15 ma prawe poddrzewo, zatem zostaje wywołana funkcja inorder () dla węzła 20.
(d) Funkcja inorder () zostaje wywołana ponownie dla węzła 16. Węzeł ten, a następnie węzeł 20 zostają odwiedzone.
(e) Następuje wywołanie inorder () dla węzła 25 i jego pustego lewego poddrzewa, po czym węzeł 25 zostaje odwiedzony i na koniec jest wywoływane inorder () dla pustego prawego poddrzewa węzła 25.

preorder( tree_type node)
{
if (node) {
visit (node);
preorder (node->left);
preorder (node->right);
}
}

inorder ( tree_type node)
{
if (node) {
inorder (node->left);
visit (node);
inorder (node->right);
}
}

postorder ( tree_type node)
{
if (node) {
postorder (node->left);
postorder (node->right);
visit (node);
}
}

Rys. 8.9. Implementacja przechodzenia drzewa w głąb
#181
Rys. 8.10. Przechodzenie drzewa metodą inorder

Jeśli podczas odwiedzania jest wypisywana wartość przechowywana w węźle, to zostanie wypisany ciąg

1 4 15 16 20 25

Kluczowe w przechodzeniu drzewa jest to, że trzy zadania L, V i R są wykonywane dla każdego węzła oddzielnie. Oznacza to, że przechodzenie prawego poddrzewa jest wstrzymane, dopóki nie zostaną zakończone dwa pierwsze zadania L i V. Kiedy zostaną wykonane, można je wykreślić, jak na rysunku 8.11.
W celu prezentacji działania funkcji inorder () prześledzimy zmiany zachodzące na stosie programu. Liczby w nawiasach oznaczają adresy powrotów umieszczone w komentarzach po lewej stronie w kodzie funkcji inorder ().

inorder (tree_type node)
{
if (node) {
/* 1 */ inorder (node->left) ;
/* 2 */ visit (node);
/* 3 */ inorder (node->right);
/* 4 */ }
}
#182
Rys. 8.11. Szczegóły niektórych spośród początkowych kroków przechodzenia drzewa metodą inorder

Prostokąt (zob. rys. 8.12) ze skierowaną do góry strzałką i liczbą oznacza bieżącą wartość węzła node włożoną na stos. Na przykład ^4 oznacza, że zmienna node wskazuje na węzeł, wartością którego jest 4. Na rysunku 8.12 widać zmiany zachodzące na stosie programu podczas wykonywania funkcji inorder () na drzewie z rysunku 8.10.

(a) Początkowo stos programu jest pusty (a raczej tylko przyjmujemy, że jest pusty, pomijając to, co zostało na nim umieszczone przed pierwszym wywołaniem inorder ()).

(b) Podczas pierwszego wywołania na stos jest wkładany adres powrotu do funkcji inorder () oraz wartość węzła node, czyli ^15. Drzewo wskazywane przez node jest niepuste, warunek w instrukcji i f jest spełniony, zatem funkcja inorder () jest wywoływana ponownie dla węzła 4.

(c) Zanim zacznie się jej wykonywanie, na stosie jest umieszczany adres powrotu (2) i bieżąca wartość węzła node - ^4. Ponieważ wartością zmiennej node nie jest NULL, funkcja inorder () będzie wywołana dla lewego syna node, węzła 1.

{Uwaga:oznaczenie ^4 - strzałka w górę przy liczbie 4}

(a)

puste

(b)

^15
(powrót)

(c)

^4
(2)
^15
(powrót)

(d)

^1
(2)
^4
(2)
^15
(powrót)

(e)

NULL
(2)
^1
(2)
^4
(2)
^15
(powrót)

(f)

^1 <- Wypisz 1
(2)
^4
(2)
^5

(g)

NULL
(4)
^1
(2)
^4
(2)
^15
(powrót)

(h)

^1
(2)
^4
(2)
^15
(powrót)

(i)

^4 <- Wypisz 4
(2)
^15
(powrót)

(j)


NULL
(4)
^4
(2)
^15
(powrót)

(k)

^4
(2)
^15
(powrót)

(l)

^15 <- Wypisz 15
(powrót)

(m)

^20
(4)
^15
(powrót)

(n)

^16
(2)
^20
(2)
^15
(powrót)

(o)

NULL
(2)
^16
(2)
^20
(4)
^15
(powrót)

(p)

^16 <- Wypisz 16
(2)
^20
(4)
^15
(powrót)

(q)

NULL
(4)
^16
(2)
^20
(4)
^15
(powrót)

(r)

^16
(2)
^20
(4)
^15
(powrót)

(s)

^20 <- Wypisz 20
(4)
^15
(powrót)

(t)

^25
(4)
^20
(4)
^15
(powrót)

(u)

NULL
(2)
^25
(4)
^20
(4)
^15
(powrót)

(v)

^25 <- Wypisz 25
(4)
^20
(4)
^15
(powrót)

(w)

NULL
(4)
^25
(4)
^20
(4)
^15
(powrót)

(x)

^25
(4)
^20
(4)
^15
(powrót)

(y)

^20
(4)
^15
(powrót)

(z)

^15
(powrót)

(aa)

puste

Rys. 8.12. Zmiany na stosie czasu wykonania podczas przejścia drzewa metodą inorder
#84
(d) Najpierw jest zapamiętywany adres powrotu i wartość węzła node. Zmienna node wskazuje na węzeł 1; wskaźnik ten oraz adres (2) są wkładane na stos.

(e) Funkcja inorder () jest wywoływana dla lewego syna węzła 1. Na stosie jest umieszczany adres (2) i bieżąca wartość parametru node, czyli NULL. Ponieważ wartością node jest NULL, następuje natychmiastowe zakończenie wywołania inorder (); w trakcie tego zakończenia rekord wywołania jest usuwany ze stosu.

(f) System odwołuje się teraz do swego stosu programu, odtwarza wartość zmiennej node, Tl, wykonuje instrukcję spod adresu (2) i wypisuje liczbę 1. Ponieważ przetwarzanie węzła node nie zostało jeszcze zakończone, wartość node i adres (2) pozostają na stosie.
(g) Wykonana zostaje instrukcja spod adresu (3), która jest wywołaniem funkcji inorder () dla prawego syna węzła 1. Najpierw jednak na stos wędruje adres (4) i bieżąca wartość zmiennej node - NULL. Ponieważ parametr node jest równy NULL, funkcja inorder () kończy działanie; w trakcie tego jest oczyszczany stos.

(h) System odtwarza teraz poprzednią wartość zmiennej node, ^1, i wykonuje instrukcję (4).

(i) Ponieważ to już koniec tego wywołania inorder (), system sięga ponownie na stos, odtwarza wartość zmiennej node, ^4, i kontynuuje wykonywanie programu od instrukcji (2). Powoduje to wypisanie liczby 4, a potem wywołanie funkcji inorder () dla prawego syna węzła node, czyli NULL.

Powyższe kroki to dopiero początek. Całość jest pokazana na rysunku 8.12.
Teraz powinniśmy rozważyć problem nierekurencyjnej implementacji naszych trzech algorytmów przechodzenia drzewa. Jak wspominaliśmy w rozdziale 7, implementacja rekurencyjna bywa często mniej efektywna niż jej nierekurencyjny odpowiednik. Jeśli funkcja zawiera dwa wywołania rekurencyjne, to podwaja się problem możliwej nieefektywności. Czy można usunąć rekursję z tej implementacji? Odpowiedź musi być twierdząca, ponieważ jeśli nie usuniemy rekursji z kodu źródłowego, to i tak zrobi to za nas system. Pytanie trzeba by zatem przeformułować: czy jest to celowe?
Przyjrzyjmy się najpierw nierekurencyjnej wersji przechodzenia drzewa metodą preorder:

void iterative_preorder (tree_type p)
{
if (P) {
push(p,stack);
while (!empty(stack)) {
p =pop(stack);
visit(p);
#185
if (p->right)
push(p->right,stack);
if (p->left) /* lewego syna wkładamy po prawym, */
push(p->left, stack); /* żeby był na czubku stosu */
}
}
}

Procedura iterative_preorder () jest dwa razy dłuższa niż procedura preorder (), ale nadal jest krótka i czytelna. Korzysta ona jednak intensywnie ze stosu. Z tego powodu są potrzebne pomocnicze procedury do obsługi stosu, a całość implementacji nie jest już taka krótka. Chociaż uniknęliśmy dwóch wywołań rekurencyjnych, na każdy obrót pętli while przypadają teraz czasem i cztery wywołania: od zera do dwóch wywołań push (), jedno wywołanie pop () i jedno visit(). Trudno to uważać za poprawę efektywności. Jeśli jednak zamiast funkcji użyjemy makrodefinicji, to efektywność może się zwiększyć.
Zwróćmy uwagę, że rekurencyjne implementacje trzech metod przechodzenia drzewa różnią się między sobą tylko kolejnością instrukcji. W funkcji preorder () na przykład najpierw jest odwiedzany węzeł, a dopiero potem następują wywołania dla lewego i prawego poddrzewa. Z kolei w postorder () oba wywołania poprzedzają odwiedzenie węzła. Czy możemy równie łatwo przekształcić nierekurencyjną wersję metody preorder w nierekurencyjną metodę postorder? Niestety, nie. W funkcji iterative_preorder () odwiedzenie węzła następuje przed włożeniem jego synów na stos. Kolejność ta nie ma jednak tak naprawdę znaczenia. Jeśli najpierw umieścimy synów na stosie, a dopiero potem odwiedzimy węzeł, to znaczy vi sit (p) przestawimy za oba wywołania push (), otrzymany kod nadal implementuje przechodzenie drzewa metodą preorder. Istotne jest tutaj to, żeby pop () poprzedzało zarówno vi sit (), jak i obydwa wywołania push (). Nierekurencyjne wersje metod inorder i postorder trzeba będzie zatem zaprojektować niezależnie.
Nierekurencyjną wersję metody postorder uzyskamy dość łatwo, jeśli zauważymy, że ciąg utworzony za pomocą metody postorder od lewej do prawej (kolejność LRV) jest odwróceniem ciągu otrzymanego metodą preorder od prawej do lewej (kolejność VRL). Wtedy implementację funkcji iterative_preorder () można przerobić na iterative_postorder (). (W jaki dokładnie sposób to zrobić?)
Nierekurencyjne przechodzenie drzewa w porządku inorder jest sprawą bardziej skomplikowaną. Jedną z możliwych implementacji podajemy poniżej:

void iterative_inorder(tree_type p)
{
while (p) {
while(p) {
#186
if (p->right) /* umieść na stosie prawego syna (jeśli */
push (p->right , stack) ; /* istnieje) oraz sam węzeł i idź w lewo */
push (p, stack) ;
p = p->left;
}
p = pop (stack) ; /* zdejmij ze stosu węzeł bez lewego syna */
while (!empty(stack) &&
!(p->right)) { /* odwiedź go i wszystkie węzły */
visit (p) ; /* bez prawego syna */
p = pop (stack) ;
}
visit (p) ; /* odwiedź też pierwszy węzeł mający */
if (! empty( stack)) /* prawego syna ( jeśli taki istnieje) */
p = pop (stack) ;
else p = NULL;
}
}

Widzimy tutaj wyraźnie siłę rekursji: funkcja iterative_inorder () jest niemal nieczytelna i bez dokładnego wyjaśnienia niełatwo byłoby stwierdzić, do czego służy. Z drugiej strony w rekurencyjnej funkcji inorder () natychmiast jest widoczne jej przeznaczenie i struktura. Dlatego wersji nierekurencyjnej można bronić tylko wtedy, kiedy okaże się, że daje ona znaczący zysk, jeśli idzie o czas wykonania, a procedura jest w programie wywoływana często. W innych sytuacjach jest zalecane użycie funkcji inorder (), a nie jej iteracyjnego odpowiednika.

8.4.3. Przechodzenie w głąb bez użycia stosu

Drzewa z łańcuchami dowiązań
W poprzednim podrozdziale analizowaliśmy zarówno rekurencyjne, jak i nierekurencyjne procedury przechodzenia drzewa, ale w obydwu przypadkach korzystały one, pośrednio lub jawnie, ze stosu do przechowywania informacji o węzłach, których przetwarzanie nie zostało jeszcze zakończone. W procedurach rekurencyjnych wykorzystywany był stos programu, a w wariantach nierekurencyjnych stos był jawnie zdefiniowany i obsługiwany przez programistę. Kłopot w tym, że obsługa stosu zajmuje dodatkowy czas, trzeba też przeznaczyć nieco pamięci na sam stos. W najgorszym przypadku, kiedy drzewo ma niekorzystny kształt, stos będzie przechowywać informacje o niemal wszystkich węzłach, co stanowi niebagatelne obciążenie, jeśli mamy do czynienia z bardzo dużymi drzewami.
Efektywniej byłoby wbudować stos w samo drzewo. Robi się to, włączając do węzła specjalne dowiązania. Są to wskaźniki do poprzednika i następnika danego węzła w pewnym ciągu, a drzewo, którego węzły wykorzystują takie dowiązania,
#187
nazywamy drzewem z łańcuchem dowiązań (ang. threaded tree). W każdym węźle drzewa potrzebne byłyby cztery pola na wskaźniki, co znowu zabiera cenną pamięć.
Problem można rozwiązać, przeciążając istniejące pola wskaźnikowe. Operator nazywamy przeciążonym, jeśli ma różne znaczenia; operator * w języku C jest tu dobrym przykładem, bo można go używać jako operatora mnożenia, a także jako odwołania do zmiennej wskazywanej. W drzewie wskaźniki lewy i prawy wskazują na synów węzła, ale można ich też użyć jako wskaźników do poprzednika i następnika, przeciążając je w ten sposób, czyli nadając im dodatkowe znaczenie. Jak rozróżnimy te znaczenia? W przypadku operatora przeciążonego znaczenie zawsze wynika jednoznacznie z kontekstu. W przypadku drzew trzeba jednak dodać nowe pole informujące o aktualnym znaczeniu wskaźników.
Ponieważ wskaźnik może wskazywać tylko jeden węzeł na raz, lewy wskaźnik jest albo wskaźnikiem do lewego syna, albo do poprzednika. Podobnie prawy wskaźnik będzie wskazywał albo na prawe poddrzewo, albo na następnik. To, czym jest poprzednik i następnik, zależy od rozważanego ciągu. Ponieważ interesują nas głównie ciągi utworzone przez przejście drzewa metodami preorder, inorder i postorder, na rysunku 8.13 są podane przykłady drzew z łańcuchami dowiązań dla tych trzech ciągów.

Rys. 8.13. Drzewa z łańcuchami dowiązań do wykorzystania przy przechodzeniu drzewa metodą: (a) preorder, (b) inorder i (c) postorder

Z rysunku 8.13 wynika, że trzeba zachowywać obydwa wskaźniki, do poprzednika i do następnika, jednak nie zawsze tak jest. Czasem wystarczy użyć tylko jednego dowiązania, co widać z poniższej implementacji metody inorder w drzewie z łańcuchem dowiązań, w której potrzebne są jedynie wskaźniki do następników.

void threaded_inorder(threaded_tree_type p)
{
threaded_tree_type prev;
if (p) { /* przetwarzaj tylko niepuste drzewa */
while (p->left) /* idź do skrajnie lewego węzła */
#188
p =p->left;
while (p) {
visit(p);
prev = p;
p = p->right; /* idź do prawego węzła i jeśli */
if (p && prev->successor == 0) /* jest on synem, */
while (p->left) /* idź do skrajnie lewego węzła, */
p = p->left; /* w przeciwnym razie odwiedź następnik */
}
}
}

Procedura jest względnie prosta. Linia przerywana na rysunku 8.14 wskazuje kolejność, w jakiej p przechodzi węzły. Zwróćmy uwagę, że do przejścia drzewa jest nam potrzebna tylko zmienna p (i jedna zmienna pomocnicza). Nie potrzebujemy stosu, oszczędzamy więc pamięć. Czy jednak rzeczywiście? Jak wspominaliśmy, węzły muszą mieć pole informujące o znaczeniu prawego wskaźnika. W implementacji funkcji threaded_inorder () rolę tę odgrywa pole successor. Może ono przyjmować tylko dwie wartości, "tak" lub "nie". Najlepszym sposobem jego implementacji jest pole bitowe, jak w poniższej deklaracji:

Rys. 8.14. Ścieżka obejścia w porządku inorder drzewa z łańcuchem dowiązań

struct node_rec {
eltype key;
unsigned successor:1;
struct node_rec *left, *right;
};
typedef struct node_rec *threaded_tree_type;

Przy użyciu tej deklaracji pole successor potrzebuje tylko jednego bitu pamięci komputera, ilości nieznacznej w porównaniu z pozostałymi polami. Szczegóły jednak bardzo silnie zależą od implementacji. System operacyjny niemal na pewno dopełni strukturę bitową, aby zapewnić poprawne wyrównanie do granicy słowa maszynowego.
#189
Skoro tak, to nasze pole successor będzie zajmowało przynajmniej jeden bajt, jeśli nie całe słowo, co niweczy argument o oszczędności pamięci dzięki użyciu drzew z łańcuchami dowiązań. Jak wiemy, zwykły algorytm korzysta ze stosu, ale stos ten będzie duży jedynie w skrajnych przypadkach (jeśli został zaimplementowany jako lista, a nie tablica). Najczęściej jego rozmiar jest znikomy w porównaniu z wielkością dużego drzewa. A co z czasem działania? Eksperymenty wykazują, że funkcja threaded_inorder() jest szybsza niż iterative_inorder() o 5-15%. Zatem szybkość nie jest argumentem dyskwalifikującym iterative_inorder () jako rozsądny wybór.

Przechodzenie za pomocą przekształcania drzewa

Pierwsza grupa algorytmów przechodzenia drzewa analizowanych dotychczas w tym rozdziale potrzebowała stosu do zachowania pewnych informacji potrzebnych do dalszego działania. W drzewach z łańcuchami dowiązań stos jest wbudowany w samo drzewo za cenę rozszerzenia reprezentacji węzła o dodatkowe pole, umożliwiające rozróżnienie między interpretacją prawego wskaźnika jako wskaźnika do syna a interpretacją go jako wskaźnika do następnika. Potrzebujemy dwóch takich pól, jeśli używamy zarówno następnika, jak i poprzednika. Możliwe jest jednak przejście drzewa bez użycia ani stosu, ani łańcucha dowiązań. Istnieje wiele takich algorytmów, a ich działanie opiera się na dokonywaniu tymczasowych zmian w drzewie podczas przechodzenia go. Zmiany te polegają na przypisywaniu nowych wartości niektórym polom wskaźnikowym. Drzewo może przy tym chwilowo utracić swoją drzewiastą strukturę, którą trzeba odtworzyć przed zakończeniem działania algorytmu. Technikę tę zilustrujemy eleganckim algorytmem zaproponowanym przez Josepha M. Morrisa, zastosowanym do przejścia drzewa w porządku inorder.
Łatwo zauważyć, że przechodzenie metodą inorder jest bardzo proste w przypadku drzew zdegenerowanych, w których żaden węzeł nie ma lewego syna (zob. rys. 8. l e). Nie musimy rozważać lewego poddrzewa w żadnym węźle, zatem zamiast zwykłych trzech kroków - LVR (odwiedź lewe poddrzewo, odwiedź węzeł, odwiedź prawe poddrzewo) dla każdego węzła wykonuje się tylko dwa kroki - VR. Nie trzeba zachowywać żadnych informacji o bieżącym stanie przetwarzanego węzła przed przejściem do jego lewego syna z tego prostego powodu, że lewego syna nie ma. Algorytm Morrisa uwzględnia tę obserwację, tymczasowo przekształcając drzewo tak, by przetwarzany węzeł nie miał lewego syna; można go więc odwiedzić i przetwarzać jego prawe poddrzewo. Algorytm można streścić następująco:

while nie koniec
if węzeł nie ma lewego syna
odwiedź go;
idź w prawo;
else uczyń go prawym synem skrajnie prawego węzła w jego lewym poddrzewie;
idź do korzenia tego poddrzewa;
#190
Algorytm ten z powodzeniem obejdzie drzewo, ale tylko raz, zniszczy bowiem jego pierwotną strukturę. Trzeba zatem zapamiętywać pewną informację, która pozwoli odtworzyć początkową postać drzewa. Osiąga się to, zachowując lewy wskaźnik węzła przesuwanego w dół swojego lewego poddrzewa, co widać na rysunku 8.15.

void Morris_inorder(tree_type p)
{
tree_type tmp;

while (p)
if (p->left == NULL) {
visit(p);
p =p->right;
}
else {
tmp =p->left;
while (tmp->right && /* idź do skrajnie prawego węzła */
tmp->right != p) /* w lewym poddrzewie lub do */
tmp = tmp->right; /* tymczasowego ojca węzła p */
if (tmp->right == NULL) { /* jeśli tak, to został osiągnięty */
tmp->right = p; /* skrajnie prawy węzeł; uczyń go */
p = p->left; /* tymczasowym ojcem bieżącego korzenia */
}
else { /* w przeciwnym razie został znaleziony */
visit(p); /* tymczasowy ojciec; odwiedź węzeł p, */
tmp->right = NULL; /* a potem odetnij prawy wskaźnik jego */
p - p->right; /* tymczasowego ojca, przywracając */
} /* poprzednią sytuację */
}
}

Rys. 8.15. Implementacja algorytmu Morrisa przechodzenia drzewa w porządku inorder

Szczegóły działania ilustruje rysunek 8.16. Poniższy opis jest podzielony na akcje wykonywane podczas kolejnych obrotów zewnętrznej pętli while.

1. Początkowo p wskazuje na korzeń, który ma lewego syna. W efekcie wewnętrzna pętla while spowoduje ustawienie wskaźnika tmp na węzeł 7, będący skrajnie prawym węzłem w poddrzewie lewego syna węzła 10, wskazywanego przez p (rys. 8.16a). Ponieważ nie dokonaliśmy dotychczas żadnych przekształceń, więc węzeł tmp nie ma prawego syna, a wewnętrzna instrukcja i f czyni korzeń, węzeł 10, prawym synem węzła tmp. Węzeł 10 zachowuje swój lewy wskaźnik do węzła 5, pierwotnie jego lewego syna. Teraz nasza struktura nie jest już drzewem, ponieważ zawiera cykl (rys. 8.16b). Kończy to pierwszą iterację.
#191
Rys. 8.16. Przechodzenie drzewa metodą Morrisa

2. Wskaźnik p wskazuje na węzeł 5, także mający lewego syna. Najpierw tmp osiąga skrajnie prawy węzeł w lewym poddrzewie, czyli 3 (rys. 8.16c), a potem bieżący korzeń, węzeł 5, staje się prawym synem węzła 3, nadal utrzymując dowiązanie do węzła 3 poprzez lewy wskaźnik (rys. 8.16d).

3. Ponieważ wskazywany przez p węzeł 3 nie ma lewego syna, w trzeciej iteracji węzeł ten jest odwiedzany, a wskaźnik p przeniesiony na jego prawego syna, węzeł 5 (rys. 8.16e).

4. Lewy wskaźnik węzła 5 jest niepusty, więc znaleziony zostaje tymczasowy ojciec węzła 5, którym jest węzeł aktualnie wskazywany przez zmienną tmp (rys. 8.16f). Następnie jest odwiedzany węzeł 5 i jest odtwarzana konfiguracja drzewa z rysunku 8.16b poprzez przypisanie prawemu wskaźnikowi węzła 3 wartości NULL (rys. 8.16g).
#192
5. Odwiedzany jest wskazywany obecnie przez p węzeł 7, a wskaźnik p przesuwa się w dół do jego prawego syna (rys. 8.16h).

6. Uaktualniana jest zmienna tmp tak, by wskazywała na tymczasowego ojca węzła 10 (rys. 8.16i). Następnie jest odwiedzany węzeł 10, który z powrotem staje się korzeniem dzięki wyzerowaniu prawego wskaźnika węzła 7 (rys. 8.16J).

7. Wreszcie jest odwiedzany węzeł 20 bez żadnych dalszych komplikacji, ponieważ nie ma on lewego syna ani nie zmieniał położenia w drzewie.

Kończy to działanie algorytmu Morrisa. Zwróćmy uwagę, że zewnętrzna pętla while wykonuje siedem obrotów, chociaż w drzewie na rysunku 8.16 jest tylko pięć wierzchołków. Jest to związane z faktem, że w drzewie tym jest dwóch lewych synów, zatem liczba dodatkowych iteracji zależy od liczby lewych synów w całym drzewie. Algorytm będzie działał gorzej dla drzew z dużą liczbą lewych synów.


8.5. Wstawianie

Procedura wyszukiwania w drzewie binarnym nie modyfikuje samego drzewa. Przegląda ona drzewo w ściśle określony sposób, badając niektóre lub nawet wszystkie klucze w drzewie, ale samo drzewo po takiej operacji pozostaje nie zmienione. Przechodzenie drzewa może je zmienić, ale może też pozostawić je w takim samym stanie. To, czy drzewo zostanie zmodyfikowane, zależy od działań podejmowanych przez procedurę visit(). Niektóre operacje zawsze powodują pewne określone

Rys. 8.17. Wstawianie węzłów do drzew poszukiwań binarnych
#193
zmiany w drzewie; do operacji takich należy dodawanie węzłów, usuwanie ich, modyfikowanie elementów przechowywanych w drzewie, scalanie drzew i równoważenie drzewa w celu zmniejszenia jego wysokości. W niniejszym podrozdziale zajmiemy się wstawianiem węzła do drzewa poszukiwań binarnych.
Aby wstawić do drzewa nowy węzeł o nazwie n_node, trzeba dojść w drzewie do węzła, który nazwiemy t_node, nie mającego odpowiedniego syna, i przyłączyć do niego nowy węzeł. Węzeł t_node znajdujemy tą samą metodą, której używaliśmy przy przeszukiwaniu drzewa: klucz wstawianego węzła n_node jest porównywany z wartością w węźle bieżącym, oznaczonym jako c_node. Jeśli wartość klucza jest mniejsza niż ta wartość, próbujemy dalej z lewym synem węzła c_node (jeśli istnieje), w przeciwnym razie sprawdzamy prawego syna. Jeśli węzeł c_node nie ma syna, którego właśnie mamy sprawdzić, to przeglądanie jest przerywane, a synem tym staje się węzeł n_node. Powyższą procedurę ilustruje rysunek 8.17.
Na rysunku 8.18 jest przedstawiony algorytm wstawiania węzła.

void insert (tree_type *root_addr, eltype key)
{
tree_type p, previous = NULL, new_node, malloc();

new_node =malloc (sizeof(struct node_rec));
new_node->left = new_node->right = NULL;
new_node->key = key;
p = *root_addr; /* znajdź miejsce do wstawienia węzła new_node */
while (p) {
previous = p;
if (p->key > key)
p =p->left;
else p = p->right;
}
if (!*root_addr); /* drzewo jest puste */
*root_addr = new_node;
else if (previous->key > key)
previous->left = new_node;
else previous->right = new_node;
}
}

Rys. 8.18. Implementacja algorytmu wstawiania - pierwsza wersja

Procedura ta nie jest wystarczająco elastyczna, aby można ją było zawsze stosować w powyższej formie. Radzi sobie z liczbami i pojedynczymi znakami, ale kiedy klucze w drzewie będą tablicami, strukturami albo uniami, procedura insert () będzie działać niepoprawnie, jeśli w ogóle będzie działać. Powodem tego jest to, że w dwóch instrukcjach if zastosowaliśmy relację ">" tak samo jak w konstrukcji if (p->key > key). Jeśli klucz reprezentuje napis, to porównanie ">" będzie
#194
dotyczyć wskaźników, a nie treści napisów. Dla napisów trzeba by użyć funkcji strcmp() w połączeniu z ">". Dla struktur porównywanie musi spełniać jeszcze większe wymagania, jeśli na przykład trzeba brać pod uwagę dwa pola przy wyznaczaniu relacji porządku między dwiema strukturami.
Podobny problem stwarza instrukcja przypisania. Polu key struktury utworzonej właśnie przez malloc () jest nadawana wartość początkowa przekazana jako parametr w instrukcji przypisania new_node->key = key. Znowu nie będzie kłopotu, jeśli key jest liczbą albo znakiem. Jeśli jednak jest tablicą, to key jest adresem tablicy, a nie samą tablicą. Dlatego w new_node->key zostanie zapisany adres tablicy, a nie jej zawartość. Aby tego uniknąć, trzeba przepisać tablicę komórka po komórce z key do new_node->key. W przypadku napisów można użyć funkcji strcpy(). Z powyższych powodów innej wersji procedury insert () potrzebowalibyśmy dla napisów, tablic liczb i struktur. Jeśli jest to niepożądane, wystarczy jedna wersja insert (), ale trzeba uogólnić instrukcje przypisania i porównania.
Użyjemy w tym celu wskaźników do funkcji, przekazując procedurze insert () jako parametry wskaźnik do funkcji dokonującej przypisania i wskaźnik do funkcji porównującej. W nowej wersji insert () trzeba zmienić tylko nagłówek i trzy wiersze, co widać na rysunku 8.19.

void insert2(void **root_addr, eltype *key,
int (*comparison) (eltype *, eltype *) ,
void (*copy) (eltype *, eltype *) ) /* zmiana */
{
tree_type p, previous = NULL, new_node, malloc();

new_node = malloc ( sizeof(struct node_rec));
new_node->left = new_node->right =NULL;
(*copy)(&new_node->key, key); /* zmiana */
p = *root_addr;
while (p) {
previous =p;
if ((*comparison)(&p->key, key)) /* zmiana */
p =p->left;
else p = p->right ;
}
if (!*root_addr)
*root_addr =new_node;
else if ((*comparison)(&previous->key,key)) /* zmiana */
previous->left = new_node;
else previous->right =new_node;
}

Rys. 8.19. Implementacja algorytmu wstawiania -druga wersja
#195
Taką procedurę można umieścić w bibliotece i włączać do każdego programu, który zdefiniuje funkcje comparison () i copy (). Przy definiowaniu tych dwóch funkcji trzeba jednak zachować dużą ostrożność. Jeśli w programie zdefiniujemy eltype jako int, to funkcje przekazywane do procedury insert2 () trzeba by zdefiniować następująco:

void copy1(eltype *e1, eltype *e2)
{
*e1= *e2;
}

i

comparison1 (eltype *v1, eltype *v2)
{
return *v1 > *v2;
}

insert2() zaś wraz z parametrami należałoby wywołać tak:

insert2(&root, &n, comparison1, copy1);

Jeśli natomiast program zawiera deklaracje

typedef char eltype;
eltype s [20];

to sytuacja się zmienia, ponieważ zmienna s jest wskaźnikiem do tablicy znaków, a nie samą tablicą. W związku z tym, skoro jeden z parametrów procedury insert2 () jest zadeklarowany jako eltype *key, przekazywany jest wskaźnik do wskaźnika do napisu. Musi to zostać uwzględnione w funkcjach przekazywanych procedurze insert2 () jako parametry. Funkcjami tymi są

void copy2(eltype *s1, eltype *s2)
{
strcpy(*s1,s2);
}

i

comparison2 (eltype *s1, eltype *s2
{
return strcmp(*s1,s2) >0;
}
#196
Zwróćmy uwagę, że przed s1 jest gwiazdka, ale nie ma jej przed s2. Jest tak, ponieważ funkcja comparison2 () otrzymuje dwa różne parametry: wskaźnik do wskaźnika i zwykły wskaźnik. Wywołanie insert2 () wraz z parametrami ma postać

insert2(&root, s, comparison2, copy2);

void InsertlnThreadedTree(threaded_tree_type *root_addr, eltype key)
{
threaded_tree_type p, prev = NULL, new_node;

new_node= (threaded_tree_type) malloc (sizeof(struct threaded_node_reci
new_node->left = new_node->right = NULL;
new_node->key = key;
new_node->successor =O;
if ( ! *root_addr) { /* drzewo jest puste */
*root_addr = new_node;
return;
}
p = *root_addr; /* znajdź miejsce do wstawienia węzła new_node */
while (p) { prev=p;
if (p->key > key)
p =p->left;
else if (p->successor == 0) /* idź wprawo, jeśli jest to */
p = p->right; /* syn, a nie następnik; nie idź */
else break;/* za dowiązaniem do następnika */
}
if (prev->key > key) { /* jeśli new_node jest lewym synem * /
prev->left = new_node; /* swojego ojca, to ojciec staje się /*
new_node->successor =1; /*też jego następnikiem */
new_node->right =prev;
}
else if (prev->successor == 1) { /* jeśli ojciec węzła new_node */
new_node->successor = 1; /* nie jest skrajnie prawym węzłem, */
prev->successor = 0; /* to uczyń jego następnik następnikiem */
new_node->right = prev->right; /* węzła new_node */
prev->right = new_node;
}
else prev->right =new_node; /* w przeciwnym razie new_node */
} /* nie ma następnika */

Rys. 8.20. Implementacja algorytmu wstawiania węzła do drzewa z łańcuchem dowiązań

Analizując problem przechodzenia drzew binarnych, zaprezentowaliśmy trzy podejścia: przechodzenie z wykorzystaniem stosu, przechodzenie z zastosowaniem łańcucha dowiązań i przechodzenie za pomocą przekształcania drzewa. W pierwszym podejściu drzewo nie zmienia się podczas całego procesu. W trzecim zmienia się, ale
#197
później wraca do stanu początkowego. Jedynie drugie podejście wymaga pewnych pomocniczych operacji na drzewie, aby proces stał się wykonalny: trzeba utworzyć łańcuch dowiązań. Można to robić za każdym razem przed rozpoczęciem procedury przechodzenia i usuwać modyfikacje po jej zakończeniu. Jeśli przechodzenie drzewa jest wykonywane rzadko, może to być praktyczne rozwiązanie. Czwartym podejściem jest zachowywanie łańcucha dowiązań podczas wszystkich operacji przy wstawianiu nowego elementu do drzewa poszukiwań binarnych.
Procedura wstawiania węzła do drzewa z łańcuchem dowiązań jest prostym rozszerzeniem procedury insert () dla zwykłych drzew poszukiwań binarnych, polegającym na uaktualnianiu dowiązań, kiedy jest to potrzebne. Procedura poprawia łańcuch pomocny w przechodzeniu drzewa metodą inorder i zajmuje się tylko następnikami, nie poprzednikami.
Węzeł mający prawego syna ma następnik gdzieś w swoim prawym poddrzewie. Nie potrzebuje on zatem dowiązania do następnika. Dowiązania takie są potrzebne w celu umożliwienia pójścia w górę drzewa, a nie schodzenia w dół. Następnik węzła bez prawego syna znajduje się gdzieś nad nim. Wszystkie, z wyjątkiem jednego, węzły bez prawego syna będą miały dowiązania do swoich następników. Jeśli węzeł staje się prawym synem innego węzła, to dziedziczy następnik po swoim nowym ojcu. Jeśli węzeł staje się lewym synem innego węzła, jego nowy ojciec staje się jego następnikiem. Na rysunku 8.20 jest przedstawiona implementacja tego algorytmu - procedura InsertlnThreadedTree (). Kilka pierwszych operacji wstawienia widać na rysunku 8.21.

Rys. 8.21. Wstawianie węzłów do drzewa z łańcuchem dowiązań
#198

8.6. Usuwanie

Usuwanie węzła jest kolejną operacją niezbędną do obsługi drzew poszukiwań binarnych. Poziom trudności w realizacji tej operacji zależy od położenia usuwanego węzła w drzewie. Znacznie trudniej jest usunąć węzeł mający obydwa poddrzewa niż liść; stopień komplikacji algorytmu usuwania jest proporcjonalny do liczby synów węzła. Przy usuwaniu węzła z drzewa poszukiwań binarnych mogą wystąpić trzy przypadki:
1. Węzeł jest liściem, nie ma synów. Ten przypadek jest najłatwiejszy. Odpowiedni wskaźnik ojca usuwanego węzła przyjmuje wartość NULL, a pamięć zajmowana przez węzeł jest zwalniana za pomocą funkcji free(), co ilustruje rysunek 8.22.

Rys. 8.22. Usuwanie liścia

2. Węzeł ma jednego syna. Przypadek ten nie jest skomplikowany. Wskaźnik ojca do danego węzła zostaje przeniesiony na syna tego węzła. W ten sposób syn węzła zostaje podniesiony o jeden poziom do góry, a wszystkie jego pra-pra-...prawnuki tracą jedno ,,pra" ze swego oznaczenia pokrewieństwa. Usunięcie na przykład węzła 20 (zob. rys. 8.23) polega na ustawieniu prawego wskaźnika jego ojca, zawierającego liczbę 15, tak by wskazywał na jedynego syna węzła 20, czyli 16.

3. Węzeł ma dwóch synów. W tym przypadku nie da się wykonać żadnej jednofazowej operacji, ponieważ ani prawy, ani lewy wskaźnik ojca nie może wskazywać na obydwu synów węzła jednocześnie. W bieżącym podrozdziale omówimy dwa różne rozwiązania tego problemu.

Rys. 8.23. Usuwanie węzła z jednym synem
#199

8.6.1. Pierwsze rozwiązanie

W rozwiązaniu tym z dwóch poddrzew robi się jedno drzewo, a następnie przyłącza sieje do ojca usuwanego węzła. Metoda ta jest nazywana usuwaniem przez scalanie. Powstaje jednak pytanie, w jaki sposób połączyć te poddrzewa? Z natury drzew poszukiwań binarnych wynika, że dowolna wartość w prawym poddrzewie jest większa niż każda wartość w lewym poddrzewie, więc najlepsze, co można zrobić, to znaleźć w lewym poddrzewie węzeł o największej wartości i uczynić go ojcem korzenia prawego poddrzewa. Symetrycznie, można znaleźć węzeł o najmniejszej wartości w prawym poddrzewie i przyłączyć pod niego lewe poddrzewo.
Potrzebny jest nam skrajnie prawy węzeł w lewym poddrzewie. Możemy go znaleźć, przemieszczając w tym poddrzewie wzdłuż prawych wskaźników, dopóki nie natrafimy na wartość NULL. Oznacza to, że węzeł nie ma prawego syna i skierowanie jego prawego wskaźnika na prawe poddrzewo nie grozi naruszeniem własności drzew poszukiwań binarnych. To samo można by zrobić, przypisując lewemu wskaźnikowi skrajnie lewego węzła w prawym poddrzewie korzeń lewego poddrzewa. Rysunek 8.24 obrazuje tę operację, a rysunek 8.25 zawiera implementację algorytmu.

Rys. 8.24. Schemat usuwania przez scalanie

Kod ten wymaga nieco bardziej szczegółowych wyjaśnień. Po pierwsze, przekazywana jest zmienna *root_addr, będąca wskaźnikiem do tree_type. Jednak już sam typ tree_type został zdefiniowany jako typ wskaźnikowy instrukcją typedef struct node_rec *tree_type;. Dlatego to, co jest przekazywane do funkcji delete () jako parametr, jest wskaźnikiem do wskaźnika do węzła, zwykle do korzenia. Spowodowane jest to tym, że wszystkie parametry, oprócz tablic, są w języku C przekazywane przez wartość, to znaczy, że funkcja używa kopii przekazywanych parametrów zamiast oryginałów. Jeśli więc trzeba usunąć korzeń i uaktualnić wskazującą nań zmienną root, to nie można przekazać root jako parametru, bo wszystkie poczynione na niej zmiany miałyby tylko lokalny efekt wewnątrz funkcji delete (). Skoro zmiany mają być trwałe, należy przekazać wskaźnik do zmiennej root.
#200

void delete_by_merging (tree_type *node)
{
tree_type tmp = *node;
if (*node) {
if (!(*node)->right) /* węzeł nie ma prawego syna: jego lewego syna */
*node = (*node)->left; /* (jeśli istnieje) przyłączamy pod jego ojca */
else if (!(*node)->left) /* węzeł niema lewego syna: jego prawego syna */
*node = (*node)->right; /* (jeśli istnieje) przyłączamy pod jego ojca */
else { /* trzeba scalić poddrzewa: */
tmp = (*node)->left; /*1. idź w lewo */
while (tmp->right) /* 2. a potem w prawo, dopóki można */
tmp = tmp->right;
tmp->right = /* 3. połącz skrajnie prawy węzeł */
(*node)->right; /* lewego poddrzewa z korzeniem prawego poddrzewa */
tmp = *node; /* 4. */
*node= (*node)->left; /*5. */
}
free(tmp); /* 6. */
}
}

void delete(tree_type *root_addr, eltype key)
{
tree_type node = *root_addr, previous = NULL;

if (!(*root_addr)) {
printf("drzewo jest puste\n") ;
return;
}
while (node) {
if (node->key == key)
break;
previous =node;
if (node->key > key)
node = node->left;
else node = node->right;
}
if (node)
if (node == *root_addr)
delete_by_merging (root_addr);
else if (previous->left == node)
delete_by_merging (&previous->left) ;
else delete_by_merging (&previous->right) ;
else printf ( " klucza %d nie ma w drzewie\n" , key) ;
}

Rys. 8.25. Implementacja algorytmu usuwania przez scalanie
#201

Po drugie, może się wydawać, że funkcja delete () zawiera niepotrzebnie powtórzony kod. Zamiast skorzystać z funkcji search1() przed wywołaniem delete_by_merging (), funkcja delete () zapomina o search1() i szuka węzła do usunięcia, używając własnego kodu. Wykorzystanie search1() w funkcji delete () byłoby jednak zgubnym uproszczeniem. Funkcja search1() zwraca wskaźnik do węzła zawierającego klucz key. W funkcji delete () jest istotne, aby wskaźnik ten był umieszczony w jednym z pól wskaźnikowych ojca tego węzła. Innymi słowy, wywołującemu search1 () wystarczy, jeśli ma dostęp do węzła skądkolwiek, podczas gdy delete () potrzebuje dostępu do niego z lewego albo prawego pola wskaźnikowego jego ojca. W przeciwnym razie zostałaby usunięta cała gałąź drzewa zaczynająca się od danego węzła, a nie tylko sam węzeł. Jedną z przyczyn tego jest fakt, że search1 () koncentruje się na zawartości węzła o danym kluczu, a delete () skupia się na samym węźle jako elemencie większej struktury, konkretnie - drzewa.

Rys. 8.26. Szczegóły usuwania przez scalanie

Na rysunku 8.26 są pokazane kolejne kroki tej operacji. Widać na nim zmiany dokonywane podczas działania funkcji delete (). Cyfry na tym rysunku odpowiadają numerom umieszczonym w komentarzach kodu z rysunku 8.25.
Algorytm usuwania przez scalanie może spowodować wzrost wysokości drzewa. Niekiedy otrzymane drzewo może być bardzo niezrównoważone, co ilustruje rysunek 8.27a. Czasami wysokość może się zmniejszyć (zob. rys. 8.27b). Algorytm ten niekoniecznie musi być nieefektywny, ale na pewno daleko mu do doskonałości. Potrzebujemy algorytmu, który gwarantuje, że wysokość drzewa nie wzrośnie przy usuwaniu jednego z jego węzłów.
#202
Rys. 8.27. Wysokość drzewa po usunięciu węzła przez scalanie może się zwiększyć (a) lub zmniejszyć (b)

8.6.2. Drugie rozwiązanie

Alternatywne rozwiązanie zaproponował Thomas Hibbard, a ulepszył Donald Knuth. Przypadek, kiedy węzeł ma dwóch synów, można sprowadzić do jednego z dwóch prostych przypadków - kiedy węzeł jest liściem albo ma tylko jednego syna. Robi się to, zastępując węzeł jego bezpośrednim poprzednikiem lub następnikiem w drzewie. Jak już wspominaliśmy przy omawianiu pierwszego algorytmu, poprzednikiem węzła jest skrajnie prawy węzeł w lewym poddrzewie, a następnikiem - skrajnie lewy węzeł w prawym poddrzewie. Najpierw trzeba znaleźć poprzednik. Robimy to tak jak w opisanym powyżej algorytmie, idąc jeden krok w lewo i osiągając w ten sposób korzeń lewego poddrzewa węzła, a potem idąc w prawo, jak długo się da. Następnie wartością znalezionego węzła zastępujemy wartość w węźle do usunięcia. Tutaj właśnie pojawia się jeden z dwóch prostych przypadków. Jeśli skrajnie prawy węzeł jest liściem, zachodzi przypadek pierwszy, a jeśli ma on jednego (lewego) syna - drugi. W celu zaimplementowania tego algorytmu, trzeba napisać nową funkcję delete_by_copying (), natomiast procedurę delete() można wykorzystać ponownie, zastępując w niej wywołania delete_by_merging () przez wywołania delete_by_copying(). Rysunek 8.28 zawiera kod tej ostatniej funkcji.
#203

void delete_by_copying (tree_type *node)
{
tree_type previous, tmp = *node;
if (!(*node)->right) /* węzeł node nie ma prawego syna */
*node= (*node)->left;
else if(!(*node)->left) /* węzeł node nie ma lewego syna */
*node= (*node)->right;
else {
tmp = ( *node) ->left; /* węzeł node ma obu synów */
previous = *node; /*1.*/
while (tmp->right) { /* 2. */
previous = tmp;
tmp = tmp->right;
}
(*node)->key = tmp->key; /* 3 . */
if (previous == *node)
previous->left = tmp->left;
else previous->right = tmp->left; /* 4. */
}
free(tmp); /* 5. */
}

Rys. 8.28. Implementacja algorytmu usuwania przez kopiowanie

Na rysunku 8.29 można krok po kroku prześledzić działanie algorytmu. Cyfry pod diagramami odnoszą się do numerów w komentarzach umieszczonych w kodzie funkcji delete_by_copying ().
Algorytm nie zwiększa wysokości drzewa, ale i tak może stwarzać problemy, jeśli stosuje się go wiele razy w połączeniu ze wstawianiem węzłów. Jest on asymetryczny; zawsze usuwa bezpośredni poprzednik węzła node, zmniejszając wysokość lewego poddrzewa, a prawe pozostawiając nie zmienione. Wskutek późniejszych wstawień prawe poddrzewo węzła node może się powiększyć, a jeśli ponownie będziemy usuwać informację z węzła node, wysokość prawego poddrzewa pozostanie taka sama. Po wielu wstawieniach i usunięciach całe drzewo staje się przechylone w prawo; jego prawe poddrzewo jest gęstsze i większe niż lewe.
Aby obejść ten problem, można zastosować proste usprawnienie, przerabiając algorytm na symetryczny. Możemy na przemian usuwać poprzednik węzła node z lewego poddrzewa i jego następnik z prawego poddrzewa. Jest to znaczące ulepszenie. Symulacje, które zrealizował Jeffrey Eppinger, wykazują, że oczekiwana łączna długość ścieżek (IPL) dla wielu wstawień przy asymetrycznym usuwaniu wynosi Teta(n lg^(3)n) dla n węzłów, a przy symetrycznym tylko Teta(n lg n). Wyniki teoretyczne otrzymane przez J. Culbersona potwierdzają te wnioski. Według Culbersona wstawianie i asymetryczne usuwanie daje oczekiwaną wartość IPL równą Teta(n sqr t) i średni
#204
czas wyszukiwania Teta(nsqr n), podczas gdy przy symetrycznym usuwaniu średni czas wyszukiwania wynosi O(lgn), a średnia wartość IPL to, jak poprzednio,Teta(n Ig n).
Wyniki te mają umiarkowane znaczenie w praktycznych zastosowaniach. Eksperymenty pokazują, że dla 2048-węzłowego drzewa binarnego dopiero po 1,5 miliona wstawień i asymetrycznych usunięć wartość IPL staje się gorsza niż w losowo wygenerowanym drzewie.
Wyniki teoretyczne są jedynie częściowe ze względu na niezwykłą złożoność problemu. Arne Jonassen i Donald Knuth analizowali problem losowych wstawień i usunięć dla drzewa o zaledwie trzech węzłach, a wymagało to zastosowania funkcji Bessela i dwuwymiarowych równań całkowych, analiza zaś została oceniona jako "najtrudniejsza ze wszystkich dotąd przeprowadzonych dokładnych analiz algorytmów". Z tego powodu opieranie się na wynikach doświadczalnych nie jest rzeczą zaskakującą.


8.7. Równoważenie drzewa

Na początku tego rozdziału zamieściliśmy dwa argumenty przemawiające na korzyść drzew: dobrze nadają się one do reprezentowania hierarchicznej struktury jakiejś dziedziny, a proces wyszukiwania jest znacznie szybszy, gdy stosuje się drzewa zamiast list. Ten drugi argument nie zawsze jest jednak prawdziwy. Wszystko zależy od wyglądu drzewa. Na rysunku 8.30 są pokazane trzy drzewa poszukiwań binarnych.


205

Wszystkie przechowują takie same dane, ale oczywiście drzewo z rysunku 8.30a jest najlepsze, a to z rysunku 8.30c - najgorsze. W najgorszym przypadku do wyszukania obiektu w pierwszym drzewie potrzebne są trzy sprawdzenia, a w ostatnim sześć. Problem z drzewami na rysunkach 8.30b i 8.30c polega na tym, że są one nieco niesymetryczne, czy też przechylone; węzły w drzewie nie są rozłożone równomiernie, do tego stopnia, że drzewo z rysunku 8.30c praktycznie stało się listą, chociaż formalnie nadal jest drzewem. Taka sytuacja nie zdarza się w drzewach zrównoważonych.

Rys. 8.30. Różne drzewa poszukiwań binarnych zawierające tę samą informację

Drzewo binarne jest zrównoważone, jeśli różnica wysokości obu poddrzew każdego węzła w drzewie wynosi zero lub jeden. Na przykład dla węzła K na rysunku 8.30b różnica między wysokościami jego poddrzew, wynosząca jeden, jest akceptowalna. Natomiast dla węzła B różnica ta wynosi trzy, co oznacza, że całe drzewo jest niezrównoważone. Dla tego samego węzła B na rysunku 8.30c różnica jest najgorsza z możliwych, czyli pięć. Drzewo nazwiemy doskonale zrównoważonym, jeśli jest zrównoważone, a wszystkie liście znajdują się na jednym lub dwóch poziomach.
Na rysunku 8.31 jest podane, ile węzłów mogą pomieścić drzewa binarne różnej wysokości. Ponieważ każdy węzeł może mieć dwóch synów, liczba węzłów na danym poziomie jest co najwyżej podwojoną liczbą ich ojców, mieszczących się na poprzednim poziomie (oczywiście oprócz korzenia). Jeśli na przykład 10000 elementów umieścimy w doskonale zrównoważonym drzewie, to jego wysokość wyniesie [lg(10 001)] = [13,288] = 14. W praktyce oznacza to, że jeśli doskonale zrównoważone drzewo binarne zawiera 10000 węzłów, to w celu znalezienia konkretnego elementu trzeba będzie sprawdzić co najwyżej czternaście węzłów. Jest to znaczący postęp w porównaniu z 10000 sprawdzeń potrzebnych na liście (w najgorszym przypadku). Dlatego opłacalny jest trud zbudowania drzewa zrównoważonego lub przerobienia istniejącego drzewa na zrównoważone.









206

Wysokość; Węzły na jednym poziomie; Węzły na wszystkich poziomach

1; 2^0=1; 1 -2^1 - 1
2; 2^1 = 2; 3 = 2^2-1
3; 2^2 = 4; 7 = 2^3 - 1
4; 2^3 = 8; 15 = 2^4-1
..............................
..............................
11; 2^10 = 1024; 2047 = 2^11-1
...............................
...............................
14; 2^13 = 8192; 16383 = 2^14-1
..............................
..............................
h; 2^(k-1); n = 2^(k)-1
..............................
...............................

Rys. 8.31. Maksymalna liczba węzłów w drzewach binarnych różnej wysokości

Istnieje wiele metod równoważenia drzewa binarnego. Niektóre z nich polegają na ciągłym przebudowywaniu drzewa, kiedy przybywające elementy powodują jego niezrównoważenie. Niektóre polegają na przestawianiu samych danych, a następnie budowaniu drzewa, jeśli uporządkowanie danych zapewnia, że powstałe drzewo będzie zrównoważone. W niniejszym podrozdziale zaprezentujemy prostą metodę tego rodzaju.
Podobne do listy drzewo z rysunku 8.30c jest efektem szczególnej kolejności napływających danych. Jeśli dane przybywają w kolejności rosnącej lub malejącej, to drzewo będzie przypominało kształtem listę. Drzewo na rysunku 8.30b jest przechylone, ponieważ pierwszym przybyłym elementem była litera B, która poprzedza niemal wszystkie pozostałe litery, z wyjątkiem A; lewe poddrzewo B nie może więc mieć więcej węzłów niż jeden. Drzewo na rysunku 8.30a wygląda bardzo dobrze, ponieważ korzeń zawiera element leżący w pobliżu środka zbioru wszystkich możliwych elementów, a P jest mniej więcej w połowie drogi między K a Z. Uwagi te naprowadzają nas na algorytm oparty na metodzie wyszukiwania binarnego.
Zgromadźmy wszystkie napływające dane w tablicy. Następnie posortujmy ją, używając jednego z efektywnych algorytmów, które będziemy omawiać w rozdziale 11. Teraz zrobimy korzeniem środkowy element tablicy. Tablica jest podzielona na dwie podtablice: jedna między początkiem tablicy a elementem właśnie wybranym na korzeń, druga zaś między korzeniem a końcem tablicy. Lewego syna korzenia bierzemy ze środka pierwszej podtablicy, prawego ze środka drugiej. Kończy to tworzenie poziomu zawierającego synów korzenia. Następny poziom, składający się z synów synów korzenia, konstruujemy w ten sam sposób, wybierając środkowe elementy z czterech podtablic. Przykład tego procesu widać na rysunku 8.32.
Algorytm jest całkiem prosty. Najpierw umieszczamy wszystkie dane w tablicy i sortujemy ją. Następnie wstawiamy dane do drzewa, jak w poniższej funkcji:


207

Napływające dane: 5 1 9 8 7 0 2 3 4 6 Posortowana tablica: 0 1 2 3 4 5 6 7 8 9

(a) 1 2 3 [4] 5 6 7 8 9
(b) 0 [1] 2 3 [4] 5 6 7 8 9
(c) [0] [1] [2] 3 [4] 5 6 7 8 9
(d) [1] [2] [3] [4] [5] [6] [7] [8] [9]

Rys. 8.32. Utworzenie drzewa poszukiwań binarnych z uporządkowanej tablicy

void
balance (int data[], int first, int last)
{ int middle = (first+last) /2;
if (first <- last) {
insert (&root, datafmiddle]) ;
balance(data,first,middle-1);
balance(data,middle+1,last);
}
}

Algorytm ten ma jedną poważną wadę: wszystkie dane trzeba umieścić w tablicy, zanim będzie można utworzyć drzewo. Można je zapisywać w tablicy bezpośrednio po ich wprowadzeniu. W tym wypadku algorytm może okazać się nieprzydatny, jeśli drzewa trzeba używać, podczas gdy dane, które mają być w nim umieszczone, nadal napływają. Dane można jednak przenieść do tablicy z drzewa niezrównoważonego, przechodząc je metodą inorder. Drzewo można teraz usunąć i utworzyć ponownie za

208

pomocą funkcji balance (). Nie wymaga to przynajmniej stosowania żadnej procedury sortującej do ustawienia danych w kolejności.

8.7.1. Algorytm DSW

Algorytm omawiany w poprzednim podrozdziale był raczej nieefektywny, gdyż wymagał użycia dodatkowej tablicy, którą trzeba było posortować przed rozpoczęciem budowania drzewa doskonale zrównoważonego. Żeby uniknąć sortowania, trzeba było dokonać dekompozycji, a później rekonstrukcji drzewa, co może być efektywne tylko dla względnie małych drzew. Istnieją jednak algorytmy, w których potrzeba niewiele dodatkowej pamięci na pomocnicze zmienne i nie korzysta się z procedur sortujących. Bardzo elegancki algorytm, zwany algorytmem DSW, wynalazł Colin Day, a później ulepszyli Quentin F. Stout i Bette L. Warren.
Podstawową procedurą przy przekształcaniu drzewa za pomocą tego algorytmu jest rotacja. Istnieją dwa rodzaje rotacji, lewa i prawa, wzajemnie symetryczne. Prawa rotacja węzła Ch względem jego ojca Par jest wykonywana zgodnie z poniższym algorytmem:

RotateRight (Gr, Par, Ch)
i f Par nie jest korzeniem drzewa /* tzn. jeśli Gr nie jest równy NULL */
dziadek Gr węzła Ch staje się ojcem Ch, zastępując Par;
prawe poddrzewo Ch staje się lewym poddrzewem węzła Par ;
węzeł Par staje się prawym synem swego dotychczasowego lewego syna Ch;

Rys. 8.33. Prawa rotacja syna Ch względem ojca Par

Kroki wchodzące w skład tej złożonej operacji są pokazane na rysunku 8.33. Podstawą rotacji jest krok drugi, kiedy to Par, ojciec węzła Ch, staje się synem Ch, a więc ojciec i syn zamieniają się rolami. Ta zamiana ról nie może jednak wpłynąć na podstawową własność drzewa, a mianowicie na to, że jest to drzewo poszukiwań. Kroki pierwszy i trzeci w procedurze RotateRight () są potrzebne do zapewnienia, że po rotacji drzewo pozostanie drzewem poszukiwań.
Ujmując rzecz w skrócie, algorytm DSW powoduje przekształcenie dowolnego drzewa poszukiwań binarnych w drzewo o kształcie listy, zwane kręgosłupem albo



















209

linią, a następnie to rozprostowane drzewo jest przekształcane w wielu przebiegach w drzewo doskonale zrównoważone za pomocą wielokrotnych rotacji co drugiego węzła tej linii względem jego ojca.
W pierwszej fazie do utworzenia linii jest wykorzystywana poniższa procedura:

CreateBackbone(root, n)
tmp = root while (tmp != NULL)
if tmp ma lewego syna
wykonaj rotację tego
svna względem tmp; /* zatem lewy syn staje się ojcem węzła tmp */
tmp staje się węzłem, który właśnie został ojcem;
else tmp staje się węzłem, który jest prawym synem tmp;

Algorytm ten ilustruje rysunek 8.34. Zwróćmy uwagę, że wykonanie rotacji wymaga znajomości ojca węzła tmp, więc podczas implementacji algorytmu musimy zachowywać jeszcze jeden wskaźnik.

Rys. 8.34. Przekształcenie drzewa poszukiwań binarnych w linię
W najgorszym przypadku pętla while obróci się 2/7-1 razy i wykona się n-l rotacji, gdzie n jest liczbą węzłów w drzewie; czas działania pierwszej fazy wynosi O(n).
W drugiej fazie linia zostaje przekształcona w drzewo, ale tym razem drzewo będzie doskonale zrównoważone, mając liście jedynie na dwóch sąsiednich poziomach. Podczas każdego przebiegu w dół drzewa są dokonywane rotacje co drugiego węzła względem jego ojca. Jeden taki przebieg zmniejsza długość linii o połowę. Jedynie pierwszy przebieg może nie osiągnąć końca linii: jest potrzebny do uwzględnienia

210

różnicy między liczbą n węzłów w naszym drzewie a liczbą 2L'e("+l)J- l węzłów w najbliższym pełnym drzewie binarnym, gdzie bd oznacza największą liczbę całkowitą nie przekraczającą x. Nadmiarowe węzły są zatem traktowane oddzielnie.

CreatePerfectTree(n)
m = 2^[lg(n+1]-1;
wykonaj n-m rotacji, zaczynając od początku linii;
while (m > l)
m = m/2 ;
wykonaj m rotacji, zaczynając od początku Unii;

Na rysunku 8.35 jest przedstawiony przykład. Linia na rysunku 8.34e ma dziewięć węzłów, a pierwszy przebieg (przed pętlą) przekształca ją w linię pokazaną na rysunku 8.35b. Teraz są wykonywane dwa przebiegi. Na każdej linii węzły, które lewa rotacja przesunie o jeden poziom w górę, są zaznaczone jako kwadraty, a ich ojcowie, względem których są dokonywane rotacje, są oznaczeni kółkami.

Rys. 8.35. Przekształcanie linii w drzewo doskonale zrównoważone

Aby wyznaczyć złożoność fazy budowania drzewa, zauważmy że

m = 2^[lg(n+1]-1<=2^[lg(n+1]-1=n;

Liczbę rotacji możemy teraz zapisać wzorem
n-m+Sigma_i=1;^(lg (m)-1[m/2^i]<=Sigma_i=1;^(lg (m)-1[m/2^i] ->n dla dużych n
= 2 = 2


211

ponieważ szereg geometryczny Sigma(1/2^i) -> 1; zatem liczba rotacji wynosi O (n). Ponieważ
przekształcenie drzewa niezrównoważonego w linię także wymagało co najwyżej O (n) rotacji, łączny koszt zrównoważenia drzewa w algorytmie DSW jest optymalny, jeśli idzie o czas i pamięć, bo czas rośnie liniowo wraz z n, a dodatkowo używana pamięć jest bardzo niewielkiego, stałego rozmiaru.

8.7.2. Drzewa AVL
W poprzednich dwóch podrozdziałach omawialiśmy algorytmy równoważące drzewo globalnie; każdy bez wyjątku węzeł mógł brać udział w równoważeniu albo przez przemieszczanie danych rozlokowanych w węzłach, albo przez przypisywanie nowych wartości polom wskaźnikowym. Równoważenie drzewa można jednak wykonywać lokalnie, jeśli zmiany niezbędne po wstawieniu lub usunięciu elementu dotyczą tylko części drzewa. Autorami klasycznej metody tego rodzaju są Adel'son-Vel'skii i Landis, co zostało upamiętnione w nazwie drzewa modyfikowanego tą metodą: drzewo AVL.
Drzewo AVL (pierwotnie nazywane drzewem dopuszczalnym) to drzewo, w którym wysokości lewego i prawego poddrzewa każdego węzła różnią się co najwyżej o jeden. Na rysunku 8.36 na przykład wszystkie drzewa są drzewami AVL. Liczby w węzłach oznaczają współczynniki wyważenia, będące różnicami wysokości lewego i prawego poddrzewa. W drzewie AVL wszystkie współczynniki wyważenia powinny być równe +1, O albo -1. Zauważmy, że definicja drzew AVL jest taka sama jak definicja drzew zrównoważonych. Jednak pojęcie drzewa AVL ukrywa w sobie metody równoważenia drzewa. Co więcej, w odróżnieniu od dwóch wcześniej omawianych metod, metoda równoważenia drzew AVL nie gwarantuje, że otrzymane drzewo będzie doskonale zrównoważone.
Z definicji drzewa AVL wynika, że minimalna liczba węzłów w takim drzewie wyraża się równaniem rekurencyjnym

AVL_h=AVL_(h-1)+AVL_(h-2)+1

Rys. 8.36. Przykłady drzew AVL

212

gdzie AVL_0 = 0 i AVL_1 = 1 są warunkami brzegowymi (Liczby zdefiniowane tym wzorem rekurencyjnym nazywamy liczbami Leonarda.)
. Jak pokazali Adel'son-Vel'skii i Landis, wzór ten pociąga za sobą następujące ograniczenia dotyczące wysokości h drzewa AVL w zależności od liczby węzłów n:

lg(n + 1) <= h < 1,44 Ig(n + 2) - 0,328

Wysokość h daje się zatem oszacować jako O(lgn); wyszukiwanie w najgorszym przypadku wymaga logarytmicznej liczby porównań. Dla doskonale zrównoważonego drzewa binarnego tej samej wysokości h=[lg(n+ 1)]. Zatem w najgorszym przypadku czas wyszukiwania w drzewie AVL jest 44% gorszy (wyszukiwanie wymaga 44% więcej porównań) niż w najlepszym możliwym drzewie. Eksperymenty wskazują, że średnia liczba porównań przy wyszukiwaniu jest bliższa najlepszemu przypadkowi niż najgorszemu i dla dużych n wynosi Ig n + 0,25 [17]. Dlatego z drzewami AVL zdecydowanie warto się zapoznać.
Jeśli współczynnik wyważenia w dowolnym węźle drzewa AVL staje się mniejszy niż -l albo większy niż l, to drzewo musi zostać zrównoważone. Drzewo AVL przestaje być zrównoważone w czterech sytuacjach, musimy jednak przeanalizować tylko dwie spośród nich; pozostałe dwie są symetryczne. Pierwszy przypadek, efekt wstawienia węzła do prawego poddrzewa prawego syna, jest zilustrowany na rysunku 8.37. Wysokości poddrzew biorących udział w przekształceniu są zaznaczone wewnątrz nich. W drzewie AVL na rysunku 8.37a wstawiamy węzeł gdzieś do prawego poddrzewa węzła Q (rys. 8.37b), co zakłóca równowagę drzewa o korzeniu P. Zaburzenie to można jednak łatwo skorygować, wykonując rotację węzła Q względem jego ojca P (rys. 8.37c). W ten sposób współczynnik wyważenia zarówno węzła P, jak i Q staje się równy zero, czyli jest nawet lepiej niż na początku.

Rys. 8.37. Równoważenie drzewa po wstawieniu węzła do prawego poddrzewa węzła Q


213

Drugi przypadek, powstający przy wstawianiu węzła do lewego poddrzewa prawego syna, jest bardziej skomplikowany. Węzeł jest wstawiany do drzewa z rysunku 8.38a; powstające w wyniku tego drzewo jest pokazane na rysunku 8.38b, a bardziej szczegółowo na rysunku 8.38c. W celu przywrócenia równowagi drzewa wykonuje się podwójną rotację. Najpierw równoważy się drzewo Q, wykonując rotację R względem węzła Q (rys. 8.38d), a następnie ponownie wykonuje się rotację /?, tym razem względem węzła P (rys. 8.38e).
Q
Q
(a)
h-1
(b)
(c)
(e)
Rys. 8.38. Równoważenie drzewa po wstawieniu węzła do lewego poddrzewa węzła Q
W obu tych przypadkach traktowaliśmy poddrzewo o korzeniu P jako samodzielne drzewo. Może ono być jednak częścią większego drzewa AVL; węzeł P może być synem jakiegoś innego węzła w drzewie. Jeśli wstawiamy węzeł do drzewa i równowaga węzła P zostaje zachwiana, a następnie odtworzona, to czy trzeba jeszcze dodatkowo zajmować się poprzednikami P? Na szczęście nie. Zauważmy, że wysokości drzew na rysunkach 8.37c i 8.38e, będących efektem rotacji, są takie same jak wysokości drzew przed operacją wstawienia (rys. 8.37a i 8.38a) i wynoszą h+ 2. Oznacza to, że współczynnik wyważenia ojca nowego korzenia (Q na rys. 8.37c, a R na rys. 8.38e) pozostaje taki sam jak przed wstawieniem, a zmiany poczynione w poddrzewie P wystarczają do przywrócenia równowagi w całym drzewie AVL. Problem polega na znalezieniu węzła P, którego współczynnik wyważenia stał się nieakceptowalny po wstawieniu nowego węzła do drzewa.
Węzeł ten można odszukać, idąc w górę drzewa od pozycji, na którą został wstawiony nowy węzeł, w kierunku korzenia i uaktualniając współczynniki wyważenia napotykanych wierzchołków. Jeśli natrafiamy na węzeł ze współczynnikiem wyważenia ą1, to współczynnik ten może się zmienić na ą2, a pierwszy węzeł, którego współczynnik wyważenia zmienia się w ten sposób, jest korzeniem poddrzewa, którego równowagę trzeba przywrócić. Wiemy już, że nie trzeba poprawiać współczynników wyważenia powyżej tego węzła, ponieważ pozostają one nie zmienione. Jeśli jednak wszystkie współczynniki wyważenia na ścieżce od nowo wstawionego węzła do korzenia były równe zero, to wszystkie trzeba będzie uaktualnić, ale nie wykonamy żadnej rotacji.

214

Drzewo AVL na rysunku 8.39a ma ścieżkę, na której wszystkie współczynniki wyważenia są zerami. Po dostawieniu węzła na końcu tej ścieżki (rys. 8.39b) nie robimy w drzewie żadnych zmian oprócz poprawienia współczynników wyważenia wszystkich węzłów na tej ścieżce.

Rys. 8.39. Wstawienie nowego węzła do drzewa AVL, nie wymagające korygowania wysokości
Na rysunku 8.40a jest zaznaczona ścieżka, na której jeden współczynnik wyważenia jest równy +1. Wstawienie nowego węzła na końcu tej ścieżki powoduje powstanie drzewa niezrównoważonego (rys. 8.40b), a równowagę przywraca jedna lewa rotacja (rys. 8.40c).

Rys. 8.40. Przykład wstawienia nowego węzła (b) do drzewa AVL (a), wymagającego jednej rotacji (c) do przywrócenia równowagi
Usuwanie może być bardziej czasochłonne niż wstawianie. Najpierw usuwamy węzeł, stosując procedurę delete_by_copying () . Pozwoli nam to sprowadzić problem usunięcia węzła z dwoma synami do problemu usunięcia węzła z co najwyżej jednym synem.


215

Po usunięciu węzła z drzewa uaktualnia się współczynniki wyważenia od ojca usuniętego węzła w górę do korzenia. Dla każdego węzła na tej ścieżce, którego współczynnik wyważenia staje się równy ą2, trzeba wykonać pojedynczą lub podwójną rotację w celu przywrócenia równowagi jego poddrzewa. Co jest istotne, równoważenie nie kończy się po znalezieniu pierwszego węzła o niedopuszczalnym współczynniku wyważenia, jak przy wstawianiu. Oznacza to także, że usuwanie może prowadzić do co najwyżej O(lg n) rotacji, bo w najgorszym przypadku każdy wierzchołek na ścieżce od usuniętego węzła do korzenia może potrzebować równoważenia.
Usunięcie węzła nie musi powodować natychmiastowej rotacji, ponieważ może poprawić współczynnik wyważenia jego ojca (zmieniając go z ą1 na 0), ale może też pogorszyć współczynnik wy ważenia jego dziadka (zmieniając go z ą1 na ą2). Zilustrujemy jedynie te sytuacje, w których jest potrzebna natychmiastowa rotacja. Są cztery takie przypadki (plus cztery symetryczne). W każdym z nich zakładamy, że jest usuwany lewy syn węzła P.
W pierwszym przypadku drzewo z rysunku 8.41 a zmienia się w drzewo na rysunku 8.41 b. Drzewo jest równoważone za pomocą rotacji węzła Q względem P (rys. 8.41c). W drugim przypadku jest potrzebna taka sama rotacja (rys. 8.41d-f). Trzeci przypadek jest bardziej skomplikowany: najpierw jest wykonywana rotacja R względem <2, a potem względem P (rys. 8.41 g-i). Czwarty przypadek jest bardzo podobny do trzeciego i wymaga tych samych dwóch rotacji. Różnicę stanowi współczynnik

Rys. 8.41. Równoważenie drzewa AVL po usunięciu węzła

216

wyważenia węzła R, wynoszący -1, to znaczy, że lewe poddrzewo jest wyższe niż prawe. Po obydwu rotacjach współczynnik wyważenia węzła P wynosi -1, a współczynnik węzła Q jest równy 0.
Z powyższej analizy wynika, że przy wstawianiu i usuwaniu trzeba wykonywać co najwyżej 1,44 lg(n + 2) porównań. Oprócz tego przy wstawianiu może być potrzebna jedna pojedyncza lub podwójna rotacja, a przy usuwaniu w najgorszym przypadku 1,44 lg(n+2) rotacji. Wiemy też jednak, że w przypadku średnim potrzeba IgOO + 0,25 porównań, co redukuje liczbę rotacji przy usuwaniu do tej właśnie wartości. Załóżmy na wszelki wypadek, że wstawianie w przypadku średnim wymaga jednej pojedynczej lub podwójnej rotacji. Eksperymenty wykazują, że usuwanie w 78% przypadków wcale nie wymaga równoważenia. Z drugiej strony tylko 53% wstawień nie wytrąca drzewa z równowagi [16]. Tak więc bardziej czasochłonne usuwanie zdarza się rzadziej niż wstawianie, co nie zagraża zbytnio efektywności równoważenia drzew AVL.
Drzewa AVL można uogólnić, dopuszczając różnicę wysokości Delta > 1 [15]. Nie jest zaskakujące, że wysokość w najgorszym przypadku rośnie wraz z Delta i wynosi

h= {1,81lg(n)-0,71, gdy Delta = 2; 2,15lg(n)-1,13, gdy Delta = 3

Jak pokazują eksperymenty, średnia liczba odwiedzanych węzłów wzrasta o połowę w stosunku do zwykłych drzew AVL (Delta=1), ale liczba operacji potrzebnych do przebudowy drzewa może się zmniejszyć 10-krotnie.

8.8, Samokorygujące się drzewa

Główną troską przy równoważeniu drzew jest niedopuszczenie do ich przechylenia i umożliwianie powstawania liści tylko na jednym lub dwóch poziomach. Dlatego, jeśli nowo przybyły element naruszał równowagę drzewa, powodując powstanie liścia na niedozwolonej pozycji, odstępstwo to było natychmiast korygowane przez lokalną przebudowę drzewa (metoda AVL) albo przez utworzenie drzewa na nowo (metoda DSW). Możemy się jednak zastanowić, czy taka przebudowa jest zawsze niezbędna. Drzew poszukiwań binarnych używa się do szybkiego wstawiania, wyszukiwania oraz usuwania elementów i właśnie szybkość wykonywania tych operacji, a nie kształt drzewa, jest tu celem. Efektywność można poprawić, równoważąc drzewo, ale nie jest to jedyna możliwa metoda.
Inne podejście opiera się na spostrzeżeniu, że nie wszystkie elementy są wykorzystywane z jednakową częstością. Jeśli na przykład do elementu z dziesiątego poziomu drzewa odwołujemy się rzadko, to dostęp do tego poziomu nie spowalnia znacząco całego programu. Jeśli jednak bez przerwy następują odwołania do tego samego elementu, dużą różnicę stanowi to, czy znajduje się on na dziesiątym poziomie czy też blisko korzenia. Z tego powodu strategia przyjęta w samokorygujących się drzewach polega na przebudowywaniu drzew przez przesuwanie w górę drzewa










217

węzłów częściej używanych, co tworzy coś w rodzaju ,,drzewa priorytetowego". Częstość dostępu do węzłów można wyznaczać na wiele sposobów. Każdy węzeł może zawierać pole z licznikiem zapamiętującym, ile razy węzeł był wykorzystywany przy różnych operacjach. Drzewo można później przejrzeć w celu przesunięcia węzłów o największej liczbie odwołań w kierunku korzenia. W mniej wyrafinowanej metodzie zakłada się, że jeśli sięgnięto po jakiś element, to jest duża szansa, że wkrótce sięgnie się po niego ponownie. Jest on więc przesuwany w górę drzewa. Nowych elementów nigdzie się nie przestawia. Założenie to może czasem faworyzować elementy, do których sięga się sporadycznie, ale ogólną tendencją jest przesuwanie się w górę elementów o dużej częstości dostępu; większość z nich będzie zajmowała kilka pierwszych poziomów drzewa.
8.8.1 Samoorganizujące się drzewa
Strategia zaproponowana przez Allena, Munro i Bitnera obejmuje dwie możliwości:
1. Pojedynczą rotację - wykonanie rotacji węzła, do którego sięgnięto (jeśli nie jest to korzeń) względem jego ojca (rys.Rys. 8.42.)

Rys. 8.42. Przekształcenie drzewa za pomocą pojedynczej rotacji (a) lub przesunięcia do korzenia przy dostępie do węzła R (b)

2. Przesuwanie do korzenia - powtarzanie rotacji syna względem ojca dopóty, dopóki element, do którego sięgnięto, nie stanie się korzeniem (rys. 8.42b).

Jeśli użyjemy strategii pojedynczej rotacji, to często odwiedzane elementy znajdą się w końcu w pobliżu korzenia, więc późniejsze do nich dostępy będą szybsze niż poprzednie. Strategia przesuwania do korzenia zakłada, że właśnie odwiedzony element będzie z dużym prawdopodobieństwem odwiedzony ponownie, dlatego wędruje od razu do korzenia. Nawet jeśli nie zostanie od razu znowu odwiedzony, pozostanie niedaleko korzenia. Strategie te jednak nie działają najlepiej w nie sprzyjających sytuacjach, kiedy drzewo binarne przypomina raczej listę niż drzewo, jak na rysunku 8.43. Tutaj kształt drzewa poprawia się powoli, co może mieć ujemny wpływ na czas dostępu do elementów leżących daleko od korzenia.

























218

Rys. 8.43. Przesuwanie elementu T do korzenia (a-e), a następnie przesuwanie elementu S do korzenia (e-i)

8.8.2. Rozchylanie

Modyfikacja strategii przesuwania do korzenia, zwana rozchylaniem (ang. splaying), polega na wykonywaniu parami pojedynczych rotacji w kolejności zależnej od połączeń między synem, ojcem i dziadkiem [21]. Rozróżniamy trzy przypadki w zależności od relacji między odwiedzanym węzłem R, jego ojcem Q i dziadkiem P (jeśli istnieje).

Przypadek 1: Ojciec węzła R jest korzeniem.

Przypadek 2: Konfiguracja jednorodna - węzeł R jest lewym synem swego ojca Q, a Q jest lewym synem swego ojca P albo R i Q są obydwa prawymi synami.

Przypadek 3: Konfiguracja niejednorodna - węzeł R jest prawym synem swego ojca Q, a Q jest lewym synem swego ojca P albo R jest lewym synem Q, a Q jest prawym synem P.


























219

Algorytm przesuwania odwiedzonego węzła R do korzenia drzewa jest następujący:

while R nie jest korzeniem
if ojciec R jest korzeniem
wykonaj pojedyncze rozchylenie: rotację R względem
jego ojca (rys. 8.44a) ;
else i f R jest w konfiguracji jednorodnej ze swoimi poprzednikami
wykonaj jednorodne rozchylenie: najpierw rotację
Q względem P, a potem R względem Q (rys. 8.44b);
else /* R jest w konfiguracji niejednorodnej ze swoimi
poprzednikami */
wykonaj niejednorodne rozchylenie: najpierw rotację
R względem Q, a potem względem P (rys. 8.44c);

Rys. 8.44. Przykłady rozchylania

Różnicę w działaniu tej i poprzedniej metody przekształcania drzewa ilustruje rysunek 8.45, na którym w drzewie z rysunku 8.43a sięgamy do elementu 7, leżącego














220

na poziomie piątym. Kształt drzewa natychmiast się poprawił. Teraz odwiedzamy element R (rys. 8.45c) i kształt drzewa staje się jeszcze lepszy (rys. 8.45d).
Chociaż rozchylanie jest połączeniem dwóch rotacji (z wyjątkiem bezpośredniego sąsiedztwa korzenia), rotacje te nie zawsze są wykonywane od dołu do góry, jak w samoorganizujących się drzewach. W przypadku jednorodnym (lewy-lewy albo prawy-prawy) najpierw dokonuje się rotacja ojca i dziadka odwiedzonego węzła, a dopiero potem węzła i jego ojca. Daje to efekt przesunięcia elementu do korzenia i zmniejszenia wysokości drzewa, co ma pozytywny wpływ na późniejsze operacje odwiedzania węzłów.
Liczba rotacji może się wydawać zbyt duża i na pewno byłaby taka, gdyby za każdym razem odwiedzany element był akurat liściem. Dla liścia czas dostępu wynosiłby zazwyczaj O(lgn), oprócz pewnej liczby odwiedzin na początku, kiedy drzewo nie byłoby zrównoważone. Sięganie do elementów bliskich korzenia czyni jednak drzewo niezrównoważonym. Gdyby na przykład w drzewie na rysunku 8.43a stale sięgać do lewego syna korzenia, drzewo znowu w końcu przypominałoby listę, tym razem ciągnącą się w prawo. Rozchylanie jest zatem strategią skupiającą się raczej na samych elementach niż na kształcie drzewa. Może ona sprawować się dobrze w sytuacji, kiedy niektóre elementy są wykorzystywane znacznie częściej niż inne. Jeśli elementy w pobliżu korzenia są odwiedzane mniej więcej równie często co elementy na najniższych poziomach, to rozchylanie nie musi być najlepszym wyborem. Wtedy lepsza będzie strategia, w której kładzie się nacisk raczej na równoważenie drzewa, a nie na częstość odwiedzania węzłów; praktyczniejszą opcją jest modyfikacja metody rozchylania.
Półrozchylanie (ang. semisplaying) jest odmianą rozchylania, w której wykonuje się tylko jedną rotację w przypadku jednorodnym i kontynuuje rozchylanie z ojcem odwiedzonego węzła, zamiast z samym węzłem. Ilustruje to rysunek 8.44b. Po odwiedzeniu R jest wykonywana rotacja jego ojca Q względem P i operacja jest kontynuowana dla węzła Q, a nie R. Rotacja R względem 2, która występowałaby przy zwykłym rozchylaniu, nie zostanie wykonana.
Rys. 8.45. Przekształcanie drzewa przez rozchylanie po sięgnięciu do węzła T(a-c), a później R (c-d)













221

Rys. 8.46. Odwiedzenie węzła T i przekształcenie drzewa przez półrozchylanie (a-c); ponowne odwiedzenie T(c-d)

Zalety półrozchylania można zobaczyć na rysunku 8.46. Wydłużone drzewo z rysunku 8.43a staje się bardziej zrównoważone dzięki wykonaniu półrozchylenia po odwiedzeniu węzła T (rys. 8.45a-c), a po ponownym odwiedzeniu T drzewo ma w zasadzie tę samą liczbę poziomów. (Mogłoby mieć jeden poziom więcej, gdyby E albo F było drzewem wyższym niż któreś z poddrzew A, B, C lub Z)). Implementacja strategii półrozchylania została zawarta w przykładzie na końcu tego rozdziału.

8,9. Kopce

Szczególny rodzaj drzewa binarnego, zwany kopcem (ang. heap), ma dwie charakterystyczne własności:
1. Wartość w każdym wężle jest nie mniejsza niż wartości przechowywane w jego synach.
2. Wszystkie liście w drzewie leżą na co najwyżej dwóch sąsiednich poziomach, a liście na ostatnim poziomie szczelnie wypełniają jego lewą część.
Te dwie własności definiują kopiec ze względu na maksimum. Jeśli słowo "mniejsza" w pierwszym punkcie zastąpimy słowem "większa", to definicja będzie określać kopiec ze względu na minimum. Oznacza to, że korzeń kopca ze względu na maksimum zawiera największy element, a w korzeniu kopca ze względu na minimum znajduje się element najmniejszy. Drzewo ma własność kopca, jeśli każdy jego węzeł nie będący liściem zachowuje pierwszą własność.
Wszystkie drzewa na rysunku 8.47a są kopcami, drzewa na rysunku 8.47b naruszają pierwszą własność, a te z rysunku 8.47c - drugą.
Interesujące jest to, że kopce można zaimplementować za pomocą tablic. Na przykład tablica data =[2 8 6 1 10 15 3 12 11] może reprezentować drzewo z rysunku 8.48, nie będące kopcem. Elementy umieszczane na kolejnych pozycjach

222

Rys. 8.47. Przykłady kopców (a) i drzew nie będących kopcami (b-c)

reprezentują węzły drzewa od góry do dołu, a na każdym poziomie od lewej do prawej. Druga własność odzwierciedla fakt, że tablica jest szczelnie wypełniona, nie zawiera luk. Możemy teraz zdefiniować kopiec jako tablicę heap długości /?, w której

heap[i] > heap[2*i+1]

oraz

heap[i] > heap[2*i+2]

dlaO<=i<[n/2]

Ze względu na drugą własność liczba poziomów w drzewie będzie O(lg n).

Rys. 8.48. Tablica [2 8 6 1 10 15 3 12 11] traktowana jako drzewo

223

Elementy w kopcu nie są całkowicie uporządkowane. Wiadomo tylko, że największy element znajduje się w korzeniu i że dla każdego węzła wartości jego potomków są mniejsze bądź równe jego wartości. Natomiast relacja pomiędzy braćmi, czy też, trzymając się terminologii pokrewieństwa, pomiędzy stryjem a bratankiem nie jest określona. Uporządkowanie elementów zachowuje prostą linię pochodzenia, nie zważając na poboczne. Z tego względu wszystkie drzewa na rysunku 8.49 są poprawnymi kopcami, chociaż kopiec na rysunku 8.49b jest najlepiej uporządkowany.

Rys. 8.49. Różne kopce zbudowane z tych samych elementów

Kopiec jest wyśmienitym sposobem implementacji kolejki priorytetowej. W rozdziale 6 używaliśmy do tego celu list, a złożoność takiego ich zastosowania wynosiła O(n) lub O(sqr n). Dla dużych n może to być zbyt nieefektywne rozwiązanie. Kopiec jest drzewem doskonale zrównoważonym, zatem dotarcie do liścia wymaga O(lg n) porównań (Nie oznacza to, że w kopcu można wyszukiwać w czasie logarytmicznym (przyp. tłum.)). Taka efektywność wygląda bardzo obiecująco. Dlatego właśnie użyjemy kopca do realizacji kolejki priorytetowej. Trzeba w tym celu zaimplementować dwie procedury: wstawiania i usuwania elementu maksymalnego z kolejki priorytetowej.
Aby wstawić nowy element, kładziemy go na koniec kopca jako ostatni liść. Do drzewa na rysunku 8.50a dodajemy na przykład liczbę 15 jako kolejny liść (rys. 8.50b), co psuje własność kopca tego drzewa. Aby ją przywrócić, liczbę 15 trzeba przesuwać w górę drzewa dopóty, dopóki nie dojdzie do korzenia albo nie natrafi na ojca o wartości nie mniejszej niż 15. W naszym przykładzie zachodzi ten drugi przypadek i węzeł 15 przesuwa się w górę tylko dwa razy, nie osiągając korzenia. Przywrócenie własności kopca w przypadku wstawiania osiąga się, poprawiając ścieżkę od ostatniego liścia w kierunku korzenia.
Algorytm wstawiania jest następujący:

HeapEnąueue(Q,el)
umieść el na końcu Q;
while el nie jest korzeniem i el > ojciec el
zamień el z jego ojcem;
















224

Rys. 8.50. Wstawianie elementu do kopca

Rys. 8.51. Usuwanie elementu maksymalnego z kopca

Usunięcie elementu maksymalnego z kopca polega na usunięciu korzenia, ponieważ na mocy własności kopca to on jest elementem o największym priorytecie. Następnie na jego miejscu jest umieszczany ostatni liść i niemal na pewno trzeba przywrócić własność kopca, tym razem idąc od korzenia w dół drzewa. Z kopca na



225

rysunku 8.51 a jest na przykład usuwane 20, a na jego miejsce wchodzi 6 (rys. 8.51 b) W celu przywrócenia własności kopca 6 jest zamieniane najpierw z większym z( swoich synów, węzłem 15 (rys. 8.51c), a potem znowu z większym z synów, czyli \L (rys. 8.51d).
Algorytm usuwania wygląda następująco:

HeapDeąueue(Q)
usuń element z korzenia;
wstaw na jego miejsce element z ostatniego liścia;
usuń ostatni liść;
/* oba poddrzewa korzenia są kopcami */
p = korzeni;
while p nie jest liściem i p < obaj synowie
zamień p z większym z synów;

Trzy ostatnie wiersze tej procedury można potraktować jako oddzielny algorytrr przywracający własność kopca, jeśli została naruszona przez korzeń drzewa. W te sytuacji element z korzenia jest przesuwany w dół drzewa dopóty, dopóki nie znajdzk się na właściwej pozycji. Jedna z możliwych implementacji tego algorytmu, stanowiącego podstawę metody sortowania za pomocą kopca i omawianego dokładniej w dal szej części książki, jest przedstawiona na rysunku 8.52.

move_down (int data[], int first, int last)
{ int largest = 2*first+1;

while (largest <= last) {

/* NP: Wszystkie węzły w drzewie o korzeniu first, z wyjątkiem samego
węzła "first", spełniają własność kopca. |
Zmienna largest to albo 2*first+1, albo last+1.
Jeśli largest jest równe last+1, to węzeł "first" spełnia własność kopca. */
if (largest < last) /* węzeł data[first] ma dwóch synów */
/* (na pozycjach 2*first+l i 2*first+2) */
if (data[largest] < data[largest+lj)
/* wybierz większego z synów */
largest++;

/* jeśli trzeba, zamień wartości i idź w dół */

if (data[first] < data[largest]) {
swap(data+first, data+largest);
first = largest;
largest =2*first+1;
}
else largest = last+1; /* w celu wyjścia z pętli : węzeł data[f irst] */
} /* nie narusza własności kopca */
>

Rys. 8.52. Implementacja algorytmu przesuwania elementu z korzenia w dół drzewa


226

Aby sprawdzić, że niezmiennik pętli jest poprawny, załóżmy, że początkowo we wszystkich węzłach drzewa, oprócz f irst, jest spełniona własność kopca i przyjmujemy largest równe 2*f irst+1. Jeśli zmienna largest jest równa last+1, to f irst spełnia warunek kopca, ponieważ skoro 2 *f irst+1 = last+1, to first nie ma synów. Jeśli pętla jest wykonywana, to first jest zamieniany z większym ze swoich dwóch synów, zatem własność kopca zostaje przywrócona w węźle first, ale może ją teraz naruszać jego syn largest. Ponieważ f irst staje się teraz równy largest, wszystkie węzły, oprócz first, zachowują własność kopca. Z tekstu procedury jasno widać, że largest przyjmuje wartość 2 *first+1 albo last+1. Zmienna largest może stać się równa last+1, jeśli zachodzi zależność data[first] < data[largest], a nowa wartość węzła first nie ma synów, albo jeśli data[first] > data[largest]. W obu przypadkach w węźle first zostaje przywrócona wartość kopca. Kiedy wreszcie pętla się kończy, largest jest równe last+1, zatem własność kopca musi zachodzić dla wszystkich węzłów w drzewie.

8.10. Notacja polska j drzewa wyrażeń

Jednym z zastosowań drzew binarnych jest jednoznaczna reprezentacja wyrażeń arytmetycznych, relacyjnych lub logicznych. Na początku lat dwudziestych naszego wieku polski logik Jan Łukasiewicz wprowadził specjalną notację w rachunku zdań, umożliwiającą wyeliminowanie nawiasów z zapisu formuł. Notacja Łukasiewicza, zwana notacją polską, daje jednak mniej czytelne formuły niż ich wyposażone w nawiasy odpowiedniki i nie była powszechnie stosowana. Okazała się natomiast użyteczna po pojawieniu się komputerów, szczególnie przy pisaniu kompilatorów i interpretatorów.
Aby zachować czytelność i uniknąć niejednoznaczności formuł, trzeba używać dodatkowych symboli, takich jak nawiasy. Jeśli jednak uniknięcie niejednoznaczności jest jedynym celem, to symboli tych można się pozbyć za cenę zmiany kolejności części składowych formuł. Dokładnie to robi kompilator. Pomija on wszystko, co nie jest istotne dla odczytania właściwego znaczenia formuł, ignorując wszelkie "składniowe ozdobniki".
Jak wygląda ta notacja? Przyjrzyjmy się najpierw poniższemu przykładowi. Jaka jest wartość wyrażenia algebraicznego

2-3*4 + 5?

Wynik zależy od kolejności, w jakiej są wykonywane operacje. Jeśli najpierw wykonamy mnożenie, potem odejmowanie i dodawanie, to wynikiem będzie -5, tak jak oczekiwaliśmy. Jeśli zaczniemy od odejmowania, a następnie wykonamy dodawanie i mnożenie, jak w zapisie

(2-3)* (4 + 5),
to wynikiem będzie -9. Jeśli zaś odejmowanie nastąpi po mnożeniu i dodawaniu, jak w zapisie

227

2-(3*4+5),

to otrzymamy -15. Kiedy widzimy pierwsze wyrażenie, wiemy w jakiej kolejności je wykonywać. Komputer jednak nie wie, że w takiej sytuacji mnożenie ma pierwszeństwo przed dodawaniem i odejmowaniem. Jeśli chcemy to pierwszeństwo uchylić, to potrzebne są nawiasy.
Kompilatory muszą generować kod maszynowy, w którym jest wykonywana jedna operacja na jeden raz, a wynik jest zachowywany do użycia w innych operacjach. Dlatego wszystkie wyrażenia muszą być jednoznacznie podzielone na pojedyncze operacje, a te trzeba ustawić we właściwej kolejności. Tu właśnie przydaje się notacja polska. Pozwala nam ona na tworzenie drzew wyrażeń, które narzucają porządek wykonywania operacji. Na przykład pierwsze wyrażenie, 2-3*4 + 5, oznaczające to samo co 2-(3*4)+5, byłoby reprezentowane przez drzewo z rysunku 8.53a. Wyrażenia drugie i trzecie odpowiadałyby drzewom na rysunku 8.53b i 8.53c. Teraz jest oczywiste, że zarówno na rysunku 8.53a, jak i 8.53c musimy najpierw pomnożyć 3 przez 4, otrzymując 12. Drzewo na rysunku 8.53a nakazuje następnie odjąć 12 od 2, natomiast to z rysunku 8.53c - dodać do 5. W takiej drzewiastej reprezentacji nie ma żadnej niejednoznaczności. Końcowy rezultat może zostać obliczony dopiero wówczas, gdy poznamy wyniki pośrednie.

a) 2-3*4+5

Preorder; +-2*345
Inorder; 2-3*4+5
Postorder; 234*-5+

b) (2-3)*(4+5)

Preorder; *-23*45
Inorder; 2-3*4+5
Postorder; 23-45+*


c) 2-(3*4+5)

Preorder; -2+*345
Inorder; 2-3*4+5
Postorder; 234*5+-


Rys. 8.53. Przykłady trzech drzew wyrażeń i wyniki ich przechodzenia

Zwróćmy uwagę, że w drzewach nie używamy nawiasów, a mimo to nie pojawia się niejednoznaczność. Możemy sobie radzić z tą beznawiasową sytuacją, dokonując linearyzacji drzewa, to znaczy przekształcając je w wyrażenie za pomocą jakiejś metody przechodzenia drzewa. Trzy metody wchodzące tu w grę to preorder, inorder i postorder. Stosując te metody, otrzymujemy dziewięć wyrażeń pokazanych na rysunku 8.53. Co ciekawe, przejście metodą inorder wszystkich trzech drzew daje ten


228

sam wynik, będący początkowym wyrażeniem, które spowodowało cały kłopot. Oznacza to, że metoda inorder nie jest odpowiednia do generowania jednoznacznego zapisu. Pozostałe dwie metody natomiast są odpowiednie. Dają one różne wyniki dla różnych drzew i dlatego nadają się do tworzenia jednoznacznego zapisu wyrażeń i instrukcji.
Ze względu na ważność owych różnych konwencji jest stosowana specjalna terminologia. Przejście metodą preorder daje zapis w notacji prefiksowej (to właśnie jest notacja polska), metoda inorder tworzy zapis infiksowy, a metoda postorder - zapis postfiksowy (tzw. odwrotna notacja polska). Notacja infiksowa to ta, do której jesteśmy przyzwyczajeni. W tym sposobie zapisu operator jest otoczony przez swoje dwa argumenty. W notacji prefiksowej operator poprzedza argumenty, a w postfiksowej - następuje po nich. Wiele ręcznych kalkulatorów operuje wyrażeniami w notacji postfiksowej. Notacja polska, zwykła lub odwrotna, jest także stosowana w niektórych językach programowania. W języku Form na przykład wykorzystuje się notację postfiksową, a w Lispie i w dużym stopniu w Logo używa się notacji prefiksowej.
8.10.1. Operacje na drzewach wyrażeń
Drzewa binarne można tworzyć na dwa różne sposoby, z góry na dół albo z dołu do góry. Implementując wstawianie, wykorzystywaliśmy pierwsze podejście. W niniejszym podrozdziale zastosujemy drugie podejście, budując drzewa wyrażeń od dołu do góry podczas przeglądania wyrażeń w zapisie infiksowym od lewej do prawej.
Najistotniejszą częścią tego procesu konstrukcji jest zachowanie tej samej kolejności operatorów co w analizowanym wyrażeniu, jak to ilustruje przykład na rysunku 8.53. Jeśli nie dopuszczamy użycia nawiasów, zadanie staje się proste, bo to nawiasy powodują powstanie wielu poziomów zagnieżdżenia w wyrażeniu. Nasz algorytm powinien umieć poradzić sobie z dowolnie głębokim zagnieżdżeniem w wyrażeniu. Naturalnym podejściem jest tutaj implementacja rekurencyjna. Dokonamy modyfikacji interpretatora działającego metodą zejść rekurencyjnych, który omawialiśmy w przykładzie z rozdziału 7, i naszkicujemy program, który na podstawie tej metody konstruuje drzewo wyrażenia.
Jak widać na rysunku 8.53, węzeł zawiera operator albo argument, ten ostatni będący identyfikatorem lub liczbą. Gdyby wszystkie identyfikatory były pojedynczymi znakami, a wszystkie liczby były jednocyfrowe, węzeł można by zadeklarować w języku C jako strukturę o jednym polu przeznaczonym na klucz i dwóch polach wskaźnikowych. W ogólniejszym przypadku, kiedy identyfikatory mogą być napisami, a liczby mogą mieć dwie lub więcej cyfr, możemy także użyć konstrukcji struct, z polem przeznaczonym na typ przechowywanego elementu, napis i dwa pola wskaźnikowe, przy czym pole przeznaczone na napis może służyć również do przechowywania liczby jako ciągu cyfr albo operatora (zob. rys. 8.54). Deklaracja jest następująca:


229

(var2 + n) * (var2 + var\)/5

Rys. 8.54. Drzewo wyrażenia

typedef enum {integer, id, operator} token_type;
struci: tree_type {
token_type type ;
char *key;
struct tree_type *left, right;
};

W wyrażeniach, które będą przetwarzane na drzewa, wykorzystuje się tę samą składnię co w wyrażeniach z przykładu w rozdziale 7. Z tego względu możemy użyć tych samych diagramów składniowych. Przy ich zastosowaniu pseudokod funkcji przetwarzających czynnik i składnik będzie wyglądał następująco (funkcja przetwarzająca wyrażenie ma taką samą strukturę jak funkcja przetwarzająca składnik):

factor(pt1, pt2)
if (key jest liczbą)
return create_node (key, integer, NULL, NULL) ;
if (key jest identyfikatorem)
return create_node(key, id, NULL, NULL);
if (key jest lewym nawiasem ' ( ' )
return expr (ptl, pt2 ) po pominięciu ' ) ' ;

230

term(pt1, pt2)
pl = factor(ptl, pt2) ;
while (key jest równy ' f ' lub ' * ' ) {
oper = key;
p2 = factor(NULL, NULL);
pl=create_node(oper, operator, p1, p2);
}
return pl ;

Drzewiasta struktura wyrażeń świetnie nadaje się do generowania kodu w kompilatorach, co pokazuje poniższy pseudokod:

generate (p)
if (p->key jest liczbą n)
return n;
if (p->key7e.st identyfikatorem x)
return x;
if (p->key ye.st operatorem dodawania)
printf("add" , generate(p->left), generate(p->right));
return new_temporary () ;
}
if (p->l.
.
.

Rys. 8.55. Przekształcenia drzewa dla różniczkowania iloczynu i ilorazu


231

Struktura ta jest również bardzo dogodna do wykonywania innych operacji symbolicznych, takich jak różniczkowanie. Reguły różniczkowania (podane w zadaniach programistycznych w rozdziale 7) są pokazane w formie przekształceń drzew na rysunku 8.55, a jako pseudokod na rysunku 8.56. Parametr p jest tutaj wskaźnikiem do wyrażenia, które ma zostać zróżniczkowane względem zmiennej x.

differentiate (p,x)
if (p jest równy NULL)
return NULL;
if (p->key ./e.Yf identyfikatorem x)
return p z. polem key zmienionym na 1 ;
if (p->key jest innym identyfikatorem]
return p z. polem key zmienionym na 0;
if (p->key jest liczbą)
return p z. polem key zmienionym na 0;
if (p->key jest operatorem dodawania lub odejmowania] {
p->left = differentiate (p->left,x);
p->right = differentiate (p->right,x);
return p;
}
if (p->key jest operatorem mnożenia) {
left = create_node(multiplication,operator,p->left,copy(p->right));
left->right = differentiate (left->right,x);
right =create_node(multiplication,operator,copy(p->left),p->right)
right->left = differentiate (right->left,x);
p->left =left;
p->right = right;
return p z. polem key zmienionym na operator dodawania;
}
if (p->key jest operatorem dzielenia) {
.
.
.

Rys. 8.56. Implementacja reguł różniczkowania iloczynu i ilorazu

Regułę dla dzielenia pozostawiamy jako ćwiczenie.

8.11. Przykład: obliczanie częstości występowania słów
Jednym z narzędzi przy ustalaniu autorstwa tekstu wówczas, gdy tekst nie jest podpisany lub jest przypisywany komu innemu, jest badanie częstości występowania słów. Jeśli wiadomo, że autor A napisał tekst r,, a rozkład częstości słów w analizowanym tekście T2 jest bardzo bliski rozkładowi częstości w T,, to najprawdopodobniej tekst T2 został również napisany przez autora A.

232


Tekst, który posłużył do utworzenia tego drzewa, jest początkiem poematu Johna Miltona, zatytułowanego Lycidas:
Yet once morę, o ye laurels,
and once morę ye myrtles brown,...

Rys. 8.57. Drzewo zbudowane metodą półrozchylania, służące do obliczania częstości występowania słów

Niezależnie od wiarygodności tej metody w studiach nad literaturą, interesuje nas napisanie programu, który przegląda plik tekstowy i oblicza częstości pojawiania się słów w tym pliku. Dla uproszczenia będziemy pomijać znaki przestankowe oraz nie będziemy odróżniać małych i wielkich liter. Zatem wyraz mań's policzymy jako dwa słowa, mań i s, chociaż w rzeczywistości może to być jedno słowo (w dopełniaczu), a nie dwa słowa (skrócona forma od mań is albo mań has). Niektóre formy skrócone będą liczone osobno; na przykład s ze słowa mań's będzie potraktowane jako oddzielny wyraz. Podobnie znaki rozdzielające, występujące w środku słowa, takie jak łącznik, będą powodowały odrębne traktowanie części słowa. Słowo pre-existence na przykład zostanie podzielone na prę i existence. Ze względu na nierozróżnianie małych i wielkich liter słowo Good oznaczające nazwisko w zwrocie Mr. Good zostanie potraktowane jako kolejne wystąpienie wyrazu good. Z kolei słowo Good użyte w zwykłym znaczeniu na początku zdania zostanie poprawnie uwzględnione jako wystąpienie good.
W programie koncentrujemy się nie tyle na językoznawstwie, co na zbudowaniu samokorygujących się drzew poszukiwań binarnych z użyciem techniki półrozchylania. Jeśli natrafiamy w pliku na jakieś słowo po raz pierwszy, wstawiamy je do drzewa. W przeciwnym razie wykonujemy półrozchylanie, zaczynając od węzła odpowiadającego temu słowu.
Kolejnym zagadnieniem jest zapamiętywanie wszystkich poprzedników podczas przeglądania drzewa. Osiąga się to za pomocą tablicy predfJ, której używa się niemal jak stosu. Mówimy "niemal", bo wprawdzie nowe poprzednik! (a raczej wskażniki do nich) są umieszczane na końcu tablicy pred[], jednak do elementów w niej przechowywanych odwołujemy się niekoniecznie usuwając je z końca, ale sięgamy także do elementów leżących przed ostatnim. Można by co prawda wszystko to robić, zdejmując elementy ze stosu, a potem z powrotem nań wkładając, lecz ze względu na efektywność nie zastosujemy takiego sposobu dostępu do elementów tablicy pred[J.
Również z uwagi na efektywność używamy kilku zmiennych globalnych, aby uniknąć przekazywania ich jako parametrów. Szczególnie wyraźnie widać to w funkcji inorder (); funkcja ta wykorzystuje trzy następujące zmienne globalne: FOut, Di f f erentWords i WordCnt. Gdyby przekazywać je jako parametry, musiałyby być umieszczane na stosie programu przy każdym wywołaniu funkcji, a więc tysiące razy dla dużych plików tekstowych.
Na rysunku 8.57 widać strukturę drzewa utworzonego dla krótkiego tekstu, a rysunek 8.58 zawiera kompletny kod programu.



233

_include
_include

struct node_rec {
char *word;
int freq;
struct node_rec *left, *right;
};

typedef struct node_rec *tree_type;

tree_type root -NULL,
pred[100]; /* lista poprzedników */
int parent, /* indeks w tablicy poprzedników */
DifferentWords =0 /* licznik różnych słów w pliku tekstowym */
WordCnt = O; ; /* licznik wszystkich słów w tym pliku */

_tdefine UpdateGrandparentOrRoot { if (i > 0) /* jeśli Q ma dziadka */ \
if (pred[i-1]->right == pred[i]) \
pred[i-1]->right = Q; \
else pred[i-1]->left = Q; \
else root = Q; \
parent--; /* dziadek staje się ojcem */\
}
void
RotateR (tree_typeQ, int i)
{
pred[i]->lef t = Q->right;
Q->right = predfi];
UpdateGrandparentOrRoot
}
void
RotateL (tree_typeQ, int i)
{
pred[i]->right = Q->left;
Q->left = pred[i];
UpdateGrandparentOrRoot
}
void
semisplay (tree_typeQ)
{
while (Q != root) {
if (parent == O ) /* jeśli ojciec Q jest korzeniem */
if (pred[0]->left ==Q) RotateR(Q, 0) ;

Rys. 8.58. Implementacja obliczania częstości występowania wyrazów
234

else RotateL(Q, 0) ;
else if (pred[parent]->lef t == Q) /* jeśli Q jest lewym synem
if (pred[parent-1]->lef t -= predfparent]) {
Q = pred[parent] ;
RotateR (predfparent], parent-1) ;
parent-- ;
}
else {
RotateR(Q, parent) ; /* rotacja Q względem jego ojca */
RotateL(Q, parent); /* rotacja Q względem jego nowego ojca */
}
else /* jeśli Q jest prawym synem */
if (pred[parent-l]->right == pred[parent]) {
Q = predfparent] ;
RotateL (predfparent] , parent-1) ;
parent-- ;
}
else { /*
RotateL(Q, parent); rotacja Q względem j ego ojca */
RotateR(Q, parent); /* rotacja Q względem jego nowego ojca */
if (parent == -1) /* uaktualnij korzeń drzewa */
root = Q;
}
}

void
CheckAndlnsert (tree_type *root_addr, char *key)
{ tree_type p - *root_addr, prev = NULL, new_node;
register int v;
parent = -1;
while (p) {
prev = p;
v = strcmp(p->word, key) ;
if (V== Q) { /* jeśli słowo key jest w drzewie */
p->freq++; /* zwiększ jego licznik częstości */
semisplay(p); /* przesuń węzeł w górę */
return; / * i wyjdź z funkcji CheckAndlnsert () * /
}
else if (v > 0)
p = p->left;
else p = p->right ;
pred[++parent] =prev; /* umieść w tablicy predf] */
} /* węzeł prev, ojca p */
if ( ! (new_node = (tree_type) malloc (sizeof(struct node_rec)))) {
printf ( " Brak pamięci na nowe węzły\n " ) ;
exit(1);
} /* utwórz węzeł dla nowego */

Rys. 8.58. Implementacja obliczania częstości występowania wyrazów (cd.)
235
new_node->left = new_node->right =NULL; /* słowa z pliku i */
new_node->freq = 1; /* zainicjuj jego pola */
if (!(new_node->word = (char*) malloc(strlen(key)+1))) {
printf ( "Brak pamięci na nowe słowa\n" ) ;
exit(1);
}
strcpy(new_node->word, key);
if ( ! *root_addr) /* jeśli drzewo jest puste */
*root_addr = new_node;
else if (v > 0)
prev->left - new_node;
else prev->right = new_node;
}
void
inorder (tree_type p, FILE *FOut) /* przepisz wszystkie słowa z drzewa */
{ /* do pliku wyjściowego w porządku */
if (p) { /* alfabetycznym */
inorder (p->left, FOut);
fprintf(FOut, " %s %d " , p->word, p->freq) ;
DifferentWords++;
WordCnt += p->freq;
inorder (p->right, FOut};
}
}

main()
{ char filename[15], s[50];
register int ch = !EOF, i;
FILE *FIn, *FOut;

printf ( "Podaj nazwę pliku: " ) ;
gets(filename);
FOut = fopen ("splay.out" , "w");
Fin = fopen (filename, "r");
while (ch != EOF) {
while (ch != EOF && l isalnum (ch = fgetc (Fin) } ) ; /* pomiń znaki nie będące literami */
if (ch== EOF)
break;
for (s[0] = toupper(ch) , i = 0; ch != EOF && isalnum(s[i]) ; i++)
s[i+1] = toupper (ch = f getc (Fin) ) ;
s[i] = '\0' ;
CheckAndlnsert(&root,s);
}
inorder(root, FOut);
fprintf ( "Plik %s zawiera %d słów, w tym %d różnych" ,
filename, WordCnt, DifferentWords) ;
fclose(Fin) ;
fclose(FOut);
}

Rys. 8.58. Implementacja obliczania częstości występowania wyrazów (cd.)



236

8.12. Ćwiczenia

1. Procedury searchl () i search2 (), opisane w podrozdziale 8.3, nadają się do wyszukiwania jedynie w drzewach poszukiwań binarnych. Spróbuj przystosować wszystkie cztery algorytmy przechodzenia drzewa do wyszukiwania w dowolnym drzewie binarnym.

2. Napisz funkcje zliczające liczbę węzłów w drzewie binarnym, liczbę liści, liczbę prawych synów i wysokość drzewa.

3. Napisz funkcję sprawdzającą, czy drzewo binarne jest doskonale zrównoważone.

4. Zaprojektuj algorytm sprawdzania, czy dane drzewo binarne jest drzewem poszukiwań binarnych.

5. Napisz funkcję usuwającą wszystkie liście z drzewa binarnego.

6. Zastosuj procedury preorder (), inorder () i postorder () do drzewa na rysunku 8.59, jeśli funkcja vis i t (p) jest zdefiniowana następująco:

Rys. 8.59. Przykład drzewa poszukiwań binarnych


237

(a) if (p->left && p->key - p->left->key < 2)
p->left->key += 2;

(b) if ( !p->left)
p->right =NULL;

(c) if ( !p->left) {
p->left= (tree_type)malloc(sizeof(struct node_rec));
p->left->key = p->key-1;
}

(d) { tree_type tmp; tmp - p->right;
p->right = p->left; p->left= tmp;

7. Podaj przykład drzewa, którego przejście metodą preorder i inorder daje ten sam ciąg węzłów.
8. Z rysunku 8.53 widać, że przejście metodą inorder różnych drzew może dać ten sam ciąg. Czy jest to także możliwe w przypaku metody preorder lub postorder? Jeśli tak, podaj przykład.
9. Narysuj wszystkie możliwe drzewa poszukiwań binarnych dla trzech elementów A, B i C.
10. Jaka jest minimalna i maksymalna liczba liści w zrównoważonym drzewie wysokości /??
11. Zaprojektuj algorytm tworzenia lustrzanego odbicia drzewa, w którym wszyscy lewi synowie stają się prawymi i na odwrót.
12. Rozważmy operację R, która dla danej metody przechodzenia drzewa t przetwarza węzły w kolejności odwrotnej niż f, oraz operację C, która przetwarza węzły lustrzanego odbicia danego drzewa przy użyciu metody przechodzenia t. Dla trzech metod przechodzenia drzewa - preorder, inorder i postorder - rozstrzygnij, które spośród poniższych dziewięciu równości są prawdziwe:

R(preorder)=C(preorder)
R(preorder)=C(inorder)
R(preorder)=C(postorder)
R(inorder)=C(preorder)
R(inorder)=C(inorder)
R?(inorder)=C(postorder)
R(postorder)=C(preorder)
R(postorder)=C(inorder)
R(postorder)=C(postorder
238

13. (a) Napisz procedurę wypisującą obrócone bokiem drzewo binarne, stosując właściwe wcięcia, jak na rysunku 8.60a. (b) Przystosuj ją do wypisywania obróconego bokiem drzewa z łańcuchem dowiązań; jeśli można, wypisuj klucz następnika, jak na rysunku 8.60b.

Rys. 8.60. Wypisywanie obróconego bokiem (a) drzewa poszukiwań binarnych oraz (b) drzewa z łańcuchem dowiązań
Rys. 8.61. Przykład drzewa z łańcuchem dowiązań

14. Zaprojektuj procedury wstawiania i usuwania węzła z drzewa z łańcuchem dowiązań, w którym dowiązania są umieszczane jedynie w liściach w sposób pokazany na rysunku 8.61.

15. Zastosuj funkcję balance () do liter alfabetu w celu otrzymania drzewa zrównoważonego.

16. Formuła Dpq oznacza tak zwaną alternatywę Sheffera. W roku 1925 J. Łukasiewicz uprościł aksjomat Nicoda, z którego można wyprowadzić wszystkie twier-



239

dzenia rachunku zdań, do postaci DDpDąrDDsDssDDsąDDpsDps. Przekształć aksjomat Nicoda-Łukasiewicza na zawierającą nawiasy formułę w zapisie infik-sowym i zbuduj dla niej drzewo binarne.

17. Napisz program wypisujący zawierające nawiasy wyrażenie w zapisie infikso-wym dla danego drzewa wyrażenia. Nie wypisuj nadmiarowych nawiasów.

18. Zaprojektuj algorytm, który dla danej pary kluczy przejrzy drzewo poszukiwań binarnych i wypisze wszystkie klucze znajdujące się między danymi. Jeśli na przykład klucze w drzewie byłyby nazwiskami, to można by zażądać wypisania wszystkich nazwisk między Drozdek a Simon.

19. W algorytmie Hibbarda [3] usuwania klucza z drzewa poszukiwań binarnych w przypadku, gdy węzeł zawierający klucz ma prawego syna, klucz jest zastępowany najmniejszym kluczem w prawym poddrzewie, w przeciwnym razie jest usuwany węzeł zawierający klucz. Pod jakim względem algorytm Knutha
(delete_by_copying () ) stanowi jego ulepszenie?

20. Które drzewo czterowierzchołkowe stanowi najgorszy przypadek w pierwszej fazie algorytmu DSW (tworzenia linii)? Wykonaj procedurę ręcznie dla tego drzewa.

21. Zdefiniuj drzewo poszukiwań binarnych, korzystając z pojęcia przejścia metodą inorder.

22. Drzewo Fibonacciego można uważać za najgorszy przypadek drzewa AVL, ponieważ ma najmniejszą liczbę węzłów spośród drzew AVL o danej wysokości h. Narysuj drzewa Fibonacciego dla h=1, 2, 3, 4 i uzasadnij nazwę drzewa.

23. Zrównoważone drzewa jednostronne to drzewa AVL, w których dopuszczalne są tylko dwa współczynniki wyważenia: -1 i O albo O i +1 [18]. Jakie jest racjonalne uzasadnienie wprowadzenia takiego typu drzewa?

8.13. Zadania programistyczne

1. Napisz program, który wczytuje wyrażenie arytmetyczne zapisane w notacji prefi-ksowej (polskiej), buduje drzewo wyrażenia, a następnie przechodzi to drzewo, obliczając wyrażenie. Obliczanie powinno się rozpocząć po wprowadzeniu całego wyrażenia.

2. Drzewa binarnego możemy użyć do posortowania n elementów w tablicy data. Najpierw tworzymy pełne drzewo binarne, o liściach na jednym poziomie oraz wysokości h = [lgn}+ 1, i umieszczamy wszystkie elementy tablicy w pierwszych n liściach. W każdym z pozostałych pustych liści zapisujemy wartość E większą niż wszystkie elementy tablicy. Na rysunku 8.62a widać przykład dla data = {8, 20, 41, 7, 2}, h=[lg(5)]+1 i E=42. Następnie, zaczynając od dołu drzewa, przypisujemy każdemu węzłowi minimum z wartości jego dwóch synów, jak na rysunku 8.62b, tak że najmniejszy element w drzewie, e_min, zostanie przypisany korzeniowi. Teraz, dopóki w korzeniu nie znajdzie się element E, wykonujemy pętlę, która w każdym przebiegu umieszcza E w liściu o wartości e_min i zaczynając od dołu,

240

Rys. 8.62. Drzewo binarne użyte do sortowania
przypisuje każdemu węzłowi na ścieżce od tego liścia do korzenia minimum z wartości jego dwóch synów. Na rysunku 8.62c jest pokazane drzewo po jednym przebiegu pętli.
3. Zaimplementuj sterowany za pomocą menu program zarządzający sklepem z oprogramowaniem. Cała informacja o oferowanych programach jest zawarta w pliku software. W jej skład wchodzi nazwa, wersja, liczba egzemplarzy i cena każdego pakietu. Po uruchomieniu program automatycznie tworzy drzewo poszukiwań binarnych, którego każdy węzeł odpowiada jednemu pakietowi oprogramowania, a klucz stanowi nazwa pakietu i numer wersji. Kolejne pole w węźle powinno zawierać pozycję odpowiedniego rekordu w pliku software. Jedyny sposób dostępu do informacji w pliku software prowadzi poprzez to drzewo.


241

Program powinien pozwalać na uaktualnienie pliku i drzewa, kiedy zostaje dostarczony nowy pakiet oprogramowania lub po sprzedaży jakiegoś pakietu. Drzewo jest uaktualniane w zwykły sposób. W pliku software pakiety występują w kolejności ich przybycia; kiedy zostaje dostarczony nowy pakiet, jest umieszczany na końcu pliku. Jeśli pakiet ma już swoje miejsce w drzewie (i w pliku), to jest tylko poprawiane pole oznaczające liczbę egzemplarzy. Kiedy pakiet jest wyprzedany, odpowiadający mu węzeł jest usuwa
ny z drzewa, a pole z liczbą egzemplarzy w pliku zostaje zmienione na 0. Jeśli plik zawiera na przykład następujące rekordy:

Ventura Publisher ; 2.0; 21; 795
Norton Utilities; 5.0; 10; 145
Norton Utilities ; 5.5; 6; 195
Exp ; 1.0; 19; 195
Exp ; 2.0; 27; 295

to po sprzedaży 6 kopii Norton Utilities 5.5 zawartością pliku będzie

Ventura Publisher; 2.0; 21; 795
Norton Utilities; 5.0; 10; 145
Norton Utilities; 5.5; O; 195
Exp; 1.0; 19; 195
Exp; 2.0; 27; 295

Jeśli z menu zostanie wybrana opcja zakończenia sesji, to program powinien zrobić porządek w pliku, przesuwając rekordy z końca na pozycje oznaczone liczbą egzemplarzy 0. Powyższy plik na przykład przejdzie w taki:

Yentura Publisher; 2.0; 21; 795
Norton Utilities; 5.0; 10 ; 145
Exp; 2.0; 27; 295
Exp; 1.0; 19; 195

4. Zaimplementuj algorytm tworzenia drzew wyrażeń i różniczkowania wyrażeń, które drzewa te reprezentują. Rozbuduj program tak, by potrafił upraszczać drzewa wyrażeń. Po dwa węzły można na przykład wyeliminować z poddrzew reprezentujących wyrażenia aą0, a*1 czy a/1.

5. Napisz program tworzący skorowidz, który konstruuje drzewo poszukiwań binarnych zawierające wszystkie słowa z pliku tekstowego i zapamiętuje numery wierszy, w których te słowa były użyte. Numery wierszy mają być umieszczane na listach dołączonych do węzłów drzewa. Po przetworzeniu pliku wejściowego program ma wypisać w porządku alfabetycznym wszystkie słowa z pliku wraz z odpowiadającymi im listami numerów wierszy, w których te słowa występują.

6. Wykonaj doświadczenie polegające na naprzemiennym wstawianiu i usuwaniu losowych elementów z losowo utworzonego drzewa poszukiwań binarnych. Zastosuj

242

asymetryczne i symetryczne usuwanie (omówione w tym rozdziale) w obydwu wariantach algorytmu usuwania, spróbuj dokładnie przeplatać usuwanie ze wstawianiem, a także przemieszać te operacje losowo. Daje to cztery różne kombinacje. W celu zapewnienia losowości użyj dwóch różnych generatorów liczb losowych. Prowadzi to do ośmiu kombinacji. Wykonaj je wszystkie dla drzew o rozmiarach 500, 1000, 1500 i 2000. Wydrukuj wyniki i porównaj je z oczekiwaną łączną długością ścieżek (IPL) podaną w tym rozdziale.

7. Każdy rozdział angielskiego podręcznika do nauki łaciny zawiera łacińsko-angiel-ski słowniczek zawierający słowa, które zostały użyte po raz pierwszy w tym rozdziale. Napisz program, który zamieni umieszczony w pliku zbiór takich słowniczków na zbiór słowniczków angielsko-łacińskich. Przyjmij następujące założenia (patrz przykład):

(a) Nazwy rozdziałów są poprzedzone znakiem %.
(b) W jednym wierszu jest tłumaczenie tylko jednego słowa.
(c) Słowo łacińskie jest oddzielone dwukropkiem od swojego angielskiego odpowiednika; jeśli jest więcej niż jeden odpowiednik, to są one oddzielone przecinkami.

Aby wypisać angielskie słowa w porządku alfabetycznym, dla każdego rozdziału utwórz drzewo poszukiwań binarnych zawierające angielskie słowa i listy łacińskich odpowiedników. Każdemu angielskiemu słowu musi odpowiadać tylko jeden węzeł w drzewie. Na przykład dla słowa and ma istnieć tylko jeden węzeł, chociaż pojawia się ono w rozdziale Unit 6 dwukrotnie: ze słowami ac i atąue. Po wykonaniu tych zadań dla danego rozdziału, to znaczy po przepisaniu zawartości drzewa do pliku wyjściowego, należy drzewo wraz ze wszystkimi listami usunąć z pamięci komputera przed utworzeniem drzewa dla następnego rozdziału.
Oto przykład pliku zawierającego słowniczki łacińsko-angielskie:

%Unit 5
ante : before, in front of, previously
antiąuus : ancient
ardeo : burn, be on fire, desire
arma : arms, weapons
aurum : gold
aureus : golden, of gold

%Unit 6

animal : anima1
Athenae : Athens
atque : and
ac : and
aurora : dawn

243

%Unit 7

amo : love
amor : love
annus : year
Asia : Asia

Dla takich danych program nasz powinien utworzyć następujący plik wyjściowy:

%Unit 5

ancient : antiąuus
arms ; armabe on fire : ardeo
before : ante
burn : ardeo
desire : ardeo
goId : aurum
golden : aureus
in front of : ante
of gold : aureus
previously : ante
weapons : arma

%Unit 6

Athens : Athenae
and : ac, atque
animal : anima1
dawn : aurora

%Unit7

Asia : Asia
love : amor, amo
year : annus

Bibliografia
Wstawianie i usuwanie
[1] Culberson J.: The effect of updates in binary search trees. Proceedings ofthe 17 th Annual Symposium on Theory of Computing, 1985, s. 205-212.
[2] Eppinger J.L.: Ań empirical study of insertion and deletion in binary search trees. Communications ofthe ACM, 1983, 26, s. 663-669.

244

[3] Hibbard T.N.: Some combinatorial properties of certain trees with applications to searching
and sorting. Journal of the ACM, 1962, 9, s. 13-28. [4] Jonassen A.T., Knuth D.E.: A trivial algorithm whose analysis isn't. Journal of Computer
and System Sciences, 1978, 16, s. 301-322. [5] Knuth D.E.: Deletions that preserve randomness. IEEE Transactions of Software Engine-
ering, 1977, SE-3, s. 351-359.
Przechodzenie drzewa
[6] Berztiss A.: A taxonomy of binary tree traversals. BIT, 1986, 26, s. 266-276.
[7] Burkhard W.A.: Nonrecursive tree traversal algorithms. Computer Journal, 1975, 18,
s. 227-230. [8] Morris J.M.: Traversing binary trees simply and cheaply. Information Processing Letters,
1979, 9, s. 197-200.
Równoważenie drzew
[9] Baer J.L., Schwab B.: A comparison of tree-balancing algorithms. Communications of the ACM, 1977, 20, s. 322-330.
[10] Chang H., lyengar S.S.: Efficient algorithms to globally balance a binary search tree. Communications of the ACM, 1984, 27, s. 695-702.
[11] Day A.C: Balancing a binary tree. Computer Journal, 1976, 19, s. 360-361.
[12] Martin W.A., Ness D.N: Optimizing binary trees grown with a sorting algorithm. Communications ofthe ACM, 1972, 15, s. 88-93.
[13] Stout Q.F., Warren B.L.: Tree rebałancing in optimal time and space. Communications of the ACM, 1986, 29, s. 902-908.
Drzewa A VL
[14] Adel'son-Vel'skii G.M., Landis E.M.: Ań algorithm for the organization of information.
Soviet Mathematics, 1962, 3, s. 1259-1263. [15] Foster C.C.: A generalization of AVL trees. Communications of the ACM, 1973, 16,
s. 512-517. [16] Karlton P.L., Fuller S.H., Scroggs R.E., Kaehler E.B.: Performance of height-balanced
trees. Communications of the ACM, 1976, 19, s. 23-28. [17] Knuth D.E.: The Art of Computer Programming, Vol. 3: Sorting and Searching. Reading,
MA, Addison-Wesley 1973. [18] Zweben S.H., McDonald M.A.: Ań optimal method for deletion in one-sided height balan-
ced trees. Communications ofthe ACM, 1978, 21, s. 441-445.
Samokorygujące się drzewa
[19] Allen B., Munro L: Self-organizing search trees. Journal ofthe ACM, 1978, 25, s. 526-535. [20] Bitner J.R.: Heuristics that dynamically organize data structures. SIAM Journal of Co/n-
puting, 1979, 8, s. 82-110. [21] Sleator D.D., Tarjan R.E.: Self-adjusting binary search trees. Journal of the ACM, 1985,
32, s. 652-686.