9. Drzewa wyższych rzędów

Na początku poprzedniego rozdziału została podana ogólna definicja drzewa, ale główny nacisk był położony na drzewa binarne, zwłaszcza drzewa poszukiwań binarnych. Drzewo było zdefiniowane jako struktura pusta lub struktura, w której synami korzenia są rozłączne drzewa ?,, ..., tk. Zgodnie z tą definicją każdy węzeł w drzewie tego rodzaju może mieć więcej niż dwóch synów. Jeśli jest ich co najwyżej m, to drzewo takie nazywamy drzewem rzędu m lub m-kierunkowym.
W bardziej użytecznej wersji drzewa wyższego rzędu na klucze umieszczone w każdym węźle jest narzucony porządek. Drzewem poszukiwań rzędu m nazywamy drzewo, w którym:

1. Każdy węzeł ma (co najwyżej) m synów i m-1 kluczy.
2. Klucze w każdym węźle są ułożone w porządku rosnącym.
3. Klucze w pierwszych i poddrzewach węzła są mniejsze niż i-ty klucz.
4. Klucze w ostatnich m-i poddrzewach węzła są większe niż i-ty klucz.

Drzewa poszukiwań rzędu m odgrywają tę samą rolę wśród drzew rzędu m co drzewa poszukiwań binarnych wśród drzew binarnych i są wykorzystywane do tego

Rys. 9.1. Drzewo rzędu 4
#246
samego celu: szybkiego odczytywania i uaktualniania informacji. Podobne są również problemy z nimi związane. Na rysunku 9.1 widać drzewo rzędu 4, w którym dostęp do kluczy może wymagać różnej liczby sprawdzeń dla różnych kluczy: liczbę 35 można znaleźć po sprawdzeniu dwóch węzłów, liczbę 55 znajdziemy dopiero w piątym sprawdzanym wierzchołku. Drzewo to ma zatem znaną już nam wadę: jest niezrównoważone. Problem ten jest szczególnie istotny, jeśli chcemy używać drzew do przetwarzania danych umieszczonych w pamięci zewnętrznej, takiej jak dyski czy taśmy, do której każdy dostęp jest kosztowny. Konstruowanie takich drzew wymaga rozważniejszego podejścia.

9.1. Rodzina B-drzew

Podstawową jednostką w operacjach wejścia-wyjścia związanych z dyskiem jest blok. Kiedy informacja jest odczytywana z dysku, cały zawierający ją blok jest wczytywany do pamięci, a kiedy jest zapisywana na dysk, zapisywany jest również cały blok. Za każdym razem, gdy trzeba sięgnąć do informacji na dysku, należy najpierw ustalić jej położenie na dysku, głowica musi zostać umieszczona nad częścią dysku mieszczącą żądaną informację, a dysk musi zostać wprowadzony w ruch obrotowy tak, by cały blok przechodzący pod głowicą mógł być przeniesiony do pamięci. Oznacza to, że istnieje kilka elementów składających się na czas dostępu do danych:

czas dostępu = czas szukania + bezwładność obrotowa + czas przesyłania

Proces ten jest niesłychanie powolny w porównaniu z przesyłaniem informacji między obszarami pamięci. Pierwszy składnik, czas szukania, jest szczególnie duży, ponieważ zależy od szybkości mechanicznego przemieszczenia głowicy dysku na właściwą ścieżkę. Bezwładność obrotowa to czas potrzebny na umieszczenie głowicy nad właściwym blokiem, a więc średnio na pół obrotu dysku. Na przykład odczytanie 5 KB (kilobajtów) z dysku potrzebującego 40 ms na znalezienie ścieżki, wykonującego 3000 obrotów na minutę i szybkości przesyłania danych 1000 KB/s zajmie w sumie

40 ms + 10 ms + 5 ms - 55 ms

Przykład ten unaocznia, że czas przesyłania informacji na dysk i z dysku mierzy się w milisekundach. Z kolei procesor przetwarza dane w czasie rzędu mikrosekund, to znaczy tysiąc razy szybciej, nanosekund, czyli milion razy szybciej, lub jeszcze szybciej. Widzimy więc, że przetwarzanie informacji przechowywanej w pamięci zewnętrznej może znacząco zmniejszyć szybkość działania programu.
Jeśli program stale korzysta z danych w pamięci zewnętrznej, to jej parametry muszą być wzięte pod uwagę przy projektowaniu programu. Reprezentacja drzewa poszukiwań binarnych może być na przykład rozproszona między wiele różnych bloków na dysku, jak na rysunku 9.2, tak że średnio potrzebny jest dostęp do dwóch bloków. Jeśli drzewo jest w programie używane często, to dostępy te mogą znacząco
#247
spowolnić działanie programu. Wstawianie i usuwanie kluczy w tym drzewie również wymaga wielu odwołań do bloków. Drzewo poszukiwań binarnych, będące bardzo efektywnym narzędziem, jeśli mieści się w całości w pamięci wewnętrznej, okazuje się niedogodne. W kontekście pamięci zewnętrznej jego dobra skądinąd wydajność prawie się nie liczy, ponieważ ciągłe odwołania do bloków na dysku, które ta metoda powoduje, bardzo ową wydajność osłabiają.

Rys. 9.2. Węzły drzewa binarnego mogą się znajdować w różnych blokach na dysku

Lepiej jest odczytać lub zapisać dużą ilość informacji za jednym razem niż skakać od jednego miejsca na dysku do drugiego, przesyłając małe porcje danych. Jeśli na przykład trzeba przesłać 10 KB, to opierając się na podanych wyżej parametrach dysku, widzimy, że

czas dostępu = 40 ms + 10 ms + 10 ms = 60 ms

Jeśli jednak ta sama informacja składa się z dwóch fragmentów po 5 KB, to

czas dostępu = 2 * (40 ms + 10 ms + 5 ms) = 110 ms

a więc jest prawie dwa razy dłuższy niż poprzednio. Powodem jest to, że każdy dostęp do dysku jest bardzo kosztowny; jeśli można, to dane powinny być ujęte w taką strukturę, żeby zminimalizować liczbę dostępów.

9.1.1. B-drzewa

W programach obsługujących bazy danych, gdzie większość informacji jest przechowywana na dyskach lub taśmach, obciążenie czasowe związane z dostępem do pamięci zewnętrznej można znacząco zmniejszyć przez właściwy dobór struktur danych. B-drzewa [2] są jednym z takich rozwiązań.
B-drzewo zostało zaprojektowane z myślą o pamięci zewnętrznej i daje się tak dostosować, by zredukować ograniczenia narzucone przez ten rodzaj pamięci. Ważną cechą B-drzew jest rozmiar węzła, który można uczynić równym rozmiarowi bloku. Liczba kluczy w jednym węźle może się zmieniać w zależności od rozmiarów kluczy,
#248
organizacji danych (czy w węzłach są przechowywane tylko klucze czy całe rekordy?) i oczywiście od rozmiaru bloku. Rozmiar bloku zależy od systemu. Może wynosić 512 B, 4 KB lub więcej; taki sam będzie rozmiar każdego węzła w B-drzewie. Ilość informacji przechowywanych w jednym węźle B-drzewa może więc być dość duża. B-drzewo rzędu m jest drzewem poszukiwań rzędu m o następujących własnościach:

1. Korzeń ma co najmniej dwa poddrzewa, chyba że jest liściem.
2. Każdy węzeł, nie będący liściem ani korzeniem, zawiera k- 1 kluczy i k wskaźników do poddrzew, gdzie [m/2]<=k<=m.
3. Każdy liść zawiera k-1 kluczy, gdzie [m/2]<=k<=m.
4. Wszystkie liście są na tym samym poziomie(W tej definicji rząd B-drzewa określa maksymalną liczbę synów. Czasami węzły w B-drzewie rzędu m definiuje się jako mające k kluczy i k+1 wskaźników, gdzie m
W myśl tej definicji B-drzewo jest zawsze co najmniej w połowie zapełnione, ma niewiele poziomów i jest doskonale zrównoważone.
Węzeł B-drzewa zazwyczaj implementuje się jako strukturę (zob. poniżej) zawierającą (m-1)-elementową tablicę kluczy, m-elementową tablicę wskaźników do innych węzłów oraz ewentualnie dalsze informacje potrzebne do zarządzania drzewem, jak liczbę kluczy w węźle i znacznik określający, czy węzeł jest liściem.

struct BTreeNode {
int leaf : 1;
int KeyTally;
KeyType keys[m-1];
struct BTreeNode *pointers[m];
};

Wartość m jest zwykle duża (50-500), żeby informacja zajmująca jedną stronę lub blok pamięci zewnętrznej mieściła się w jednym węźle. Na rysunku 9.3a widać przykład B-drzewa rzędu 7, zawierającego kody pewnych elementów. W tym drzewie jedynie klucze zasługują na uwagę. Jednak w większości przypadków takie kody byłyby tylko polami w większych strukturach, być może rekordach z wariantami (uniach). W takich sytuacjach tablica keys jest tablicą struktur, z których każda ma identyfikujące ją jednoznacznie pole (jak kod na rys. 9.3a). Struktura na rysunku 9.3b zawiera adres całego rekordu w pamięci zewnętrznej. Jeśli zawartość takiego węzła także mieści się w pamięci zewnętrznej, to każde odwołanie do klucza wymaga dwóch dostępów do pamięci zewnętrznej. Na dłuższą metę jest to lepsze rozwiązanie niż przechowywanie całych rekordów w węzłach, bo w takim wypadku węzły mogłyby pomieścić jedynie bardzo niewielką liczbę rekordów. W efekcie tego B-drzewo miałoby znacznie większą wysokość, a ścieżki poszukiwań byłyby dłuższe niż w B-drzewie z adresami rekordów.
#249
Rys. 9.3. Węzeł B-drzewa rzędu 7 (a) bez odsyłaczy do pliku i (b) z odsyłaczami

Odtąd B-drzewa będą pokazywane w formie skróconej, bez wyraźnego oznaczania liczby kluczy w węźle ani pól wskaźnikowych, jak to widać na rysunku 9.4.

Rys. 9.4. B-drzewo rzędu 5 pokazane w formie skróconej

Wyszukiwanie w B-drzewie

Najgorszy przypadek wyszukiwania zachodzi wtedy, kiedy B-drzewo ma najmniejszą dopuszczalną liczbę wskaźników w każdym węźle nie będącym korzeniem, q = [m/2], a przeglądanie musi zakończyć się w liściu (przy wyszukiwaniu pomyślnym albo zakończonym niepowodzeniem). W tym przypadku w B-drzewie wysokości h występuje
#250
1 klucz w korzeniu +
2(q-1) kluczy na drugim poziomie +
2q(q-1) kluczy na trzecim poziomie +
2q^2(q-1) kluczy na czwartym poziomie +
.
.
.
2qh^(h-2) [(q-1)] kluczy w liściach (poziom h) =
1+[Sigma_i = 0;^h-2(2q^i)](q-1) kluczy w całym B-drzewie

Zgodnie ze wzorem na sumę pierwszych n elementów ciągu geometrycznego

[Sigma_i=0;^n(q^i)] = [q^(n+1)-1]/(q-1)

liczbę kluczy w B-drzewie stanowiącym najgorszy przypadek można wyrazić jako

1+2(q-1)[Sigma_i=0;^h-2(q^i)] = 1+2(q-1) [q^(h+1)-1]/(q-1) = -1+2q^(h-1)

Zależność między liczbą kluczy n w dowolnym B-drzewie a jego wysokością wyraża się zatem jako

n <= -1+2q^(h-1)

Rozwiązując tę nierówność ze względu na wysokość h, otrzymujemy

h <= log_2[(n+1)\(2)+1

Oznacza to, że jeśli rząd m jest dostatecznie duży, wysokość jest mała, nawet dla dużej liczby kluczy przechowywanych w B-drzewie. Jeśli na przykład m = 200, a n = 2000000, to h<=3; w najgorszym przypadku odnalezienie klucza w takim B-drzewie wymaga przejścia przez trzy węzły. Jeśli korzeń może być przez cały czas trzymany w pamięci wewnętrznej, to liczba ta zmniejsza się do zaledwie dwóch odwołań do pamięci zewnętrznej.
Algorytm znajdowania klucza w B-drzewie jest prosty i można go zapisać następująco:

struct BTreeNode *
BtreeSearch (KeyType K, struct BTreeNode *node)
if (node !=NULL) {
for (i=1; i < node->KeyTally && node->keys[i-1] < K; i++);
#251
if (i == node->KeyTally || node->keys[i-1] > K)
return BTreeSearch(K,node->pointers[i-l]);
else return node;
}
else return NULL;
}

Wstawianie klucza do B-drzewa

Realizacja operacji wstawiania i usuwania wydaje się być sporym wyzwaniem, jeśli przypomnimy sobie, że wszystkie liście mają być na ostatnim poziomie. Nawet w zrównoważonych drzewach binarnych nie było takiego wymagania. Implementacja wstawiania stanie się prostsza, jeśli zmienimy strategię budowania drzewa. Kiedy wstawialiśmy węzeł do drzewa poszukiwań binarnych, drzewo było zawsze budowane od góry do dołu, co prowadziło do jego niezrównoważenia. Jeśli pierwszy z napływających kluczy był najmniejszy, to był on umieszczany w korzeniu, który w efekcie nie miał lewego poddrzewa, jeżeli nie przedsięwzięliśmy specjalnych kroków w celu zrównoważenia drzewa.
Drzewo można jednak budować od dołu do góry, tak że zawartość korzenia jest rzeczą płynną i dopiero po wszystkich wstawieniach wiadomo na pewno, co się w nim mieści. Tę właśnie strategię stosuje się przy wstawianiu kluczy do B-drzew. W trakcie tego procesu kierujemy się bezpośrednio do liścia i umieszczamy tam żądany klucz, jeśli jest miejsce. Kiedy liść jest już pełny, tworzony jest nowy liść, klucze są dzielone między te dwa liście, a jeden z kluczy zostaje przeniesiony do ojca. Jeśli ojciec jest także pełny, to proces się powtarza aż do osiągnięcia korzenia i utworzenia nowego korzenia.
Podchodząc do problemu bardziej systematycznie, przy wstawianiu klucza do B-drzewa możemy natrafić na sytuacje trzech rodzajów:
1. Klucz zostaje umieszczony w liściu, w którym jest jeszcze miejsce, jak na rysunku 9.5. W B-drzewie rzędu 5 nowy klucz 7 zostaje umieszczony w liściu przy zachowaniu uporządkowania kluczy, więc klucz 8 trzeba przesunąć o jedną pozycję w prawo.

Rys. 9.5. B-drzewo (a) przed i (b) po wstawieniu liczby 7 do liścia, w którym było jeszcze miejsce

2. Liść, w którym nowy klucz powinien być umieszczony, jest pełny, jak na rysunku 9.6. W tym przypadku liść rozdzielamy na dwa, tworząc nowy liść, a połowę kluczy przenosimy z pełnego liścia do nowego. Nowy liść trzeba jeszcze dołączyć
#252
do B-drzewa. Ostatni klucz starego liścia zostaje przeniesiony do ojca, gdzie również umieszcza się wskaźnik do nowego liścia. Tę samą procedurę można powtórzyć dla każdego węzła wewnętrznego w B-drzewie, a każda operacja rozdzielenia węzła zwiększa liczbę węzłów w drzewie o jeden. Co więcej, węzeł po takiej operacji nie ma nigdy mniej niż [m/2] -1 kluczy.

Rys. 9.6. Wstawienie liczby 6 do pełnego liścia

3. Specjalna sytuacja zachodzi, kiedy korzeń B-drzewa jest pełny. Trzeba wtedy utworzyć nowy korzeń i brata istniejącego korzenia. Taka operacja powoduje dodanie dwóch nowych węzłów do B-drzewa. Na przykład po wstawieniu klucza 13 do trzeciego liścia na rysunku 9.7a liść ten zostaje rozdzielony (jak w przypadku 2) i powstaje nowy liść, a klucz 15 powinien zostać przeniesiony do ojca, w którym jednak nie ma dla niego miejsca (rys. 9.7b). Ojciec zostaje więc rozdzielony (rys. 9.7c), ale teraz trzeba dwa B-drzewa połączyć w jedno. Osiąga się to, tworząc nowy korzeń i przenosząc do niego ostatni klucz ze starego korzenia (rys. 9.7d). Powinno być oczywiste, że jest to jedyny przypadek, w którym B-drzewo zwiększa swoją wysokość. Poniżej przedstawiamy algorytm wstawiania kluczy do B-drzewa.

BTreeInsert(K)
znajdź liść node, do którego trzeba wstawić K ;
while (1)
znajdź właściwe miejsce w tablicy keys na klucz K ;
if węzeł node nie jest pełny
wstaw K i zwiększ KeyTally;
return;
else
rozdziel node na node1 / node2 ; /* node1 = node1, node2 jest nowy; */
#253
rozdziel równo klucze i wskaźniki między node1 /
node2 oraz wypełnij właściwie ich pola KeyTally;
K = ostatni klucz węzła node1 ;
if node był korzeniem
utwórz nowy korzeń jako ojca node1 i node2 ;
umieść K / wskaźniki do node1 i node2 w korzeniu
oraz zapisz w jego polu KeyTally liczbę 1 ;
return;
else node = ojciec węzła node; /* i przetwarzaj teraz ojca węzła node */

Rys. 9.7. Wstawienie liczby 13 do pełnego liścia
#254
Na rysunku 9.8 jest pokazany wzrost B-drzewa rzędu 5 podczas wstawiania nowych kluczy. Zwróćmy uwagę, że przez cały czas drzewo jest doskonale zrównoważone.

a) Wstawienie 8, 14, 2, 15

b) Wstawienie 3

c) Wstawienie 1, 16, 6, 5

d) Wstawienie 27, 37

e) Wstawienie 18,25,7,13,20

f) Wstawienie 22,23,24

Rys. 9.8. Budowanie B-drzewa rzędu 5 za pomocą algorytmu BTreeinsert
#255
W odmianie tej metody wstawiania wykorzystuje się wstępne rozdzielanie: podczas odbywającego się z góry do dołu poszukiwania danego klucza wszystkie odwiedzane węzły, które są już pełne, zostają rozdzielone. Dzięki temu proces rozdzielania nie "wędruje" do góry.
Jak często można się spodziewać konieczności rozdzielania węzłów? Rozdzielenie korzenia B-drzewa powoduje powstanie dwóch nowych węzłów. We wszystkich pozostałych przypadkach rozdzielenie zwiększa liczbę węzłów w B-drzewie tylko o jeden. Podczas konstruowania B-drzewa o p węzłach rozdzielenie węzła trzeba wykonać p-h razy, gdzie h jest wysokością B-drzewa. W B-drzewie o p węzłach jest przynajmniej

1+([m/2]-1)(p-1)

kluczy. Proporcja liczby rozdzieleń do liczby kluczy w B-drzewie dana jest więc wzorem

(p -h)/(1+([m/2]-1)(p-1))

Po podzieleniu licznika i mianownika przez p -h i obserwacji,1/(p-h) ->0, a (p-1)/(p-h) ->1 ze wzrostem p, wnioskujemy, że średnie prawdopodobieństwo rozdzielenia wynosi

1/[m/2]

Przykładowo: dla m = 10 prawdopodobieństwo to jest równe 0,25, dla m- 100 wynosi 0,02, a dla m- 1000 tylko 0,002, co jest zgodne z oczekiwaniem; im większa pojemność jednego węzła, tym rzadziej trzeba węzły rozdzielać.

Usuwanie klucza z B-drzewa

Usuwanie jest w dużej mierze odwrotnością wstawiania, chociaż występuje tu więcej szczególnych przypadków. Trzeba zadbać o to, żeby po usuwaniu żaden węzeł nie był wypełniony mniej niż w połowie. Oznacza to, że czasem pojawia się konieczność sklejenia węzłów.
Przy usuwaniu mamy do czynienia z dwoma głównymi przypadkami: usuwanie klucza z liścia albo z węzła nie będącego liściem. W tym ostatnim przypadku użyjemy procedury podobnej do delete_by_copying (), przeznaczonej dla drzew poszukiwań binarnych (zob. p. 8.6).

1. Usuwanie klucza z liścia
1.1. Jeśli po usunięciu klucza K liść jest przynajmniej w połowie wypełniony, to trzeba tylko przesunąć w lewo klucze większe niż K, aby wypełnić lukę (zob. rys. 9.9a,b). Jest to odwrócenie przypadku 1 operacji wstawiania.
#256
Rys. 9.9. Usuwanie kluczy z B-drzewa
#257
1.2. Jeśli po usunięciu K liczba kluczy w liściu jest mniejsza niż [-m/2]- 1, to powoduje niedobór kluczy.

1.2.1 Jeślnie ma lewego lub prawego brata o liczbie kluczy przekraczającej minimalną [-m/2]- 1, to wszystkie klucze z liścia i jego brata są rozdzielone między te dwa węzły, co polega na przeniesieniu separującego je klucza z ojca do liścia i przeniesieniu jednego klucza z jego brata do ojca.

1.2.2. Jeśli w liściu nastąpił niedobór a liczba kluczy jego braci wynosi [-m/2]- 1, to liść i jego brata trzeba skleić, klucze z liścia jego brata i seperujący je klucz z ojca są umieszczone w liściu a jego brat jest niszczony. Klucze w ojcu są przesuwane, jeśli pojawi się luka. Może to spowodować cały łańcuch operacji, jeśli niedobór wystąpi w ojcu. Ojciec jest teraz traktowany, jakby był liściem i powtarzany jest krok1.2.2., dopuki nie można wykonać kroku 1.2.1., albo nie zostanie osiągnięty korzeń drzewa. Powyższa operacja jest odwróceniem przypadku 2 operacji wstawiania.

1.2.2.1. Szczególny przypadek występuje przy sklejaniu węzła z jego bratem, kiedy ich ojciec jest korzeniem zawierającym tylko jeden klucz. Wtedy klucze z węzła i jego brata wraz z jednym kluczem z korzenia są umieszczone w węźle, który staje się nowym korzeniem, a jego brat i stary korzeń są niszczone. Jest to jedyny przypadek, kiedy znikają dwa węzły za jednym razem. Wysokość drzewa zmniejsza się przy tym o jeden. Jest to odwrócenie przypadku 3 operacji wstawiania.

2. Usuwanie klucza nie będącego liściem.
Może to prowadzić do problemów z przebudową drzewa. Dlatego przypadek taki sprowadza się do usuwania klucza z liścia. Klucz do usunięcia jest zastępowany swoim bezpośrednim następnikiem(lub poprzednikiem), który musi znajdować się w liściu. Następnik jest usuwany z liścia jak w przypadku 1.

Oto algorytm usuwania klucza B-drzewa.

BTreeDelete (K)
node =BTreeSearch (K , root) ;
if (node ! = NULL)
if węzeł node jest liściem
znajdź liść zawierający najbliższy następnik S klucza K;
skopiuj S w miejsce K w węźle node ;
node = liść zawierający S;
usuń S z węzła node;
else usuń K z węzła node ;
while (1)
if w węźle node nie ma niedoboru
return;
else if istnieie brat węzła node z wystarczającą liczbą kluczy
rozdziel klucze między node i jego brata;
return;
#258
else if ojciec węzła node jest korzeniem
if ojciec ma tylko jeden klucz
sklej węzeł node, jego brata i ojca, tworząc nowy korzeń;
else sklej węzeł node i jego brata;
return;
else sklej węzeł node i jego brata;
node = ojciec węzła node ;

Z definicji B-drzew wynika, że są one wypełnione w co najmniej 50%, może się więc zdarzyć, że 50% miejsca się w nich marnuje. Jak często to się zdarza? Jeśli zbyt często, to trzeba ponownie przemyśleć tę definicję lub nałożyć na B-drzewa pewne dodatkowe ograniczenia. Analizy i symulacje wykazują jednak, że po dużej liczbie losowych wstawień i usunięć B-drzewo jest wypełnione w około 69% [13], a późniejsze zmiany w proporcji zajętego miejsca są już bardzo niewielkie. To, że B-drzewo będzie wypełnione całkowicie, jest również bardzo mało prawdopodobne, celowe więc będzie przyjęcie dodatkowych warunków.

9.1.2. B*-drzewa

Ponieważ każdy węzeł w B-drzewie reprezentuje blok pamięci zewnętrznej, dostęp do jednego węzła oznacza jedno odwołanie do pamięci zewnętrznej, kosztowne w porównaniu z dostępem do kluczy w węźle mieszczącym się w pamięci podstawowej. Dlatego im mniej tworzy się węzłów, tym lepiej. W najgorszym przypadku węzły B-drzewa mogą być wypełnione jedynie w połowie, zanim zaczniemy rozdzielać węzły; można by się więc upewnić, czy nie ma węzłów wykorzystanych tylko połowicznie.

Rys.9.10. Z nadmiarem w B*-drzewie radzimy sobie, przemieszczając klucze między węzłem, w którym on wystąpił, a jego bratem
#259
B*-drzewo jest odmianą B-drzewa wprowadzoną przez Donalda Knutha, a nazwaną tak przez Douglasa Comera. W B*-drzewie wszystkie węzły z wyjątkiem korzenia muszą być wypełnione przynajmniej w dwóch trzecich, a nie tylko w połowie, jak w zwykłym B-drzewie. Dokładniej, liczba kluczy w nie będącym korzeniem węźle B*-drzewa rzędu m może być równa k dla
[(2m-1)/(3)]<=k<=m-1. Częstość rozdzielania węzłów zmniejszamy, opóźniając operację rozdzielenia, a w odpowiednim momencie rozdzielając dwa węzły na trzy zamiast jednego na dwa.
Operację rozdzielenia w B*-drzewie opóźnia się, próbując przemieszczać klucze między węzłem a jego bratem, kiedy w węźle występuje nadmiar. Na rysunku 9.10 widać przykład B+-drzewa rzędu 9. Klucz 6 ma być wstawiony do lewego, pełnego już węzła. Zamiast rozbijać węzeł, wszystkie klucze z niego i z jego brata są równo dzielone, a klucz środkowy, 10, jest umieszczany w ojcu. Zwróćmy uwagę, że równo zostały podzielone nie tylko klucze, ale i wolne miejsca, dzięki czemu węzeł, który był przepełniony, może teraz pomieścić jeszcze jeden klucz.
Jeśli brat pełnego węzła jest także pełny, to trzeba wykonać operację rozdzielenia: tworzy się jeden nowy węzeł, klucze z węzła i jego brata (wraz z rozdzielającym je kluczem z ojca) są równo dzielone między trzy węzły, a dwa oddzielające je klucze są umieszczane w ojcu (zob. rys. 9.11). Wszystkie trzy węzły biorące udział w operacji rozdzielania pozostają wypełnione przynajmniej w dwóch trzecich.

Rys. 9.11. Jeśli w B*-drzewie zarówno węzeł, jak i jego brat są pełne, to jest wykonywane rozdzielanie: tworzy się nowy węzeł, a klucze są rozmieszczane równo w trzech węzłach

Podsumowując ten podrozdział, zauważmy, że - jak można było oczekiwać - poprawę współczynnika wypełnienia można zrealizować na wiele sposobów, a niektóre systemy baz danych pozwalają nawet użytkownikowi wybrać ten współczynnik między 0,5 a 1. W szczególności, B-drzewo, którego węzły muszą być wypełnione
#260
przynajmniej w 75%, jest nazywane B^**-drzewem [81. Nazwa ta sugeruje żartobliwe uogólnienie; B^n* -drzewo to B-drzewo, którego węzły muszą być wypełnione przynajmniej w (n+1)/(n+2) całości.

9.1.3. B^+-drzewa

Jeden węzeł B-drzewa reprezentujejedną strone lub blokpamięci zewnętrznej, przejście od jednego węzła do drugiego wymaga więc czasochłonnej zmiany stron. Z tego względu chcielibyśmy realizować możliwie najmniej odwołań do węzłów. Co by się stało gdybyśmy zażądali wypisania wszystkich kluczy w B-drzewie w kolejności rosnącej? Można by użyc łatwej do zaimplementowania metody intorder, ale dla węzłów nie będącymi liścmi byłby wpisywany tylko jeden klucz naraz, a potem trzeba by sięgnąć do następnej strony. Dobrze by było zatemulepszyć B-drzewa tak, żeby umożliwiały nam sekwencyjny dostęp do danych, szybszy niż przy użyciu metody inorder. B^+-drzewo stanowi takie rozwiązanie.
W B-drzewie odwołania do danych występują w każdym węźle drzewa, natomiast w B^+-drzewie - jedynie w liściach. Wewnętrzne węzły B^+-drzewa służą jako indeksy umożliwiające szybki dostęp do danych, ta część drzewa jest nazywana zbiorem indeksowym. Liście różnią się strukturą od pozostałych węzłów B^+-drzewa i są zazwyczaj połączone w listę, tworząc łańcuch. Przeglądanie tej listy daje sekwencyjny dostęp do danych. B^+-drzewo to zatem naprawdę B +drzewo: - zawiera indeks zaimplementowany jako zwyczajne B-drzewo plus listę danych. Na rysunku 9.12. widać przykład B*-drzewa.

Rys. 9.12. Przykład B'-drzewa rzędu 4
Rys. 9.12. Przykład B+-drzewa rzędu 4
#261
Odnotujmy, że węzeł wewnętrzny przechowuje klucze, wskaźniki i licznik kluczy. Liść Liść przechowuje klucze, adresy związanych z nimi rekordów w pliku z danymi oraz wskaźnik do następnego liścia.
Operacja na B^+-drzewach nie różni się od operacji na B-drzewach. Wstawianie klucza do liścia, w którym jest jeszcze wolne miejsce, wymaga ustawienia kluczy w tym liściu we właściwej kolejności. Nie zmienia się przy tym zbiór indeksowy. Jeśli klucz jest wstawiany do pełnego liścia, to liść ten jest rozdzielany, nowy liść jest włączany do łańcucha, klucze są rozdzielane równomiernie między stary i nowy liść, a pierwszy klucz z nowego węzła jest kopiowany (a nie przemieszczany, jak w B-drzewie) do ojca jako separator pomiędzy tymi liśćmi. Jeśli ojciec nie jest pełny, może to wymagać lokalnej reorganizacji kluczy w tym węźle (zob. rys. 9.13). Nowy liść jest tworzony i włączany do łańcucha, klucze są rozdzielane między te dwa liście, a nowy separator zostaje skopiowany z nowego liścia do ojca. Jeśli ojciec jest pełny, to proces rozdzielania postępuje jak w zwykłym B-drzewie - zbiór indeksowy jest przecież B-drzewem.

Rys. 9.13. Próba wstawienia liczby 6 do pierwszego liścia w B^+-drzewie

Usunięcie klucza z liścia, jeśli nie powoduje wystąpienia niedoboru, ogranicza się do poprawienia ustawienia pozostałych kluczy w kolejności, bez zmian w zbiorze indeksowym. W szczególności, jeśli trzeba skasować klucz występujący nie tylko w liściu, to po prostu usuwa się go z liścia, ale pozostawia w węźle wewnętrznym. Powodem takiego postępowania jest to, że klucz ten nadal pomaga znaleźć właściwą
#262
ścieżkę podczas wędrówki w dół B+-drzewa, ponieważ wciąż poprawnie separuje klucze dwóch sąsiednich synów swojego węzła, chociaż sam separator nie występuje w żadnym z tych dwóch poddrzew. W wyniku usunięcia klucza 6 z drzewa na rysunku 9.13b otrzymujemy drzewo widoczne na rysunku 9.14a. Zwróćmy uwagę, że liczba 6 nie została usunięta z węzła wewnętrznego.

Rys. 9.14. Operacje po usunięciu liczby 6 z B+-drzewa na rysunku 9.135

Jeśli usunięcie klucza z liścia powoduje niedobór, to albo klucze z tego liścia i jego brata są równo rozdzielane między te dwa węzły, albo liść zostaje usunięty, a jego pozostałe klucze są przenoszone do jego brata. Rysunek 9.14b ilustruje ten ostatni przypadek. Po usunięciu liczby 2 pojawia się niedobór i dwa liście są łączone w jeden. Pierwszy klucz prawego sąsiada węzła powstającego po połączeniu jest kopiowany do ojca, a klucze w ojcu są porządkowane. Obydwie te operacje wymagają uaktualnienia mieszczącego się w ojcu klucza separującego dwa liście. Usunięcie liścia może też wywołać serię złączeń węzłów w zbiorze indeksowym.

9.1.4. Prefiksowe B^+-drzewa

Jeśli klucz występował w liściu i w węźle wewnętrznym B^+-drzewa, to wystarczało usunąć go tylko z liścia, bo klucz pozostający w wężle wewnętrznym nadal umożliwiał poprawne wyszukiwanie. Nie ma więc tak naprawdę znaczenia, czy klucz z węzła wewnętrznego występuje w jakimś liściu czy też nie. Liczy się to, że nadaje się on
#263
na separator dla kluczy w sąsiadujących ze sobą synach jego węzła; na przykład dla dwóch kluczy K_1 i K_2 separator s musi spełniać warunek K_1Proste prefiksowe B+-drzewo [3] to B^+-drzewo, w którym rolę separatorów pełnią najkrótsze prefiksy (fragmenty początkowe) pozwalające na rozróżnienie dwóch sąsiadujących kluczy. Na rysunku 9.12 na przykład lewy syn korzenia zawiera dwa klucze BF90 i BQ322. Jeśli klucz jest mniejszy niż BF90, wybierany jest pierwszy liść; jeśli jest mniejszy niż BQ322, właściwym wyborem jest drugi liść. Zauważmy jednak, że osiągnęlibyśmy ten sam efekt, gdyby zamiast BF90 użyć klucza BF9 albo nawet BF, a zamiast BQ322 -jednego z trzech jego prefiksów: BQ32, BQ3 lub tylko BQ. Wybierzmy zatem najkrótsze prefiksy obydwu kluczy. Jeśli teraz dany klucz jest mniejszy niż BF, to wyszukiwanie kończy się w pierwszym liściu, a jeśli jest mniejszy niż BQ, to wybierany jest drugi liść - tak samo jak poprzednio. Redukcja rozmiaru separatorów do niezbędnego minimum nie zmienia rezultatu wyszukiwania. Dzięki zmniejszeniu separatorów można większą ich liczbę zmieścić w tym samym węźle, węzeł taki może więc mieć więcej synów. Całe B^+-drzewo ma mniej poziomów, co przyspiesza jego przetwarzanie.
Rozumowanie to nie kończy się na poziomie ojców liści. Przenosi się ono na każdy z pozostałych poziomów - cały zbiór indeksowy B-drzewa może składać się z prefiksów kluczy (zob. rys. 9.15).

Rys. 9.15. B'-drzewo z rysunku 9.12 przedstawione jako proste prefiksowe B^+-drzewo
#264
Operacje na prostym prefiksowym B^+-drzewie są bardzo podobne do operacji na zwykłym B^-drzewie, z pewnymi modyfikacjami uwzględniającymi użycie prefiksów jako modyfikatorów. W szczególności po wykonaniu rozdzielenia , nie przemieszcza się ani nie kopiuje pierwszego klucza nowego węzła, ale znajduje się najkrótszy prefiksodróżniający go od prefiksuostatniego klucza w starym węźle, który to prefiks znajduje się w ojcu. Przy usuwaniu klucza niektóre separatory w zbiorze indeksowym mogą okazać się zbyt długie , można ich jednak nie skracać od razu, dzięki czemu usuwanie jest szybsze.
Pomysł użycia prefiksów jako separatorów można rozwinąć dalej, jeśli zauważymy, że można opuszczać prefiksy prefiksów na niższych poziomach drzewa, na czym opiera się idea prefiksowego B+-drzewa. Metoda ta działa szczególnie dobrze, jeśli prefiksy są długie i powtarzają się. Na rysunku 9.16 jest przedstawiony przykład. Każdy klucz w drzewie zawiera prefiks AB12XY, prefiks ten pojawia się więc we wszystkich węzłach wewnętrznych. Jest to zbędne; na rysunku 9.16b widać to samo drzewo, w którym z prefiksów kluczy w synach korzenia usunięto "AB12XY". Aby odtworzyć pierwotny prefiks, klucz z ojca bez ostatniego znaku dołącza się na początek klucza w bieżącym węźle. Na przykład w pierwszej komórce syna korzenia na rysunku 9.16b znajduje się klucz "08". Ostatni znak klucza w korzeniu odrzuca się, a otrzymany prefiks "AB12XY" umieszcza się przed "08". Nowy prefiks "AB12XY08" służy do wyznaczenia kierunku wyszukiwania.
Jak efektywne są prefiksowe B^+-drzewa? Eksperymenty wykazują, że nie ma prawie różnicy w czasie wykonywania algorytmów na B+-drzewach i prostych prefiksowych B+-drzewach, natomiast prefiksowe B+-drzewa są o 50-100% wolniejsze. Jeśli idzie o liczbę dostępów do dysku, nie ma tu większych różnic dla drzew do 400 węzłów. Dla drzew od 400 do 800 węzłów zarówno proste prefiksowe B^+-drzewa, jak i prefiksowe B^+-drzewa wymagają 20-25% mniej dostępów [3]. Widać stąd, że proste prefiksowe B+-drzewa stanowią opcję godną rozważenia, prefiksowe B^+-drzewa są zaś interesujące głównie z teoretycznego punktu widzenia.

9.1.5. Drzewa bitowe

Bardzo interesujące podejście stanowi skrajna w pewnym sensie eksploatacja metody prefiksowego B+-drzewa. W metodzie tej do określania separatorów wykorzystywało się bajty. W drzewach bitowych operuje się na poziomie bitów [5].
Konstrukcja drzewa bitowego opiera się na pojęciu bitu rozróżniającego (D-bitu, ang. distinction bit). Bit rozróżniający D(K, L) to numer najbardziej znaczącego bitu, na którym różnią się dwa klucze K i L, dokładniej D(K, L) = dtugość-klucza-w-bitach - 1 - [lg(K xor L)]. Na przykład D-bit dla liter "K" i "N", których kody ASCII to odpowiednio 01001011 i 01001110, jest równy 5, czyli numerowi pozycji, na której pojawia się pierwsza różnica między tymi kluczami; Z)(,,K", "N") = 8-l-Llg5j = 5.
Drzewo bitowe wykorzystuje D-bity do rozróżniania kluczy jedynie w liściach; pozostała część drzewa stanowi prefiksowe B+-drzewo. Oznacza to, że same klucze oraz całe rekordy, do których należą, są przechowywane w pliku z danymi, liście mogą więc zawierać znacznie więcej informacji niż wtedy, kiedy zawierałyby klucze. Na rysunku 9.17 widać liść drzewa bitowego. Elementy zapisane w liściu to D-bity i wskaźniki do rekordów w pliku z danymi. Liść nie zawiera samych kluczy, które można znaleźć jedynie w pliku z danymi. Zawartość liścia odwołuje się do kluczy w sposób pośredni, określając bity rozróżniające klucze odpowiadające sąsiadującym pozycjom w liściu. Zanim zaprezentujemy algorytm przetwarzania danych w drzewie bitowym, omówimy pewne pożyteczne własności D-bitów.
#265
Rys. 9.16. Proste prefiksowe B+-drzewo (a) i jego skrócona wersja przedstawiona jako prefiksowe B4-drzewo (b)
#266
Rys. 9.17. Liść drzewa bitowego

Wszystkie klucze w liściach są trzymane w porządku rosnącym. D_i = D(K_(i-1), K) wskazuje zatem pierwszy z lewej strony bit rozróżniający te klucze. Jest on zawsze równy 1 w kluczu K_j, ponieważ K_j < K_j dla 1 <=i(01001110, 01001111) = 7, a bit na pozycji 7 w drugim kluczu jest równy 1, natomiast wszystkie wcześniejsze są takie same.
Niech j będzie pierwszą pozycją w liściu, dla której D_j i; D_j jest pierwszym D-bitem mniejszym niż poprzedzający go Z),.. W takiej sytuacji we wszystkich kluczach między pozycjami i a j w tym liściu bit o numerze D_i jest równy 1. W przykładzie na rysunku 9.17 j = i + 2, ponieważ DM jest pierwszym D-bitem leżącym za pozycją i, który jest mniejszy niż D_i. Bit 5 w kluczu "O" na pozycji i+ 1 jest równy 1, podobnie jak w kluczu "N" na pozycji i.
Algorytm wyszukiwania klucza w liściu drzewa bitowego jest następujący:

BitTreeSearch(K) R = rekord R0 ;
for (i = 1; i < m; i++)
if bit o numerze D, w kluczu K jest równy 1
R = R, ;
else pomijaj wszystkie kolejne D-bity aż do znalezienia mniejszego;
#267
wczytaj rekord R z pliku ;
if K == klucz Z rekordu R
return R;
else return -1;

Wykorzystując powyższy algorytm, będziemy szukać klucza "V" zakładając, że na rysunku 9.17 i-1 =0, a i+3 jest ostatnią pozycją w liściu. Na początku R przyjmuje wartość R_0, a i jest równe 1.

1. W pierwszej iteracji pętli for jest sprawdzany bit D, = 5 w kluczu "V" =01010110, a ponieważ jest on równy 1, więc R przyjmuje wartość R_1.

2. W drugiej iteracji jest badany bit D_2 = 7. Jest on równy O, ale nic nie pomijamy, jak każe instrukcja po else, bo od razu zostaje znaleziony D-bit mniejszy niż 7.

3. Trzecia iteracja: bit D_3 = 3 jest równy 1, więc R staje się równe R_3.

4. W czwartej iteracji jest ponownie sprawdzany bit D_4 = 5, a ponieważ jest on równy 1, więc do R jest przypisywana wartość R_4. Jest to ostatnia pozycja w liściu; procedura kończy się i zwracana jest poprawna wartość R_4.

Co się dzieje, jeśli żądanego klucza nie ma w pliku z danymi? Możemy spróbować poszukać "S" =01010011, przyjmując te same założenia na i-1 oraz i+3. Bit D_1 = 5 jest równy O, więc pozycja z D-bitem równym 7 zostaje pominięta, a ponieważ bit
D_3 = 3 w kluczu "S" jest równy 1, więc nasza procedura zwróciłaby rekord R_3. Aby temu zapobiec, procedura BitTreeSearch () sprawdza, czy rekord, który znalazła, rzeczywiście odpowiada żądanemu kluczowi. Jeśli nie, to zwracana jest liczba ujemna, co oznacza niepowodzenie.

9.1.6. R-drzewa

Dane przestrzenne to obiekty często wykorzystywane w rozmaitych dziedzinach. Projektowanie wspomagane komputerowo (CAD), problematyka geograficzna czy projektowanie układów o bardzo dużym stopniu scalenia (VLSI) stanowią przykłady zastosowań, w których dane przestrzenne są tworzone, przeszukiwane i usuwane. Efektywne przetwarzanie tego typu danych wymaga użycia specjalnych struktur danych. Możemy na przykład zażądać wypisania wszystkich okręgów administracyjnych na obszarze określonym przez dane współrzędne geograficzne albo wyznaczenia wszystkich budynków, do których można dojść na piechotę od ratusza. Istnieje wiele rozmaitych struktur danych dogodnych dla tego rodzaju danych. Jedną z nich jest R-drzewo [7].
R-drzewo rzędu m jest podobną do B-drzewa strukturą zawierającą przynajmniej m elementów w każdym węźle (z wyjątkiem korzenia) dla pewnego m nie większego od maksymalnej dopuszczalnej liczby elementów w węźle. R-drzewo nie musi być zatem do połowy wypełnione.
Liść R-drzewa zawiera pary (rect, id), przy czym rect = ([x_0, y_0], ..., [x_n, y_n]) jest n-wymiarowym prostokątem, a id jest wskaźnikiem do rekordu w pliku z danymi.
#268
Składnik rec jest najmniejszym prostokątem zawierającym obiekt id. Na przykład element w liściu odpowiadający obiektowi X na płaszczyźnie kartezjańskiej z rys.9.18. byłby parą (([10, 100], [5,52]),X)

Rys. 9.18. Obszar X na płaszczyźnie kartezjańskiej wpisany w prostokąt ([10, 100], [5, 52]). Współrzędne prostokąta i identyfikator obszaru są przechowywane w liściu R-drzewa

Element zapisany w węźle wewnętrznym ma postać (rect, child), gdzie rect jest najmniejszym prostokątem obejmującym wszystkie prostokąty węzła child. Struktura R-drzewa nie jest identyczna ze strukturą B-drzewa: tę pierwszą można traktować jako ciąg n kluczy i n wskaźników odpowiadających tym kluczom.
Wstawianie nowych prostokątów do R-drzewa wykonuje się podobnie jak w B-drzewie - z rozbijaniem węzłów i rozdzielaniem kluczy między węzły. Kluczową operacją jest odnalezienie właściwego liścia, do którego należy wstawić prostokąt rect. Podczas wędrówki w dół R-drzewa w bieżącym węźle wybieramy poddrzewo odpowiadające prostokątowi, który trzeba by najmniej powiększyć, żeby zawierał rect. Jeśli dochodzi do rozdzielenia węzła, to trzeba utworzyć nowy prostokąt otaczający mniejsze. Szczegóły algorytmu są dość skomplikowane; nie jest na przykład oczywiste, jak dzielić prostokąty w rozdzielanym węźle. Algorytm powinien tworzyć prostokąty obejmujące prostokąty obydwu powstających węzłów, a przy tym minimalnej wielkości.
Na rysunku 9.19 jest przedstawiony przykład wstawiania czterech prostokątów do R-drzewa. Po wstawieniu pierwszych trzech prostokątów, R_1 R_2 i R_3, korzeń jest zapełniony (rys. 9.19a). Wstawienie RĄ powoduje rozdzielenie węzła, prowadzące do utworzenia dwóch prostokątów otaczających mniejsze prostokąty (rys. 9.19b). Wstawienie R_7 nic nie zmienia, a wstawienie R_8 powoduje rozszerzenie prostokąta R_6 tak, by obejmował R_8 (rys. 9.19c). Na rysunku 9.19d widać kolejne rozbicie po wstawieniu R_9 do R-drzewa. Prostokąt R_6 znika, a tworzone są R_10 i R_11.
Prostokąt R może zawierać się w wielu większych prostokątach, ale w liściu może być umieszczony tylko raz. Z tego powodu procedura wyszukiwania może wybrać złą ścieżkę na pewnym poziomie h, kiedy widzi, że R jest zawarty w innym prostokącie w węźle na tym poziomie. Na przykład prostokąt R_3 na rysunku 9.19d jest zawarty zarówno w R_1O, jak i R_11. Ponieważ w korzeniu R_10 znajduje się przed R_11 procedura dotrze do właściwego liścia przy wyszukiwaniu R_3. Gdyby jednak R_11, po-
przedzał R_10 w korzeniu, pójście ścieżką odpowiadająca R , zakończyłoby się niepowodzeniem. Dla dużych i wysokich R-drzew ten efekt nakładania się prostokątów staje się drastyczny.
Modyfikacja R-drzewa, zwana R^+-drzewem jest wolna od wady [10,11]. Otaczająceprostokąty już się nie przecinają, a kazdy z nich jest zwiazany ze wszystkimi prostokątami, które przecina. Teraz jednak mieszczący dane prostokąt można znaleźć w więcej niż jednym liściu. Na rysunku 9.20 przedstawione jest R^+-drzewo skonstruowane po wstawieniu prostokąta R_9) do R-drzewa z rysunku 9.l9c. Rysunek 9.20 zastępuje rysunek 9.19d. Zwróćmy uwagę, że prostokąt R_8 można znaleźć w dwóch liściach, ponieważ jest on przecinany przez dwa otaczające prostokąty, R_10 i R_11. Realizując operacje na R+-drzewie, trudno bez dodatkowych manipulacji zapewnić, by węzły były przynajmniej w połowie wypełnione.
#269
Rys. 9.19. Budowanie R-drzewa
#270
Rys. 9.20. R-drzewo z rysunku 9.19d po wstawieniu prostokąta Rg do drzewa z rysunku 9.19c, reprezentowane jako R^+-drzewo

9.1.7. 2-4 drzewa

W podrozdziale tym omawiamy szczególny przypadek B-drzewa, mianowicie B-drzewo rzędu 4. Jako pierwszy analizował je Rudolf Bayer, który nazwał je symetrycznym binarnym B-drzewem [1], zwykle jednak jest nazywane 2-3-4 drzewem lub po prostu 2-4 drzewem. Wydaje się, że drzewo to nie otwiera żadnych nowych perspektyw, jest jednak wręcz przeciwnie. W B-drzewach rozmiar węzła jest wielki, by mógł on pomieścić cały blok z pamięci zewnętrznej. Z kolei w 2-4 drzewach w jednym węźle można pomieścić zaledwie jeden, dwa lub co najwyżej trzy elementy. Jeżeli elementy nie są bardzo duże, tak duże, by trzy z nich mogły wypełnić jeden blok na dysku, wydaje się, że brak powodów, by choćby wspominać o B-drzewach tak małego rzędu. Chociaż B-drzewa zostały omówione w kontekście operowania danymi w pamięci zewnętrznej, nie znaczy to, że muszą być używane wyłącznie w tym celu.
Poświęciliśmy cały rozdział omówieniu drzew binarnych, a zwłaszcza drzew poszukiwań binarnych, oraz algorytmów umożliwiających szybki dostęp do informacji przechowywanych w tych drzewach. Czy B-drzewa oferują lepsze rozwiązanie problemu równoważenia albo przechodzenia drzew binarnych? Chcielibyśmy powrócić teraz do zagadnień związanych z drzewami binarnymi i przetwarzaniem danych w pamięci wewnętrznej.
B-drzewa mogą skutecznie rywalizować z algorytmami dla drzew poszukiwań binarnych, ponieważ B-drzewo z samej swojej natury musi być zrównoważone. Nie-
#271
potrzebne są żadne dodatkowe zabiegi przy tworzeniu drzewa: budowanie B-drzewa jednocześnie je równoważy. Zamiast stosować drzewa poszukiwań binarnych, możemy używać B-drzew małego rzędu, jak 2-4 drzewa. Jeśli jednak drzewa te implementujemy bezpośrednio jako B-drzewa, to w węźle mamy trzy miejsca na umieszczenie co najwyżej trzech kluczy i cztery miejsca na co najwyżej cztery wskaźniki. W najgorszym przypadku oznacza to, że połowa tych miejsc jest nie wykorzystana, a w przypadku średnim 69%. Ponieważ wykorzystanie miejsca znacznie bardziej liczy się przy operowaniu pamięcią główną niż zewnętrzną, chcielibyśmy uniknąć tego marnotrawstwa. Z tego względu przekształcimy 2-4 drzewo w postać drzewa binarnego, w którym każdy węzeł przechowuje tylko jeden klucz. Transformacja ta musi oczywiście być wykonana w sposób pozwalający na jednoznaczne odtworzenie pierwotnej formy B-drzewa.
Aby reprezentować 2-4 drzewo jako drzewo binarne, potrzebujemy dwóch typów połączeń między węzłami: jeden typ oznacza powiązanie węzłów reprezentujących klucze należące do tego samego węzła w 2-4 drzewie, a drugi to zwykła krawędź łącząca ojca i syna. Bayer nazywa je odpowiednio poziomymi i pionowymi wskaźnikami lub, bardziej tajemniczo, p-wskaźnikami i 6-wskaźnikami; Guibas i Sedge-wick, stosując dwukolorową terminologię, używają nazw czerwone i czarne wskaźniki. Nie tylko nazwy się różnią, ale i same drzewa także rysowane są trochę inaczej. Na rysunku 9.2] widać węzły o dwóch i trzech kluczach, nazywane odpowiednio 3-węzłami i 4-węzłami, oraz ich dwie równoważne reprezentacje. Na rysunku 9.22 jest pokazane całe 2-4 drzewo i jego odpowiedniki będące drzewami binarnymi. Czerwone dowiązania są tu narysowane linią przerywaną. Drzewo czerwono-czarne ma wyraźniejszą formę drzewa binarnego, drzewa poziomo-pionowe lepiej zachowują kształt 2-4 drzew, a ich liście są pokazane tak, jakby były na tym samym poziomie. Drzew poziomo-pionowych można także bez trudności użyć do reprezentowania B-drzew dowolnego rzędu; z drzewami czerwono-czarnymi tak nie jest.
Zarówno drzewa czerwono-czarne, jak i poziomo-pionowe są drzewami binarnymi. Każdy węzeł zawiera dwa wskaźniki, które można interpretować na dwa sposoby. W celu rozróżnienia tych interpretacji każdy wskaźnik wyposaża się w znacznik. Węzeł drzewa poziomo-pionowego można zadeklarować jako

struct VHTTreeNode { DataType key;
struct VHTTreeNode *left, *right;
unsigned int LeftYert, RightVert : 1;

Operacje wykonywane na drzewach poziomo-pionowych są takie same jak na drzewach binarnych, chociaż ich implementacja jest znacznie bardziej skomplikowana. Jedynie wyszukiwanie jest identyczne: przy szukaniu klucza w drzewie poziomo--pionowym nie rozróżnia się wskaźników różnych typów i można zastosować tę samą procedurę przeszukiwania co dla drzew poszukiwań binarnych: jeśli klucz został odnaleziony, zatrzymujemy się. Jeśli klucz w bieżącym węźle jest większy niż szukany, to idziemy do lewego poddrzewa, w przeciwnym razie do prawego.
#272
Rys. 9.21. 3-węzeł (a) reprezentowany na dwa możliwe sposoby.

Przed omówieniem operacji wstawiania odnotujmy następujące własności drzew poziomo-pionowych:

=> Ścieżka od korzenia do każdego liścia zawiera taką samą liczbę dowiązań pionowych.

=> Żadna ścieżka od korzenia nie może zawierać dwóch kolejnych dowiązań poziomych.
Wstawienia zmieniają strukturę drzewa przez dodanie nowewego węzła i nowego dowiązania. Czypowinno ono być pionowe czy poziome?. Usuwanie także zmienia drzewo przez likwidację jednego węzła i jednego dowiazania, może to jednak prowadzić do pojawienia sie dwóch sasiednich dowiazań poziomych. Operacje te nie będa tak proste jak dla drzew poszukiwań binarnych, ponieważ ponieważ muszą uwzględniać pewne odpowiedniki rozdzielania i łaczenia węzłów.
Dobrym pomysłem przy rozdzielaniu węzłów 2-4 drzewa, o czym wspominaliśmy juz przy omawianiu B-drzew, jest rozdzielenie węzłów podczas wędrówki w dółdrzewa w trakcie wstawiania klucza. jeśli napotkamy 4-węzeł to jest on rozdzielany przed dalszym marszem w głąb drzewa. Ponieważ operacja rozdzielania odbywa się
#273
od góry do dołu, 4-węzeł może być synem 2-węzła albo 3-węzła (z tym co zwykle wyjątkiem: chyba że jest on korzeniem). Na rysunkach 9.23a i 9.23b jest przedstawiony przykład. Rozdzielanie węzła o kluczach B, C i D wymaga utworzenia nowego węzła. Dwa węzły biorące udział w rozdzieleniu (rys. 9.23a) są wypełnione w 4/6, trzy węzły po rozbiciu są wypełnione w 4/9 (dla pól wskaźnikowych odpowiednio 6/8 i 7/12). Rozdzielanie węzłów 2-4 drzew nie jest więc wydajne. Jeśli jednak te same operacje wykonywać na będących ich odpowiednikami drzewach poziomo-pio-nowych, to efektywność staje się godna uwagi. Na rysunkach 9.23c i 9.23d to samo rozbicie jest wykonywane na drzewie poziomo-pionowym, a cała operacja wymaga jedynie zmiany dwóch znaczników z "poziomego" na "pionowy" i jednego z "pionowego" na "poziomy": w sumie przestawienia trzech bitów!

Rys. 9.22. 2-4 drzewo (a) reprezentowane jako drzewo czerwono-czarne (b) i poziomo-pionowe (c)

Zmiana tych trzech znaczników sugeruje użycie algorytmu FlagFlipping o następujących krokach: jeśli odwiedzamy węzeł n, którego obydwa dowiązania są
#274
poziome, to zmieniamy znacznik odpowiadający dowiązaniu ojca węzła n do n na "poziomy", a obydwa znaczniki w n na "pionowy".
Jeśli mamy sytuację jak na rysunku 9.24a, to dochodzi do rozdzielenia w 2-4 drzewie, jak na rysunku 9.24b; zastosowanie algorytmu FlagFlipping do równoważnego drzewa poziomo-pionowego wymaga zmiany tylko trzech bitów (rys. 9.24c i 9.24d).
Z rysunku 9.21 widać, że ten sam węzeł 2-4 drzewa może mieć dwa odpowiedniki w drzewie poziomo-pionowym. Sytuacja na rysunku 9.24a może być zatem przedstawiona nie tylko jako drzewo na rysunku 9.24c, ale również jako drzewo na rysunku 9.25a. Jeśli postąpimy jak poprzednio, zmieniając trzy znaczniki jak na rysunku 9.24d, to dostaniemy drzewo z rysunku 9.25b z dwoma kolejnymi poziomymi dowiązaniami, nie odpowiadające żadnemu 2-4 drzewu. W tym wypadku po zmianie trzech znaczników musi nastąpić rotacja, a dokładniej trzeba dokonać rotacji węzła B względem A, zamiany dwóch znaczników i otrzymane drzewo na rysunku 9.25c jest takie samo, jak na rysunku 9.24d.
Na rysunku 9.26a widać inny przypadek 4-węzła dołączonego do 3-węzła w 2-4 drzewie przed rozdzieleniem. Rysunek 9.26b to widok drzewa po rozdzieleniu. Zastosowanie algorytmu FlagFlipping do drzewa z rysunku 9.26c daje drzewo z rysunku 9.26d z dwoma kolejnymi dowiązaniami poziomymi. Aby przywrócić własność drzewa poziomo-pionowego, konieczne są dwie rotacje i dwie zmiany typu krawędzi: jest wykonywana rotacja węzła C względem E (rys. 9.26e), a potem węzła C względem /4, w wyniku czego otrzymujemy drzewo pokazane na rysunku 9.26f.

Rys. 9.23. Rozdzielenie 4-węzła dołączonego do węzła o jednym kluczu w 2-4 drzewie (a, b). To samo rozdzielenie w równoważnym drzewie poziomo-pionowym (c, d)
#275
Rys. 9.24. Rozdzielenie 4-węzła dołączonego do 3-węzła w 2-4 drzewie (a, b) i podobna operacja wykonana na jednym z możliwych równoważnych drzew poziomo-pionowych (c, d)

Rys. 9.25. Poprawianie drzewa poziomo-pionowego, zawierającego kolejne dowiązania poziome

Zaprezentowaliśmy cztery konfiguracje prowadzące do rozdzielenia węzła. Liczbę tę trzeba podwoić, jeśli dodamy lustrzane odbicia analizowanych sytuacji. Liczba szczególnych przypadków jest dosyć duża, a fakt ten znajduje odzwierciedlenie w poniższym algorytmie wstawiania.
#276
Rys. 9.26. 4-węzeł dołączony do 3-węzła w 2-4 drzewie

HVTreelnsert(K)
utwórz węzeł new_node i nadaj odpowiednie wartości początkowe jego polom;
if drzewo jest puste root = new_node;
return;
for (p = root, prev = NULL; p !=NULL;)
if obydwa znaczniki w p są równe 0 /* poziome */
zmień je na 1; /* pionowe */
oznacz dowiązanie prev do p jako 0 ;
if dowiązania ojca prev do prev oraz prev do p obydwa są 0
if obydwa te dowiązania są prawe lub obydwa są lewe
wykonaj rotację prę v względem jego ojca;
else wykonaj rotację p względem prev, a później
#277
p względem jego nowego ojca;
prev = p;
if (p->key > K) p =p->left;
else p = p->right ;
dołącz węzeł new_node do prev;
oznacz dowiązanie prev do new_node jako 0 ;
if dowiązanie od ojca prev do prev jest oznaczone jako 0
wykonaj rotację prev względem jego ojca lub
najpierw wykonaj rotację new_node względem prev, a
potem new_node względem jego nowego ojca;

Na rysunku 9.27 widać przykład wstawienia ciągu liczb. Zwróćmy uwagę, że w drzewie na rysunku 9.27h przy wstawianiu 6 trzeba wykonać podwójną rotację. Najpierw jest wykonywana rotacja 9 względem 5, a następnie 9 względem 11.

Rys. 9.27. Budowanie drzewa poziomo-pionowego przez wstawianie liczb następującego ciągu: 10, 11, 12, 13, 4, 5, 8, 9, 6, 14
#278
Jak efektywne jest drzewo poziomo-pionowe w porównaniu z drzewami zrównoważonymi? Ponieważ minimalna liczba węzłów n w poziomo-pionowym drzewie wysokości h nie wyraża się tym samym wzorem dla parzystych i nieparzystych wysokości, można wykazać następujące zależności między n a. h:

lg(n+1)<=h<=2lg(n + 2)-2

Górnym ograniczeniem wysokości drzewa poziomo-pionowego jest w przybliżeniu 2 lg n, czyli więcej niż dla drzew AVL - 1,44 lg n. Drzewa poziomo-pionowe mogą się zatem wydawać mniej użyteczne niż drzewa AVL. Wymagają one jednak mniej zmian struktury drzewa podczas operacji wstawiania węzła niż drzewa AVL. Co więcej, zmiany te mogą być ograniczone do przestawienia zaledwie trzech bitów, podczas gdy w drzewie AVL przy równoważeniu drzewa trzeba dokonać przynajmniej jednej rotacji. Drzewa AVL warto więc stosować w programach wymagających niewielu zmian w drzewie, a wykorzystujących je głównie do odczytywania informacji. Jeśli z kolei oczekujemy dużej liczby wstawień i usunięć węzłów, to drzewo poziomo-pionowe stanowi roztropniejszy wybór.

Rys. 9.28. Przykład przekształcenia drzewa AVL (a) w równoważne drzewo poziomo-pionowe (b)

Klasa drzew poziomo-pionowych zawiera zresztą w sobie drzewa AVL. Drzewo AVL można przekształcić w drzewo poziomo-pionowe, zmieniając dowiązania łączące korzenie poddrzew parzystej wysokości z ich synami wysokości nieparzystej w dowiązania poziome. Rysunek 9.28 ilustruje to przekształcenie.
#279

9.2. Drzewa trie

W poprzednim rozdziale widzieliśmy, że przechodzenie drzewa binarnego odbywało się na podstawie porównań całych kluczy; każdy węzeł zawierał klucz, który był porównywany z innym kluczem w celu znalezienia właściwej drogi wzdłuż drzewa. Przykład prefiksowych B-drzew wskazuje, że nie jest to konieczne i że do wyznaczenia ścieżki niezbędna jest tylko część klucza. Teraz jednak problemem staje się znalezienie właściwego prefiksu, a konieczność zachowywania dopuszczalnej postaci i rozmiaru prefiksów czyni proces wstawiania i usuwania bardziej skomplikowanym niż w zwykłych B-drzewach. Drzewo, w którym wykorzystuje się fragmenty kluczy do sterowania wyszukiwaniem, nazywamy drzewem trie. Nazwa ta pochodzi od ang. retrieval (odczytanie), ale ze zmienioną wymową: dla odróżnienia od słowa tree nazwę trie wymawia się jako "traj".
Każdy klucz jest ciągiem znaków, a struktura drzewa trie bazuje raczej na tych znakach niż na całych kluczach. Załóżmy dla uproszczenia, że wszystkie klucze składają się z pięciu wielkich liter: A, E, I, P, R. Istnieje wiele słów, które można utworzyć z tych pięciu liter, ale w naszych przykładach znajdzie się tylko kilka spośród nich.
Na rysunku 9.29 widać drzewo trie dla słów umieszczonych w pionowych prostokątach; tej formy jako pierwszy użył E. Fredkin. Prostokąty te reprezentują liście drzewa trie, które są węzłami zawierającymi właściwe klucze. Węzły wewnętrzne można traktować jako tablice wskaźników do poddrzew trie. Na każdym poziomie i zaglądamy na pozycję w tablicy, odpowiadającą i-tej literze przetwarzanego klucza. Jeśli wskaźnik na tej pozycji jest równy NULL, to danego klucza nie ma w drzewie, co może oznaczać niepowodzenie lub sygnał do wstawienia klucza. Jeśli wskaźnik nie jest równy NULL, to kontynuujemy przetwarzanie aż do osiągnięcia liścia zawierającego szukany klucz. Poszukajmy na przykład słowa "ERIE". Na pierwszym poziomie drzewa trie jest sprawdzany wskaźnik odpowiadający pierwszej literze tego słowa, czyli "E". Wskaźnik ten nie jest równy NULL, idziemy więc na drugi poziom drzewa trie, do syna korzenia dostępnego z pozycji ,,E". Teraz jest sprawdzany wskaźnik na pozycji odpowiadającej drugiej literze - ,,R". On również jest różny od NULL, obniżamy się więc o kolejny poziom w drzewie trie. Na trzecim poziomie jako indeksu wskaźnika używamy trzeciej litery - ,,I". Wskaźnik wskazuje na liść zawierający słowo "ERIE", zatem poszukiwanie zakończyło się sukcesem. Gdyby szukanym słowem było "ERIIE", ponieślibyśmy porażkę, doszlibyśmy bowiem do tego samego liścia co poprzednio, a nasze dwa słowa byłyby różne. Gdyby zaś danym słowem było "ERPIE", doszlibyśmy do węzła, którego jeden z synów jest liściem zawierającym słowo "ERIE", tym razem jednak sięgnęlibyśmy do wskaźnika odpowiadającego w tym węźle literze "P". Ponieważ wskaźnik ten jest równy NULL, wnioskujemy, że słowa "ERPIE" nie ma w naszym drzewie trie.
Od razu pojawiają się dwa problemy. Po pierwsze, w jaki sposób odróżnić dwa słowa takie, że jedno jest prefiksem drugiego? Słowo "ARE" jest na przykład prefik-sem "AREA", jeśli więc poszukujemy słowa "ARĘ" w drzewie trie, to nie wolno nam podążyć ścieżką prowadzącą do ,,AREA".
#280
Rys. 9.29. Drzewo trie dla pewnego zbioru słów składających się z liter A, E, I, P oraz R. Znak # oznacza koniec słowa, które może być prefiksem innego słowa
#281
Aby to zapewnić, w każdym węźle używamy dodatkowo specjalnego znaku, nie występującego w żadnym słowie - tutaj jest to znak "#". Teraz podczas poszukiwania słowa "ARĘ" po przetworzeniu znaków "A", ,,R" i ,,E" znajdziemy się na czwartym poziomie drzewa trie, w węźle, którego synami są liście ,,ARE" i "AREA". Ponieważ przetworzyliśmy już wszystkie litery klucza ,,ARE", sprawdzamy wskaźnik odpowiadający końcowi słowa, czyli "#", a skoro jest on nłepusty, wnioskujemy, że słowo należy do struktury.
Ostatni przykład wskazuje kolejny problem. Czy naprawdę niezbędne jest przechowywanie w drzewie trie całych słów? Czy po osiągnięciu czwartego poziomu podczas szukania ,,ARE" i stwierdzeniu, że wskaźnik odpowiadający znakowi "#" nie jest równy NULL, musimy iść do liścia i wykonywać porównanie klucza ,,ARE" z zawartością liścia, również ,,ARE"? Niekoniecznie, a przykład prefiksowych B-drzew podpowiada rozwiązanie problemu. Wystarczy, aby liście zawierały jedynie nie przetworzone sufiksy słów. W języku C może to nawet przyspieszyć porównywanie. Jeśli na każdym poziomie drzewa trie wskaźnik s do naszego słowa jest przesuwany, to po osiągnięciu liścia musimy tylko wykonać sprawdzenie strcmp(s, leaf->key). W przykładzie w podrozdziale 9.4 przyjmujemy to właśnie podejście.
Nasz przykład drzewa trie ograniczał liczbę używanych liter do pięciu, jednak w praktyce potrzebne byłyby wszystkie litery, każdy węzeł zawierałby więc 27 wskaźników**, wliczając "#". Wysokość drzewa trie wyznacza najdłuższy prefiks, a w przypadku słów angielskich prefiksy nie powinny być długie. Dla większości słów sprawa byłaby jasna już po odwiedzeniu kilku węzłów, zapewne 5-7. Byłoby to prawdą tak dla 10000 słów, jak i dla 100000. Odpowiednie doskonale zrównoważone drzewo poszukiwań binarnych dla 10000 słów miałoby wysokość [lg 10000]=14. Ponieważ większość słów leżałaby na najniższych poziomach tego drzewa, podczas wyszukiwania średnio odwiedzałoby się 13 węzłów. (Średnia długość ścieżki w doskonale zrównoważonym drzewie o wysokości h wynosi [lgh]-2). Jest to dwukrotnie więcej niż dla drzewa trie. W drzewie poszukiwań binarnych jest porównywany cały szukany klucz z kluczem w bieżącym węźle, podczas gdy w drzewie trie w porównywaniu biorą udział tylko pojedyncze znaki. Dla 100 000 słów średnia liczba odwiedzin węzłów w drzewie binarnym wzrośnie o trzy, bo [lg 100000]= 17; w drzewie trie liczba ta wzrośnie o 1 lub 2. W sytuacji, kiedy podstawowe znaczenie ma szybkość dostępu do danych, jak przy sprawdzaniu pisowni przez program, drzewo trie stanowi dobry wybór.
Ze względu na fakt, że drzewo trie zawiera dwa rodzaje węzłów, wstawianie do niego klucza jest nieco bardziej skomplikowane niż wstawianie klucza do drzewa poszukiwań binarnych.
#282
Trielnsert (K)
i = 0;
p = korzeń;
while nie wstawiony
if (K[i] == '\0')
przypisz wartość,,prawda" do znacznika końca słowa w p;
else if (p->ptrs[K[i]] ==NULL)
utwórz liść zawierający K i umieść jego adres w p->ptrs[K[i]] ;
else if węzeł p->ptrs[K[i]] jest liściem
K_L = klucz w liściu p->ptrs[K[i]j; do
utwórz węzeł wewnętrzny i umieść jego adres w p->ptrs[K[i]];
p = ten nowy węzeł wewnętrzny;
while (K[i] == K_L[i++]) ;
utwórz liść zawierający K i umieść jego adres w p->ptrs[K[i]];
if (K[i]== '\0')
przypisz wartość,,prawda" do znacznika końca słowa w p;
else utwórz liść zawierający K_L i umieść jego adres w p->ptrs[K[i]];
else p = p->ptrs[K[i++]];

Wewnętrzna pętla do w tym algorytmie jest potrzebna, kiedy prefiks słowa K i K_L jest dłuższy niż liczba węzłów na ścieżce prowadzącej do bieżącego węzła p. Na przykład przed wstawieniem słowa "REP" do drzewa trie z rysunku 9.29 słowo "REAR" leżało w liściu wskazywanym przez wskaźnik pod literą "R" w korzeniu drzewa. Przy wstawianiu "REP" nie wystarczy zastąpić tego liścia węzłem wewnętrznym, ponieważ drugie litery obydwu słów są takie same: ,,E". Musi zatem zostać utworzony kolejny węzeł wewnętrzny na trzecim poziomie drzewa trie, a dwa liście zawierające słowa "REAR" i "REP" trzeba do niego dołączyć.
Jeśli porównamy drzewa trie z drzewami poszukiwań binarnych, widzimy, że dla drzew trie kolejność wstawiania kluczy jest nieistotna, decyduje ona natomiast o kształcie drzew poszukiwań binarnych. Kształt drzew trie mogą jednak pogorszyć same słowa, a raczej rodzaj prefiksów wstawianych słów. Rozmiar najdłuższego wspólnego prefiksu dwóch słów wyznacza wysokość drzewa trie. Dokładniej, wysokość ta jest równa rozmiarowi najdłuższego prefiksu wspólnego dla dwóch słów plus jeden (na poziom rozróżniający słowa o tym prefiksie) plus jeden (na poziom liści). Drzewo trie na rysunku 9.29 ma wysokość pięć, ponieważ najdłuższy wspólny prefiks, "ARĘ", składa się tylko z trzech liter.
Główny problem związany z drzewami trie to wielkość pamięci, której potrzebują; znacząca jej część jest w zasadzie marnowana. Wiele węzłów może zawierać zaledwie kilka wskaźników różnych od NULL, cała ich reszta musi jednak i tak zajmować pamięć. Zmniejszenie rozmiaru niezbędnej pamięci stanowi więc palącą potrzebę.
Jednym ze sposobów zmniejszenia rozmiaru węzła jest zapisywanie tylko tych wskaźników, które są faktycznie używane, jak to widać na rysunku 9.30 [16]. Tak
#283
wprowadzona elastyczność, jeśli idzie o rozmiar każdego węzła, komplikuje jednak nieco implementację. Drzewa trie tego rodzaju można implementować w stylu 2-4 drzew. Wszystkie węzły będące braćmi można umieścić na liście dostępnej z ojca, jak na rysunku 9.31. Jeden węzeł poprzedniego drzewa trie odpowiada teraz liście. Oznacza to, że swobodny dostęp do wskaźników umieszczonych w tablicy nie jest już możliwy, a listy muszą być przeglądane sekwencyjnie, chociaż nie do końca, bo zapewne zostanie utrzymany porządek alfabetyczny. Zapotrzebowanie na pamięć nadal jest znaczące., ponieważ każdy węzeł zawiera teraz dwa wskaźniki, na które potrzeba dwa lub cztery bajty albo i więcej, zależnie od systemu.
Inną metodą redukcji wymagań pamięciowych jest zmiana sposobu sprawdzania słów [21]. Do drzewa trie a tergo (z łac.: od tyłu) są wstawiane słowa odwrócone. W naszym przykładzie liczba węzłów byłaby mniej więcej taka sama, ale drzewo trie a tergo reprezentujące takie słowa, jak "logged", "loggerhead", "loggia" i,Jogging", miałobyby liście na trzecim poziomie, a nie na siódmym, jak w zwykłym drzewie trie. Trzeba jednak przyznać, że dla pewnych często spotykanych końcówek, jak angielskie ,,tion", ,,ism", czy "ics", problem pojawiłby się znowu.

Rys. 9.30. To samo drzewo trie co na rysunku 9.29, ale z usuniętymi nie używanymi polami wskaźnikowymi
#284
Rys. 9.31. Drzewo trie z rysunku 9.31 zaimplementowane jako drzewo binarne
#285
Można jeszcze rozważać wiele innych wyborów kolejności; bardzo przydatne jest na przykład sprawdzanie co drugiego znaku [15], jednak problemu optymalnej kolejności nie da się rozwiązać w całej ogólności ze względu na jego ogromną złożoność [17].
Innym sposobem oszczędzania pamięci jest kompresja drzewa trie. W jednej z metod tworzy się jedną dużą tablicę ze wszystkich tablic w węzłach wewnętrznych, przeplatając je tak, by wskaźniki się nie nałożyły. Pozycje początkowe tych tablic są zapamiętane w tablicy pomocniczej. Na przykład trzy węzły pokazane na rysunku 9.32a, zawierające wskaźniki od pl do/?7 do innych węzłów drzewa trie (w tym liści), są kolejno umieszczane w jednej tablicy tak, by nie spowodować konfliktu, jak to widać na rysunku 9.32b. Powstaje pytanie, jak zrobić to efektywnie ze względu na czas i pamięć, tak by algorytm był szybki, a powstała tablica zajmowała istotnie mniej miejsca niż wszystkie węzły wewnętrzne w sumie. W naszym przykładzie na węzły potrzeba 3*6=18 komórek pamięci, a tablica zajmuje 11 komórek, współczynnik kompresji wynosi więc (18-11)/18, czyli 39%. Jeśli jednak umieścić węzły w sposób pokazany na rysunku 9.32c, to współczynnik ten wyniesie (18- 10)/18, a więc 44%.

Rys. 9.32. Część drzewa trie przed (a) i po (b) kompresji z użyciem algorytmu CompressTree ( oraz (c) po optymalnej kompresji
#286
Okazuje się, że algorytm służący do kompresuji drzewa trie jest wykładniczy ze względu na liczbę węzłów i nie daje się stosować do dużych drzew. Inne algorytmy mogą nie dawać optymalnego współczynnika kompresji, są jednak szybsze [14]. Jednym z takich algorytmów jest CompressTrie ().

CompressTrie()
wpisz wartość NULL do wszystkich NodeNum*CellNum komórek tablicy CellArray;
dla każdego węzła node
dla każdej pozycji j w tablicy CellArray
if po nałożeniu pól węzła node na komórki
CellArray[j], . . . , CellArray[j+CellNum-1] nie
naszły na siebie żadne komórki zawierające
wskaźniki
skopiuj wskaźniki z node do odpowiadających
im komórek, zaczynając od CellArray[j];
zapisz j w tablicy TrieNodes jako pozycję
węzła node w tablicy CellArray;
break;

Ten właśnie algorytm został zastosowany do drzewa trie z rysunku 9.32a w celu otrzymania tablicy na rysunku 9.32b. Przeszukiwanie tak skompresowanego drzewa trie jest bardzo podobne do przeszukiwania zwyczajnego drzewa trie. Dostęp do węzłów odbywa się jednak za pośrednictwem tablicy TrieNodes. Jeśli węzeł node_1 jest połączony z node_2, to trzeba odnaleźć pozycję node_2 w tej tablicy, a następnie można sięgać do pól węzła node_2 w tablicy CellArray.
Problem przy korzystaniu ze skompresowanego drzewa trie polega na tym, że poszukiwanie może wywieść nas na manowce. Na przykład poszukiwanie słowa zaczynającego się od litery P w drzewie trie na rysunku 9.32a zostałoby natychmiast przerwane, ponieważ pole wskaźnikowe odpowiadające tej literze w korzeniu jest równe NULL. Z kolei w skompresowanej wersji tego samego drzewa trie (rys. 9.32b) w polu odpowiadającym literze P znajduje się wskaźnik P_3 Błędna ścieżka zostałaby wykryta dopiero po późniejszym napotkaniu wskaźnika równego NULL lub, po osiągnięciu liścia, przy porównaniu klucza w tym liściu z szukanym.
Kolejnym sposobem kompresji jest utworzenie struktury zwanej C-trie, będącej bitową wersją zwykłego drzewa trie [19]. W metodzie tej węzły na jednym poziomie drzewa C-trie są umieszczane w kolejnych miejscach w pamięci, a adresy pierwszych węzłów na każdym poziomie są przechowywane w tablicy adresów. Informacja przechowywana w konkretnych węzłach pozwala na dostęp do synów tych węzłów przez obliczenie przesunięcia od nich do ich synów.
Każdy węzeł ma cztery pola: znacznik liść/węzeł wewnętrzny, pole z informacją, czy to koniec słowa (pełniące tę samą funkcję co nasz znak #), pole K składające się z CellNum bitów odpowiadających komórkom ze znakami oraz pole C zawierające łączną liczbę jedynek we wszystkich polach K węzłów na tym samym poziomie
#287
poprzedzających dany. Ta ostatnia liczba stanowi liczbę węzłów na następnym poziomie poprzedzających pierwszego syna danego węzła.
W liściach są przechowywane same klucze (albo ich sufiksy), jeżeli mieszczą się w polach K i C razem. Jeśli nie, to klucz jest umieszczany w osobnej tablicy, a liść zawiera wskaźnik do jego pozycji w tej tablicy. Do odróżnienia tych dwóch przypadków służy znacznik końca słowa. Fragment drzewa trie z rysunku 9.29 przedstawiony jako C-trie widać na rysunku 9.33. Wszystkie węzły są tego samego rozmiaru. Zakłada się, że liść może pomieścić do trzech znaków.

Rys. 9.33. Fragment reprezentacji drzewa trie z rysunku 9.29 jako C-trie

Aby wyszukać klucz w strukturze C-trie, trzeba bardzo uważnie wyliczać przesunięcia. Oto zarys algorytmu:

CTrieSearch(K)
for (i = 1, p = korzeń; ; i++)
if p jest liściem
if K jest równy kluczowi p
return sukces;
else return porażka;
else if (K[i] == '\0' )
if znacznik końca słowa jest włączony
return sukces;
else return porażka;
else if bit odpowiadający znakowi K[i] jest zerem
return porażka;
else p = adres pierwszego węzła na poziomie i+1
+ (pole C węzła p)*(rozmiar jednego węzła)
/* pomijamy wszystkich synów węzłów */
/* poprzedzających p na poziomie i */
+ (liczba jedynek w polu K węzła p na lewo od
#288
bitu odpowiadającego K[i]j*frozmiar \vezta);
/* pomijamy część synów p */

Aby na przykład znaleźć słowo "EERIE" w C-trie na rysunku 9.33 sprawdzamy najpierw w korzeniu bit odpowiadający pierwszej literze - ,,E"- Ponieważ jest on równy l, a korzeń nie jest liściem, idziemy na drugi poziom. Adres węzła do sprawdzenia na poziomie drugim wyznaczamy, dodając do adresu pierwszego węzła na tym poziomie długość jednego węzła, aby go przeskoczyć. Bit tego węzła wewnętrznego odpowiadający drugiej literze naszego słowa, również ,,E", jest równy l, idziemy więc na poziom trzeci. Adres węzła do sprawdzenia obliczamy, dodając do adresu pierwszego węzła na poziomie trzecim rozmiar jednego węzła (pierwszego węzła na poziomie trzecim). Dochodzimy teraz do liścia ze znacznikiem końca słowa równym 0. Sięgamy więc do tablicy słów, aby porównać przechowywany w niej klucz z szukanym.
Kompresja jest znaczna. Jeden węzeł pierwotnego drzewa trie o 27 dwubajto-wych wskaźnikach zajmuje 54 bajty. Na jeden węzeł struktury C-trie potrzeba 1 + 1+27 + 16 = 45 bitów, co można pomieścić w 6 bajtach. Nie dostajemy tego jednak za darmo. Algorytm wymaga umieszczania węzłów jednego poziomu ciasno obok siebie, a zapisywanie węzłów po jednym na raz z użyciem funkcji malloc () nie gwarantuje, że będą one znajdować się na sąsiadujących pozycjach, zwłaszcza w środowisku z wieloma użytkownikami. Węzły jednego poziomu muszą zatem być tworzone najpierw w tymczasowym pomocniczym obszarze, a dopiero potem można zażądać przydzielenia fragmentu pamięci dostatecznie dużego, aby pomieścić wszystkie te węzły. Problem ten pokazuje także, że struktura C-trie kiepsko nadaje się do dynamicznej aktualizacji. Jeśli drzewo trie jest tworzone tylko raz, to C-trie jest jego doskonale nadającym się do wykorzystania wariantem. Jeśli natomiast potrzebna jest częsta aktualizacja, to tę technikę kompresji drzewa trie należałoby wykluczyć.

9.3. Uwagi końcowe

Przegląd drzew wyższych rzędów w tym rozdziale nie jest w żadnym razie wyczerpujący. Liczba różnych rodzajów drzew wyższych rzędów jest ogromna. Naszą intencją jest zademonstrowanie rozmaitości zastosowań tych drzew oraz pokazanie, jak tego samego typu drzewa można użyć w różnych dziedzinach. Szczególnie interesujące jest B-drzewo wraz ze wszystkimi swoimi wariantami. B+-drzewa są powszechnie stosowane do implementacji indeksów we współczesnych relacyjnych bazach danych. Pozwalają one na bardzo szybki swobodny dostęp do danych, a również i na szybkie sekwencyjne przetwarzanie danych.
Zastosowania B-drzew nie ograniczają się do przetwarzania informacji z pamięci zewnętrznej, chociaż taka była pierwotna motywacja ich powstania. Wariant B-drzew, 2-4 drzewa, choć nie nadają się do przetwarzania informacji w pamięci zewnętrznej, okazują się być bardzo użyteczne w operowaniu danymi w pamięci głównej.
#289
Przydatne okazują się także drzewa trie, zupełnie inny rodzaj drzew. Istniejące w wielu wariantach, mają obszerny zakres zastosowań, a nasz przykład ilustruje właśnie takie bardzo praktyczne zastosowanie drzew trie.

9.4. Przykład: sprawdzanie pisowni

Niezbędnym narzędziem w każdym edytorze tekstu jest moduł sprawdzający pisownię, pozwalający użytkownikowi wychwycić tak wiele błędów, jak to możliwe. W zależności od stopnia wyrafinowania tego modułu użytkownik może nawet zobaczyć możliwe poprawne wersje. Moduły sprawdzające pisownię są stosowane głównie w środowisku interakcyjnym; użytkownik może wywołać je w dowolnej chwili w trakcie używania edytora, zrobić poprawki i przerwać nawet przed przetworzeniem całego pliku. Wymaga to napisania programu edytora i dodatkowo modułu sprawdzającego pisownię. W naszym przykładzie koncentrujemy się na wykorzystaniu drzew trie. Dlatego moduł sprawdzający pisownię będzie u nas samodzielnym programem przeznaczonym do zastosowania na zewnątrz edytora. Będzie też przetwarzał plik tekstowy w trybie wsadowym, nie dopuszczając poprawiania słowa po słowie po wykryciu ewentualnego błędu.
Sercem modułu sprawdzającego pisownię jest struktura danych umożliwiająca efektywny dostęp do słów ze słownika. Słownik taki będzie najprawdopodobniej zawierał tysiące słów, dostęp musi więc być bardzo szybki, aby można było przetwarzać tekst użytkownika w rozsądnym czasie. Spośród wielu możliwych struktur danych do reprezentowania słownika wybierzemy drzewo trie. Po uruchomieniu programu sprawdzającego pisownię najpierw jest tworzone drzewo trie, a następnie odbywa się samo sprawdzanie pisowni.
Gdy w słowniku jest duża liczba słów, rozmiar drzewa trie jest bardzo istotny, ponieważ powinno się ono mieścić w pamięci głównej, bez uciekania się do pamięci wirtualnej. Jak już widzieliśmy w tym rozdziale, drzewa trie o stałym rozmiarze węzła, jak na rysunku 9.29, są zbytnim marnotrawstwem, ponieważ zazwyczaj jedynie część spośród pozycji w każdym węźle jest wykorzystywana, a im dalej od korzenia, tym ułamek ten staje się mniejszy (korzeń może być jedynym węzłem mającym wszystkich synów). Tworzenie list odpowiadających wszystkim wykorzystywanym literom dla każdego węzła zmniejsza ilość marnowanej pamięci, jak na rysunku 9.31. Podejście to ma dwie wady: ilość pamięci niezbędnej na pola wskaźnikowe może być znaczna, a zastosowanie list wymusza użycie przeszukiwania sekwencyjnego. Ulepszeniem w stosunku do tego rozwiązania jest rezerwowanie tylko tyle pamięci, ile potrzeba w każdym węźle, bez uciekania się do użycia list. Idealnym rozwiązaniem byłaby tablica dynamiczna, tej struktury danych jednak w języku C brak. Użyjemy zatem tablic pseudodynamicznych, zastępując istniejące tablice większymi, kopiując zawartość starych tablic do nowych i zwracając stare systemowi operacyjnemu.
Kluczem do użycia owych tablic pseudodynamicznych jest implementacja węzła. Węzeł jest strukturą o czterech polach: znacznik liść/węzeł wewnętrzny, znacznik
#290
końca słowa, wskaźnik do napisu oraz wskaźnik do tablicy wskaźników do struktur tego samego typu. Na rysunku 9.34 widać drzewo trie o wierzchołkach będących takimi strukturami. Jeśli napis dowiązany do pewnego węzła ma zostać rozszerzony, to tworzony jest nowy napis, zawierający stary z nową literą wstawioną na właściwą pozycję; funkcję tę realizuje procedura AddCell ( ). Litery w każdym węźle są przechowywane w porządku alfabetycznym.
Funkcja Trielnsert ( ) jest implementacją algorytmu Trielnsert, omawianego wcześniej w tym rozdziale. Ponieważ położenie każdej litery może się zmieniać w zależności od węzła, jej pozycja musi być za każdym razem wyznaczana, co realizuje funkcja position ( ). Jeśli litery nie ma w węźle, to position ( ) zwraca wartość -l, co pozwala funkcji Trielnsert ( ) przedsięwziąć właściwą akcję.
Przy omawianiu drzew trie w tym rozdziale zakładaliśmy, że ich liście zawierają pełne klucze. Nie jest to potrzebne, ponieważ prefiksy wszystkich słów są niejawnie przechowywane w strukturze trie i mogą być odtworzone przez pozbieranie wszystkich liter na ścieżce prowadzącej do liścia. Aby na przykład dojść do liścia ze słowem "ERIE", trzeba przejść w dwóch węzłach wewnętrznych przez wskaźniki odpowiadające literom ,,E" i ,,R". Dlatego wystarczy przechowywać w liściu sufiks ,,IE" zamiast całego słowa "ERIE". Tak postępując, będziemy musieli zachować tylko 13 liter sufiksów słów w liściach wobec 58 liter przechowywanych we wszystkich liściach drzewa trie z rysunku 9.29 - jest to znaczące ulepszenie.
Zamieściliśmy także funkcję TrieSideView( ), wypisującą zawartość drzewa trie oglądanego z boku. Efekt działania tej funkcji zastosowanej do drzewa trie z rysunku 9.34 jest następujący:
>>REP |
>>REA | R
>>PI | ER
>>PER |
>>PEE | R
>>PEA | R
>>IR|E
>>IP|A
>>ERI | E
>>ERE |
>>ERA |
>>EI | RE
>>EE | RIE
>>AREA |
>>>ARE |
>>ARA|
>>>A|
Trzy symbole ,,>" oznaczają słowa, dla których w odpowiadającym im węźle został włączony znacznik EndOfWord. Słowa z dwoma symbolami ">" kończą się w liściach drzewa trie. Czasami liście te zawierają tylko znak '\0 '. Pionowa kreska oddziela prefiks odtworzony podczas przechodzenia drzewa trie od sufiksu odczytanego z liścia.
Sprawdzanie pisowni odbywa się w prosty sposób przez badanie każdego słowa z pliku tekstowego i wypisywanie wszystkich błędnych słów wraz z numerami wierszy, w których się znajdują. Rysunek 9.35 zawiera kompletny kod programu sprawdzającego pisownię.
#291
Rys. 9.34. Implementacja drzewa trie, w której wykorzystuje się tablice pseudodynamiczne. Drzewo trie zawiera te same słowa co trie z rysunku 9.29
#292
#include
#include
#include
#include

#define leaf 1 u
#def ine yes lu
#define success 1
#def ine NotFound -1

struct NonLeafRec {
unsigned int kind : 1;
unsigned int EndOfWord : 1;
char *letters;
struct NonLeafRec **ptrs;
};
typedef struct NonLeafRec *NonLeafPtr;

struct LeafRec {
unsigned int kind : 1; char *word;
};
typedef struct LeafRec *LeafPtr;

char *
strupr(char *s)
{ char *ss = s ;

while ( *s) {
*s = toupper(*s) ;
S++;
}
return ss;
}
void
TrieSideView (intdepth, NonLeafPtrp, char *prefix)
{ register int i ; /* założenie: korzeń nie jest liściem i nie jest równy NULL */

Rys. 9.35. Implementacja programu sprawdzającego pisownię z użyciem drzew trie
#293
if (p->kind == leaf) {
LeafPtr If= (LeafPtr) p;
for (i = 1; i <= depth; i++)
printf(" ");
printf ( " %s | %s\n" , prefix, lf->word) ;
}
else {
for (i =strlen(p->letters)-1; i >= 0 ; i--)
if(*(p->ptrs + i)){ /* dodaj do prefiksu */
pref ix[depth] = * (p->letters + i) ; /* literę odpowiadającą */
pref ix[depth+l] - ' \0 ' ; /* pożycji i*/
TrieSideView (depth+1, * (p->ptrs+i) , prefix) ;
}
if (p->EndOfWord == yes) {
pref ix[depth] = ' \0 ' ;
for (i = l; i <= depth+1; i++)
printf(" ");
printf (">%s \n", prefix) ;
}
}
}

position (NonLeafPtr p; char ch)
{ register int i;

for (i = 0 ; i < strlen (p->letters) && * (p->letters + i) !=ch; i++) ;
if (i < strlen(p->letters))
return i ;
else return NotFound;
}
SearchTrie (NonLeafPtr root, char *word)
{ NonLeafPtr p = root;
LeafPtr lf;
int pos ;

while (1)
if (p->kind == leaf) { /* węzeł p jest liściem, */
If = (LeafPtr) p; /* w którym powinien */
if ( ! strcmp (word, lf->word) ) /* znajdować się pasujący */
return success; /* sufiks słowa */
else return ! success;
}
else if (*word == NULL) /* koniec słowa powinien */
if (p->EndOffrJord == yes) /* odpowiadać znacznikowi */
return success; /* EndOfWord w węźle p */
else return Isuccess; /* ustawionemu na "tak" */

Rys. 9.35. Implementacja programu sprawdzającego pisownię z użyciem drzew trie (cd.)
#294
else if (* (p->ptrs + (pos = position (p, *word))}) {/* idź dalej */
p = *(p->ptrs + pos) ; /* ścieżką, jeśli można */
word++;
}
else return Isuccess; /* w przeciwnym razie porażka */
}
void
AddCell (char ch, NonLeafPtr p, int stop)
{ int i;
int len = strlen(p->letters) ;
char *s=p->letters;
NonLeafPtr *tmp =p->ptrs;
p->letters = (char *) malloc(len+2) ;
p->ptrs = (NonLeafPtr*) calloc (1,(len+1)*sizeof(NonLeafPtr) );
if (p->letters == NULL | | p->ptrs ==NULL) {
printf ( "brak pamięci 1\n" ) ;
exit(1);
}
if (stop < len) /* jeśli ch nie przypada po wszystkich literach w p ,
for (i = len; i >= stop+1; i--) { /* skopiuj z tmp litery > ch * /
*(p->ptrs + i) = *(tmp + i-1) ;
*(p->letters + i) = *(s+i-1) ;
}

*(p->letters + stop) = ch;
for (i = stop-l; i>=0; i--) { /* i litery < ch */
*(p->ptrs + i) = *(tmp + i) ;
*(p->letters + i) = *(s+i) ;
}
* (p->letters + len + 1) = ' \0 ' ;
free(s);
free(tmp);
}
CreateLeaf(char ch, char *suffix, NonLeafPtr p)
{ intpos= position (p , ch) ;
int len = strlen(p->letters) ;
LeafPtr If1 = (LeafPtr) malloc(sizeof (struct LeafRec)

lfl->kind = leaf;
lfl->word= (char*) malloc (strlen (suf f ix)+1 );
if (lfl==NULL | lf1->word == NULL) {
printf ( "brak pamięci 2\n" ) ;
exit(1) ;
}
strcpy(Ifl->word,suffix);

Rys. 9.35. Implementacja programu sprawdzającego pisownię z użyciem drzew trie (cd.)
#295
if (pos == NotFound) {
for (pos = 0; pos < len && * (p->letters + pos) < ch; pos++) ;
AddCell(ch,p,pos);
}
*(p->ptrs +pos) = (NonLeafPtr) If1;
}

NonLeafPtr
CreateNonLeaf (charch)
{ NonLeafPtr p = (NonLeafPtr) calloc(l,sizeof(struct NonLeafRec));

p->kind = lleaf;
p->EndOfWord = !yes;
p->ptrs = (NonLeafPtr *) calloc(l,sizeof(NonLeafPtr));
p->letters = (char *) malloc(2) ;
if (p==NULL p->ptrs == NULL | p->letters == NULL) {
printf ( " brak pamięci 3 \n " ) ;
exit(1);
}
* (p->letters) - ch;
*(p->letters+l) = '\0';
return p ;
}

Trielnsert (char *word, NonLeafPtr root)
{ NonLeafPtr p = root;
LeafPtr If2 ;
int offset, pos ;

while (1) {
pos = position(p,*word) ;
if ( *word ==NULL) { /* jeśli osiągnięto koniec słowa, */
p->EndOfWord = yes ; /* ustaw znacznik EndOfWord na "tak" */
return;
} /* jeśli pozycja w p wskazywana */
else if (pos == NotFound) { /* przez pierwszą literę słowa */
CreateLeaf(*word, word+1, p); /* word nie istniej e, utwórz liść */
return; /* i umieść w nim nie przetworzony */
} /* sufiks słowa */
else if (pos != NotFound && /* jeśli pozycja *word jest */
( * (p->ptrs + pos) ) ->kind == leaf) { /* zajmowana przez liść, */
lf2 = (LeafPtr) * (p->ptrs +pos) ; /* zachowaj go */
offset = 0;
/* utwórz tyle węzłów wewnętrznych, ile wynosi długość */
/* wspólnego prefiksu słowa word i napisu w liściu (dla */
/* komórki 'R', liścia 'EP' i słowa 'REAR' są tworzone */
/* dwa takie węzły) */

Rys. 9.35. Implementacja programu sprawdzającego pisownię z użyciem drzew trie (cd.)
#296
do {
pos =position(p,*(word+offset) ) ;
*(p->ptrs +pos) =CreateNonLeaf(*(word+offset+1) ) ;
P = * (p->ptrs + pos) ;
offset++;
} while (*(word + offset) == * (If2->word + offset - 1) ) ;
offset--;
CreateLeaf(*(word+offset+1) ,word+offset+2 , p) ;
if (*(If2->word+offset) == '\0' ) /* jeśli osiągnięto koniec */
/* słowa, dodaj znacznik */
p->EndOfWord=yes; /* EndOfWord do p */
/* w przeciwnym razie przydziel o jeden znak mniej na */
/* sufiks słowa */
else CreateLeaf(*(lf2->word+offset) , lf2->word+offset+1, p);
free(lf2->word);
free(lf2); return;
}
else {
p = * (p->ptrs + pos) ;
word++;
}
}
}

main()
{ FILE *FIn, *words;
char word[80], prefix[80]=" " ;
NonLeafPtr root;
int i, LineNum = 1, ch;

if ( (words = fopen( " words " , " r " ) ) ==NULL) {
printf( "nie mogę otworzyć pliku 'words' " ) ;
exit(1);
}
fscanf(words, " %s ",word) ;
strupr(word);
root = CreateNonLeaf (*word) ; /* nadaj początkową wartość korzeniowi, */
CreateLeaf(*word, word+1, root) ; /* aby uniknąć późniejszych sprawdzeń */
while (fscanf(words, " %s", word) == 1) {
Trielnsert(strupr(word), root);
}
TrieSideView(0,root,prefix);
if ( (Fin = fopen( "text" , "rb")) -=NULL) {
printf("nie mogę otworzyć pliku 'text' " ) ;
exit(1);
}

Rys. 9.35. Implementacja programu sprawdzającego pisownię z użyciem drzew trie (cd.)
#297
puts("Błędne słowa: " ) ;
ch = fgetc(FIn);
while (1) {
while (ch != EOF && ! isalpha ( (char) (ch) ) ) {
if ( (char) ch == '\n' )
LineNum-H-;
ch = fgetc(Fin) ;
}
if ( (char) ch == EOF)
break;
if (isalpha((char) ch) ) {
*word = (char) ch;
i = 1;
}
else i = 0 ;
while (isalpha((char)(ch = fgetc(Fin))))
*(word+i++) = (char) ch;
*(word+i) = '\0';
if (SearchTrie (root, strupr (word) ) !=success)
printf(" %s w wierszu %d\n" , word, LineNum)
}
fclose(words);
fclose(FIn);
}

Rys. 9.35. implementacja programu sprawdzającego pisownię z użyciem drzew trie (cd.

9.5. Ćwiczenia
1. Jaka jest maksymalna liczba węzłów w drzewie wysokości h?
2. Ile kluczy może pomieścić B-drzewo rzędu m i wysokości h?
3. Napisz procedurę wypisującą zawartość B-drzewa w porządku rosnącym.
4. Korzeń B^*-drzewa wymaga specjalnego traktowania, ponieważ nie ma on braci. W wyniku rozdzielenia nie otrzymamy dwóch węzłów wypełnionych w dwóch trzecich i nowego korzenia o jednym kluczu. Zaproponuj jakieś rozwiązanie tego problemu.
5. Czy kolejność napływających danych ma wpływ na kształt B-drzewa? Skonstruuj B-drzewa rzędu 3 (dwa klucze w węźle) najpierw dla ciągu 1, 5, 3, 2, 4, a następnie dla ciągu 1, 2, 3, 4, 5. Czy lepiej budować B-drzewa z danych uporządkowanych czy przemieszanych losowo?
6. Narysuj dziesięć B-drzew rzędu 3, mogących pomieścić 15 kluczy, i utwórz tabelę zawierającą dla każdego z tych drzew liczbę węzłów oraz średnią liczbę odwiedzanych węzłów [9]. Jakie wnioski uogólniające można z niej wysnuć? Czy tabela ta wskazuje, że: 1) im mniejsza liczba węzłów, tym mniejsza średnia liczba
#298
odwiedzonych węzłów i 2) im mniejsza średnia liczba odwiedzonych węzłów, tym mniejsza liczba węzłów? Na jakich własnościach B-drzew powinniśmy się skoncentrować, aby uczynić je bardziej efektywnymi?
7. We wszystkich naszych rozważaniach dotyczących B-drzew zakładaliśmy, że klucze się nie powtarzają. Nie musi tak jednak być, ponieważ wielokrotne wystąpienia tego samego klucza nie naruszają własności B-drzewa. Jeśli klucze te są związane z różnymi obiektami w pliku z danymi (np. kluczem jest nazwisko, a wielu ludzi może mieć takie samo nazwisko), to w jaki sposób zrealizowałbyś takie odwołania do danych?
8. Jaka jest maksymalna wysokość B^+-drzewa o n kluczach?
9. W prostym prefiksowym B+-drzewie może się zdarzyć, że separator będzie rozmiaru klucza w liściu. Jeśli na przykład ostatnim kluczem w jednym liściu jest słowo "Herman", a pierwszym kluczem w następnym liściu jest "Hermann", to jako separator w ojcu tych liści musiałoby zostać wybrane słowo "Hermann". Zaproponuj procedurę wymuszającą krótszy separator.
10. Napisz funkcję wyznaczającą najkrótszy separator dla dwóch kluczy w prostym prefiksowym B^+-drzewie.
11. Czy byłoby dobrym pomysłem używanie skróconych form prefiksów w liściach prefiksowych B^+-drzew?
12. Jeśli na dwóch różnych pozycjach i oraz j (i13. Jeśli klucz K_i zostaje usunięty z liścia drzewa bitowego, to trzeba zmienić D-bit między K_(i-1) a K_(i+1). Jaka będzie wartość tego D-bitu, jeśli wartości D_i i D_(i+1) są znane? Wykonaj operacje usunięcia klucza z liścia na rysunku 9.17 w celu postawienia hipotezy, a potem uogólnij tę obserwację. Przy dokonywaniu uogólnienia rozważ dwa przypadki: 1) D_jD_i+1.
14. Napisz algorytm znajdowania w liściach R-drzewa wszystkich prostokątów przecinających się z danym prostokątem R.
15. Dlaczego przy rozważaniach dotyczących B-drzew porównywalnych co do efektywności z drzewami poszukiwań binarnych mówi się tylko o B-drzewach małego rzędu, a nie dużego?
16. Jaki jest najgorszy przypadek wstawiania klucza do 2-4 drzewa?
17. Jaka jest złożoność algorytmu CompressTrie () w najgorszym przypadku?
18. Czy liście drzewa trie skompresowanego algorytmem CompressTrie () mogą nadal zawierać skrócone wersje słów, a ściślej części, które nie są zawarte w węzłach wewnętrznych?
19. W przykładach drzew trie analizowanych w tym rozdziale używanych było tylko 26 wielkich liter. W praktyce chcielibyśmy dopuścić także użycie małych liter. Niektóre słowa muszą jednak zaczynać się od wielkiej litery (nazwy własne), inne muszą być całe napisane wielkimi literami (akronimy). Jak możemy rozwiązać ten problem, nie umieszczając zarówno małych, jak i wielkich liter w węzłach?
#299
20. Wariantem drzewa trie jest drzewo cyfrowe, przetwarzające informację na poziomie bitów. Ponieważ istnieją tylko dwie wartości bitu, możliwe są jedynie dwa rozgałęzienia. Drzewa cyfrowe są więc binarne. Aby sprawdzić na przykład, czy słowo ,,BOOK" znajduje się w drzewie, nie porównujemy całej pierwszej litery ,,B", z kluczem w korzeniu, a jedynie pierwszy bit, równy O, pierwszej litery (ASCII(B) = 01000010). Na drugim poziomie porównujemy drugi bit i tak dalej, zanim dotrzemy do drugiej litery. Czy byłoby dobrym pomysłem użycie drzewa cyfrowego w programie sprawdzającym pisownię, takim jak omawiany wcześniej w przykładzie?

9.6. Zadania programistyczne

1. Rozbuduj program sprawdzający pisownię, aby sugerował także poprawną pisownię błędnego słowa. Rozważ następujące rodzaje błędów: zamiana kolejności liter (kopmuter), opuszczenie litery (komputr), dodanie litery (kompueter), powtórzenie litery (komputter) i zamianę litery (kompurer). Jeśli na przykład litera i została zamieniona z literą i+ l, to przez poziom / drzewa trie należy przejść po przejściu poziomu i+ 1.
2. Drzewo ćwiartek (ang. quadtree) to drzewo rzędu 4 stosowane do reprezentowania punktów na płaszczyźnie [23]. Węzeł zawiera parę współrzędnych (szerokość, długość} i wskaźniki do czterech synów reprezentujących cztery ćwiartki: NW,
NE, SW i SE. Ćwiartki te powstają przez przecięcie pionowej i poziomej linii przechodzących przez punkt płaszczyzny (szer, dl). Napisz program odczytujący nazwy miast i ich położenia geograficzne (szer, dl) oraz wstawiający je do drzewa ćwiartek. Następnie program powinien podać nazwy wszystkich miast leżących w odległości d od punktu (Szer, Dl) albo od danego miasta C.
Na rysunku 9.36 jest przedstawiony przykład. Miejsca na mapie (rys. 9.36a) są wstawiane do drzewa ćwiartek (rys. 9.36b) w kolejności numerów w kółeczkach przy nazwach miast. Przy wstawianiu do drzewa ćwiartek na przykład miejscowości Pittsburgh sprawdzamy, w jakim kierunku znajduje się ona względem korzenia. W korzeniu są zapisane współrzędne Louisville, a Pittsburgh jest od niego na północny wschód, czyli należy do drugiego syna korzenia. Syn ten zawiera miasto Washington. Zadajemy więc to samo pytanie dotyczące położenia Pittsburgha względem bieżącego węzła, drugiego syna korzenia. W jakim kierunku względem niego leży Pittsburgh? Tym razem odpowiedzią jest północny zachód. Idziemy więc do pierwszego syna bieżącego węzła. Jest on równy NULL, tutaj zatem można wstawić węzeł Pittsburgh.
3. Na rysunku 9.29 jest widoczne pewne źródło nieefektywności drzew trie: ścieżka do słów ,,REAR" i "REP" prowadzi przez węzeł mający tylko jednego syna. Przy dłuższych powtarzających się prefiksach liczba takich węzłów może być większa. Zaimplementuj program sprawdzający pisownię, wykorzystujący wariant drzewa trie, zwany drzewem Patricia(Drzewo Patricia było pierwotnie binarne, a sprawdzenia były wykonywane na poziomie bitów.) wyższego rzędu [20], w którym ścieżki drzewa trie zostają skrócone przez pozbycie się węzłów o jednym synu. Robi się to, zapisując przy każdym rozgałęzieniu informację, ile znaków należy opuścić przed dokonaniem sprawdzenia. Na przykład drzewo trie z rysunku 9.37a przekształcono w drzewo Patricia pokazane na rysunku 9.37b. Ścieżki wiodące do czterech słów o prefiksie "LOGG" skracają się za cenę zapisania w każdym węźle liczby znaków do pominięcia, poczynając od bieżącej pozycji w napisie. Obecnie, ze względu na to, że niektóre znaki w ogóle nie były sprawdzane podczas wędrówki wzdłuż ścieżki, ostateczne porównanie należy wykonać między szukanym kluczem a całym kluczem znajdującym się w liściu.
#300
Rys. 9.36. Mapa pokazująca współrzędne kilku miast (a) oraz drzewo ćwiartek zawierające tę samą informację (b)
#301
Rys. 9.37. Drzewo trie zawierające słowa o długich wspólnych prefiksach (a) oraz drzewo Patricia zawierające te same
słowa (b)
#302
Bibliografia

B-drzewa

[I] Bayer R.: Symmetric binary B-trees: Data structures and maintenance algorithms. Acta Informatica, 1972, l, s. 290-306.
[2] Bayer R., McCreight E.: Organization and maintenance of large ordered indexes. Acta
Informatica, J 972, l, s. 173-189. [3] Bayer R., Unterauer K.: Prefix B-trees. ACM Transactions on Database Systems, 1977,
2, s. 11-26.
[4] Comer D.: The ubiąuitous B-tree. Computing Surveys, 1979, 11, s. 121-137. [5] Ferguson D.E.: Bit-tree: A data structure for fast f ile processing. Communications of the
ACM, 1992, 35, No. 6, s. 114-120. [6] Folk M.J., Zoellick B.: File structure: A conceptual toolkit. Reading, MA, Addison-Wes-
ley 1987, Chs. 9, 10. [7] Guttman A.: R-trees: A dynamie index structure for spatial searching. ACM SIGMOD'84
Proc. of Annual Meeting, SIGMOD Record, 1984, 14, s. 47-57 (także Stonebraker M.
(ed.): Readings in database systems. San Mateo, CA, Kaufmann 1988, s. 599-609.) [8] McCreight E.M.: Pagination of B*-trees with variable-length records. Communications of
the ACM, 1977, 20, s. 670-674. [9] Rosenberg A.L., Snyder L.: Time- and space-optimality in B-trees. ACM Transactions on
Database Systems, 1981, 6, s. 174-193. [10] Sedgewick R.: Algorithms. Reading, MA, Addison-Wesley 1988, Ch. 15.
[II] Sellis T., Roussopoulos N., Faloutsos C.: The R+-tree: A dynamie index for multi-di-mensional objects. Proceedings of the J3th Conference on Very Large Database, 1987, s. 507-518.
[12] Stonebraker M., Sellis T., Hanson E.: Analysis of rule indexing implementations in data base systems. Proceedings of the First International Conferecne on Expert Database Systems, Charleston 1986, s. 353-364.
[13] Yao A.C.C.: On random 2-3 Trees. Acta Informatica, 1978, 9, s. 159-170.
Drzewa trie
[14] Al-Suwaiyel M., Horowitz E.: Algorithms for trie compaction. ACM Transactions on
Database Systems, 1984, 9, s. 243-263. [15] Bourne C.P., Ford D.F.: A study of methods for systematically abbreviating English words
and names. Journal of the ACM, 1961, 8, s 538-552. [16] de la Briandais R.: File searching using variable length keys. Proceedings of the Western
Joint Conference, 1959, s. 295-298.
#303
[17] Comer D., Sethi R.: The complexity of trie index construction. Journal ofthe ACM, 1977,
24, s. 428-440.
[18] Fredkin E.: Trie memory. Communications of the ACM, 1960, 3, s. 490-499. [19] Mały K.: Compressed tries. Communications ofthe ACM, 1976, 19, s. 409-415. [20] Morrison D.R.: Patricia trees. Journal ofthe ACM, 1968, 15, s. 514-534. [21] Rotwitt T., de Maine P.A.D.: Storage optimization of tree structured files representing
descriptor sets. Proceedings ofthe ACM SIGFIDET Workshop on Data Description, Acces
and Control. New York 1971, s. 207-217.
Drzewa ćwiartek
[22] Finkel R.A., Bentley J.L.: Quad trees: A data structure for retrieval on composite keys.
Acta Informatica, 1974, 4, s. 1-9. [23] Samet H.: The design and analysis of spatial data structures. Reading, MA, Addison-
-Wesley 1989.