microgeek.eu

Drzewa binarne

Chcąc ocalić od zapomnienia. Garść dywagacji na temat drzew binarnych.https://www.youtube.com/watch?v=2oANV6SQhwI

Jest taki wynalazek, który nazywa się drzewa binarne. Przymiotnik „binarne” symbolizuje to, że każdy element drzewa ma dwóch potomków (synów czy córek). To dosyć wygodna struktura pozwalająca na usystematyzowanie (uporządkowanie) czegoś. Oczywiście zastosowań tego algorytmu można zaproponować całe multum. Bazując na tym algorytmie realizowałem pierwsze rozwiązania z tematu baz danych. Jednak zanim zagłębię się w to zagadnienie, w pierwszej kolejności przedstawię kilka dywagacji i rozważań na temat algorytmu. Te eksperymenty będą oparte o zmienne wskaźnikowe lokowane w pamięci programu. Struktura elementu drzewa (Node) w najprostszym rozwiązaniu pokazana jest na rysunku:

tree01-01.png

gdzie:

• Klucz – jest porządkowaną informacją, w przykładach jest to liczba, w ogólnym przypadku może być to dowolna informacja, dla której można określić funkcję komparującą, funkcję do porównywania treści kluczy, która daje wynik: równy, mniejszy lub większy.
• Link w lewo – jest wskazaniem na kolejny element drzewa, który zawiera klucze mniejsze od aktualnego (zawartego w określonym elemencie drzewa),
• Link w prawo – jest wskazaniem do kolejny element drzewa, który zawiera klucze większe od aktualnego.

W prezentacji będą używane liczby jako klucze, dla których prosto realizuje się funkcję porządkującą: liczba może być mniejsza od innej, większa od innej lub równa. Równie dobrze w roli klucza można zastosować dowolne łańcuchy znaków, dla których można zaproponować funkcję porządkującą odzwierciedlającą kolejność alfabetyczną.
Z drzewem związany jest element będący szczytem (początkiem) drzewa. Czasem można napotkać określenie: korzeń. To trochę przypomina dywagację filozoficzną, gdyż korzeń to z reguły rośnie w ziemi a szczyt drzewa ucieka „do nieba” w kosmos. Jakkolwiek by to nazywać, znaczenie tego jest takie, że wskazuje na pierwszy element struktury drzewa.
Program ilustrujący jest w Lazarus (Pascal).
Rozpatrzmy taki typ:i zmienną:Podstawienie:oznacza, że drzewo symbolizowane zmienną TopTree jest puste (nie zawiera żadnego elementu). Wszelkie operacje na drzewach najprościej implementują się w oparciu o algorytmy rekurencyjne. Rozpatrzmy procedurę budującą drzewo:Procedura dodaje nowy klucz (reprezentowany przez parametr Key) do drzewa (reprezentowanego przez parametr NodeEntry). Istotnym elementem jest to, że wskaźnik do drzewa musi być parametrem z zaklęciem var, procedura dodania elementu drzewa dodając modyfikuje wskaźniki, które muszą być „widoczne” na zewnątrz. Algorytm jest rekurencyjny a jego realizacja jest operacją poszukiwania z ewentualnym wstawieniem nowego elementu. Nowy element zawsze doda się na końcu gałęzi drzewa, czyli rekurencyjnie należy dokręcić się do takiego miejsca, gdzie bieżący wskaźnik elementu drzewa jest nil. Jeżeli bieżący element istnieje (jest różny od nil), to należy odpowiednio (w ogólnym przypadku w wyniku zastosowania funkcji porządkującej) przeszukać lewe (reprezentowane przez dziecko LeftLink) lub prawe (reprezentowane przez dziecko RightLink) poddrzewo. Tu, dla uproszczenia nie jest rozpatrywana kwestia duplikatów, dodania elementu już istniejącego (gdzie funkcja porządkująca da wynik: równy, o czym będzie później).
Rozpatrzmy ciąg wywołań:Po wstępnym podstawieniu TopTree:=nil drzewo jest puste i pierwsze rekurencyjne wywołanie AddKey ( 8 , TopTree ) ; utworzy element. Utworzony element „doczepi się” do zmiennej TopTree (parametr w wywołaniu funkcji dodania klucza jest typu var).Po pierwszym wywołaniu będzie:

tree01-02.png

Kolejne wywołanie: AddKey ( 4 , TopTree ) ; zauważy, że nowododawany klucz (4) jest mniejszy od aktualnego (8), więc dojdzie do rekurencyjnego wywołania z potomkiem LeftLink. Ponieważ ten jest równy nil, utworzy się nowy element, który doczepi się jako potomek LeftLink. Po akcji będzie:

tree01-03.png

Po kolejnej akcji, drzewo przyjmie postać:

tree01-04.png

Po kolejnej serii wywołań:Drzewo wygląda następująco:

tree01-05.png

Ostatecznie:

tree01-06.png

Tu muszę się przyznać, że przykład dobrany jest tendencyjnie, by wszystko wyszło „ładnie”. Niestety nie zawsze jest tak pięknie i cudownie, co wymaga trochę trudu by doprowadzić do takiego stanu (będzie o tym dalej).
Rozpatrzmy inny ciąg wywołań procedur realizujących budowanie drzewa.Doprowadzi on do następującego efektu:

tree01-07.png

W tym wypadku doświadczymy pewnej przykrości: drzewo binarne zredukowało się do listy liniowej. Ma to dosyć istotny wpływ na optymalność rozwiązania pod każdym względem:

• algorytm musi się głębiej wkręcać rekurencyjnie, co odbija się na wielkości wymaganego stosu,
• koszt poszukiwania elementu jest proporcjonalny do liczby elementów (w przypadku „pięknego drzewa”, koszt jest proporcjonalny do logarytmu przy podstawie 2 z liczby elementów).

Jednak nie ma co płakać nad rozlanym mlekiem. Na każdą koncepcję można zaproponować anykoncepcję. Również w tym przypadku da się coś zaradzić na tą przypadłość (ale to w dalszej części). Bez względu na optymalność ostatecznej postaci drzewa, która rzutuje jedynie na koszty operacyjne, podstawowe akcje są następujące:
Poszukiwanie elementu w drzewie:Funkcja poszukująca zwraca wskaźnik do znalezionego elementu (jeżeli został znaleziony). Jeżeli aktualny wskaźnik jest pusty (NodeEntry = nil), to oznacza, że poszukiwany element nie występuje w drzewie (dotarliśmy do granic galaktyki i nie natrafiliśmy na poszukiwany element). W przeciwnym wypadku (element drzewa istnieje), to są dwa wyjścia: albo został znaleziony (to zwracany jest jako wynik funkcji wskaźnik do tego elementu) albo nie: należy odpowiednio przeszukać lewe lub prawe poddrzewo. Zagadnienie ma charakter fraktalny: z każdego punktu widzenia wygląda identycznie.
Równie prosto jest realizowana operacja usunięcia całego drzewa. Rekurencyjny algorytm, z każdego punktu można interpretować następująco: usuń lewe poddrzewo, usuń prawe poddrzewo i usuń się sam.
Wydruk całego drzewa: nic prostszego:sprowadza się do: wydrukuj lewe poddrzewo (elementy uporządkowane młodsze), wydrukuj siebie i wydrukuj prawe poddrzewo (elementy uporządkowane starsze). W wyniku mamy uporządkowany ciąg elementów bez względu na kolejność wkładania. Wkładanie to ważna rzecz: w różny sposób tworzą się dzieci (jak było widać wyżej). Tu taka ciekawostka, zamieniamy kolejność rekurencyjnych wywołań: w pierwszej kolejności link w prawo, na koniec rekurencyjne wywołanie z linkiem w lewo. Uzyskamy wynik uporządkowany w przeciwną stronę: jak niewielka zmiana w algorytmie może mieć daleko idące skutki finalne.

Z podstawowych operacji pozostało usunięcie określonego elementu z drzewa, ale to już w innym odcinku.
Dla tropicieli (Lazarus):

Pięknie wytłumaczone... Ciekawe,bo dzisiaj akurat rozważałem zaprojektowanie kilka algorytmów do bardziej efektywnej komunikacji (dla ATTiny), które bazują niejako na wykorzystaniu drzewa binarnego. Niejako,no bo nie tylko na tym.
Bardzo spodobało mi się to wytłumaczenie,więc cierpliwie poczekam na dalszy ciąg tego tutoriala (algorytm usuwania WYBRANYCH węzłów drzewa), bo wtedy posiada się prawie gotową, bardzo wydajną metodologię postępowań do już praktycznego wykorzystania tego w/w wspaniałego algorytmu. A jest z czego korzystać... Znajomość postępowania z drzewami binarnymi bardzo przydaje się wraz z algorytmem kodowania Huffman'a,czy tzw.kodem liczbowym Gray'a, które to algorytmy mają już praktyczne, wymierne przełożenie na efektywność jakiegoś algorytmu do komunikacji. Np. żeby ograniczyć liczbę znaków alfanunerycznych, które to z kolei kodują rozkazy wykorzystane we wspomnianym przeze mnie algorytmie komunikacyjnym, (np.SND, RCV, ACK... etc.) można -wg metodologii postępowania z kodem Huffman'a- pogrupować te rozkazy w hierarchii od najczęściej do najrzadziej używanych, a żeby zwiększyć efektywność inkrementacji/dekrementacji przy odliczaniu zastosować kod Gray'a.
Kibicuję i czekam niecierpliwie na dalszą część tego tutoriala!
Pozdrawiam! J23

j23 pisze:Kibicuję i czekam niecierpliwie na dalszą część tego tutoriala!

No wiesz Jarku, robię co mogę. Trochę trzeba uzbroić się w cierpliwość, najwięcej czasu zajmują mi rysunki

a te rysunki w jakimś graficznym narzędziu, czy "nakodzone" w dot?

dambo pisze:a te rysunki w jakimś graficznym narzędziu, czy "nakodzone" w dot?

Wygooglaj sobie "Inkscape".

Usuwanie elementów z drzewa binarnego

Nutahttps://www.youtube.com/watch?v=pjyFydbgBG4

O ile dodawanie elementów do drzewa jest dosyć prostą operacją, o tyle usunięcie już takie nie jest. W sytuacjach bardziej złożonych trzeba się trochę natrudzić. Wymaga to rozpatrzenia dwóch wariantów: gdzie element drzewa ma dwóch potomków oraz gdzie element ma jednego potomka (wariant braku jakiegokolwiek potomka można rozpatrywać jako przypadek szczególny jednego potomka). Zacznijmy od wariantu prostego (by nie rzec trywialnego): usuwany element drzewa nie ma żadnego potomka. Usuwamy końcowy element w gałęzi (przykładowo usuwamy klucz 5).

tree02-01.png

W elemencie nadrzędnym w odpowiednim linku wstawiamy nil, przez co usuwany element przestaje być elementem drzewa (nikt na niego nie wskazuje). Po odwiązaniu go od struktury drzewa można go fizycznie unicestwić. Zagadnienie jest symetryczne (w znaczeniu link w lewo lub w prawo).

tree02-02.png

Również mało skomplikowanie jest realizowana operacja usunięcia w przypadku, gdy element ma jednego potomka. Potomek usuwanego elementu zastąpi sam element, który w ten sposób staje się elementem spoza struktury.

tree02-03.png

Zagadnienie jest lustrzano-symetryczne.

tree02-04.png

Znacząco bardziej skomplikowane jest usunięcie elementu z dwoma potomkami.

tree02-05.png

Pozbądźmy się przykładowo elementu 4. W takim przypadku należy usuwany element niejako zastąpić innym. Tego innego, rzecz jasna należy odpowiednio znaleźć. Można (patrząc na drzewo z punktu widzenia usuwanego elementu) odnaleźć element, który nie ma prawego potomka zaczynając od lewej gałęzi. Sprowadza się to do pójścia prawą krawędzią do odpowiedniego elementu, ale pierwszy krok jest w lewo (w tym przypadku znaleźć element 3).

tree02-06.png

Przepisać dane użytkowe (w tym przypadku jedynie klucz).

tree02-07.png

Przepisać lewego potomka do elementu nadrzędnego (pamiętamy, że znaleziony element nie ma prawego potomka).

tree02-08.png

W elemencie 3 również jest brak lewego potomka. Jednak w sytuacji, gdyby on istniał, zostanie zachowany jako dziecko innego rodzica. Po wykonanych roszadach, do fizycznego uwalenia jest inny element niż się spodziewaliśmy. Teraz do utłuczenia jest element, z którego zostały „odessane” dane.

tree02-09.png

Kontynuując rozważania w zakresie struktur danych, procedura usuwania wygląda następująco:Algorytm, jest jak można się spodziewać, realizacją rekurencyjną. W klasyczny sposób poszukiwany jest element do usunięcia. Po jego znalezieniu rozpatrywane są konieczne warianty: czy usuwany element ma dwoje dzieci czy mniej. Jeżeli występują dwa potomki, to uruchamiana jest pomocnicza procedura do przebudowy drzewa (również rekurencyjna).
Jakby nad tym wszystkim trochę pomyśleć, to można zauważyć, że zastosowany sposób przebudowy drzewa wynikający z usunięcia elementu z dwoma potomkami nie jest jedynym rozwiązaniem. Równie skutecznym może być wariant, gdzie poszukuje się elementu nie mającego lewego potomka, jednak pierwszy krok jest zrealizowany w prawą stronę. Zagadnienie jest lustrzane. Rozpatrując to z innej strony, przy usuwaniu elementu 4 z drzewa, zostałby on zastąpiony elementem 5. Różnica, poza faktem migracji innych elementów, nie ma żadnego znaczenia.
Program ćwiczebny ma możliwość wydrukowania postaci drzewa. Wyżej opisany bardziej złożony wariant w wynikach generowanych przez program wygląda następująco:

tree02-10.png

Z pięknego drzewa (z czerwonymi linkami), usuwany jest element 4. Zaszła tu reorganizacja struktury i przetasowania. Wyniki prezentuje fragment z niebieskimi linkami.
W operacjach usuwania elementów drzewa występuje pewne zjawisko, które najprościej ujmując można określić jako migracja: czasami element zmienia miejsce „zamieszkania” (jak było widać w przypadku elementu 4). W pewnych specyficznych zastosowaniach ta cecha może okazać się niepożądaną, w innych może nie mieć znaczenia. To wszystko zależy od zastosowania.
Dla tropicieli:

Drzewa binarne równoważone

Nutahttps://www.youtube.com/watch?v=EHhnD6QZUi0

Jak dało się wyżej zauważyć, normalne drzewa binarne mają jedną istotna wadę: w niekorzystnych przypadkach redukują się do listy liniowej. Na taka przypadłość jest odpowiednie lekarstwo: równoważenie drzewa binarnego. Drzewo jest traktowane za zrównoważone, jeżeli z każdego jego węzła długość lewej i prawej gałęzi nie różni się więcej niż o 1. To zmusza do przechowywania w każdym jego węźle aktualnego stanu zrównoważenia i po każdej akcji, która może doprowadzić do destabilizacji drzewa (każde dodanie lub usunięcie elementu) odpalana jest akcja łapania równowagi. To oznacza, że struktura węzła musi zostać rozbudowana:Status niezrównoważenia jest informacją trzywartościową określającą stan równowagi przed operacją wstawienia. Na ilustracjach będzie symbolizowany przez:

• = (State1) → poprzednie niezrównoważenie zostało usunięte,
• < (State2) → środek ciężkości został przesunięty,
• ! (State3) → wymagane jest ponowne równoważenie.

Rozpatrzmy przypadek drzewa pustego, do którego dodany zostaje element 1.

tree03-01.png

Zostaje dodany element 2.

tree03-01a.png

Jest to drzewo zrównoważone. Z punktu widzenia elementu 2 obie gałęzie są tej samej długości (zerowej → równej). Z punktu widzenia elementu 1, drzewo jest również zrównoważone, gdyż długość lewej gałęzi (=0) nie różni się od długości prawej gałęzi (=1) o więcej niż 1. „Normalne” dodanie kolejnego elementu do drzewa doprowadzi do stanu drzewa niezrównoważonego. Stan przed akcją równoważenia pokazuje rysunek.

tree03-02.png

Operacja równoważenia polega na przeniesieniu środka ciężkości gałęzi, taki specyficzny obrót. Po dodaniu elementu 3 (z punktu widzenia elementu 2) zmieniły się długości gałęzi. Wycofując się z rekurencji, algorytm dojdzie do elementu 1. Ponieważ zmieniła się długość drzewa, oraz wskaźnik zrównoważenia jest ! → zostaje uruchomiona dla tego elementu akcja równoważenia.

tree03-03.png

Odpowiednie wskaźniki ulegają zmianie.

tree03-04.png

tree03-05.png

Ostatecznie:

tree03-06.png

Algorytm dodania elementu z kluczem do drzewa wraz z równoważeniem jest następujący:Dotychczasowy najbardziej upierdliwy przypadek (dodanie kluczy już uporządkowanych), przy zastosowaniu algorytmu równoważenia wychodzi najbardziej cudownie.

tree03-07.png

Pozostałe operacje (poszukiwanie, usunięcie całego drzewa) są identyczne. Usuwanie pojedynczego elementu, jak można się spodziewać, również jest bardziej złożone, ale o tym później.

Trochę testów RANDOM

Z nutąhttps://www.youtube.com/watch?v=FF1mh1wqFwg

Często tak się zdarza, że "ładnie" dobrane dane nie są w stanie zmusić program by przeszedł każdą swoją ścieżkę. Bo przykładowo, dodawanie kluczy już uporządkowanych w sposób monotoniczny, zmusza program do błądzenia ciągle po tych samych ścieżkach programu. By doświadczyć każdej możliwej drogi, to dobrym rozwiązaniem jest wygenerowanie danych w "losowej" kolejności. Napisałem "losowej" z uszkami, bo sama losowość jest w dużym stopniu również iluzoryczna. Nie miej potraktujmy, że poniższa sekwencja dodawania kluczy do drzewa jest losowa.
Po każdej operacji dodania "drukowałem" do pliku postać drzewa. Nie ma sensu przeglądać wszystkich stanów pośrednich, niemniej warto przyjrzeć się efektowi końcowemu. Po dodaniu 63 kluczy w kolejności "losowej" drzewo wygląda... jak wygląda. Cóż, rysunek siłą rzeczy musi być szeroki.

tree04-01.png

Rozpatrując jego fragmenty zawsze można dostrzec, że jest zrównoważone. Wszędzie w obrębie jakiegokolwiek prostokąta długość lewej i prawej gałęzi nie różni się więcej niż o 1.

tree04-02.png

tree04-03.png

Usuwanie elementów z drzewa wyważonego

Szczyty górhttps://www.youtube.com/watch?v=QFlcs8vwLK4

W swej podstawowej formie usuwanie elementów z drzewa wyważonego nie różni się od usuwania z drzewa nierównoważonego. Przypadek usunięcia elementu końcowego (który nie ma już potomków) podobnie jak w drzewie nierównoważonym jest trywialny. Po usunięciu elementu długość gałęzi ulega zmianie, co czasami rodzi potrzebę przerównoważenia całej reszty. Identycznie realizowane jest usunięcie elementy mającego jednego potomka. Jeden potomek tworzy lokalną listę liniową (minimum 2-elementową), więc usunięcie nie należy do operacji zbyt skomplikowanych. Również zmianie ulega długość gałęzi drzewa, więc ten fakt może być wyzwalaczem do akcji, której zadaniem jest przeniesienie środka ciężkości całego poddrzewa. Najbardziej złożony przypadek, w którym usuwany element ma dwóch potomków realizowany jest podobnie jak w drzewie nierównoważonym. Akcja polega na wyszukaniu elementu w poddrzewie, które przypięte jest do usuwanego elementu, który nie ma dwóch potomków. Po znalezieniu takiego elementu następuje akcja zamiany miejsc odpowiednich elementów, taka akcja migracyjna.
Mając to na uwadze, szczegóły koncepcyjne zostały już opisane wyżej: zarówno proces usuwania jak i równoważenia polegający na specyficznym rodzaju obrotu. Naturalnie ten obrót może nastąpić w lewą lub w prawą stronę w zależności od aktualnego rozkładu „masy drzewa”.Ilustracją działania powyższego algorytmu może być poniższy rysunek. Zrealizowane działania są dziełem programu.

tree05-01.png

Dla tropicieli:

Problem duplikatów - zastosowanie drzewa

W dotychczasowych rozważaniach nie była poruszana kwestia duplikatów. Tak nazywam operację związaną z akcją programu w sytuacji, gdy w dodając nowy element do drzewa okazuje się, że taki już istnieje. Konkretne rozwiązanie zależy od zastosowania. Przykładowo, w problemie zasygnalizowanym przez J23 wystarczyłoby (tak sądzę) jedynie posiadanie w elemencie struktury drzewa pola o charakterze licznika, który w przypadku znalezienia duplikatu byłby inkrementowany. O ile dobrze zrozumiałem jego zagadnienie, problem polega na zliczeniu wystąpień określonych znaków.
Rozpatrzmy jako przykład zagadnienie bardziej złożone, które polega na zgromadzeniu informacji o każdym wystąpieniu elementu „godnego uwagi” w jakimś pliku tekstowym. Do interesujących elementów zaliczam słowa, liczby oraz napisy (ciągi znaków ujęte w apostrofy). Pozostałe element składniowe, jakie mogą wystąpić w pliku nie zaprzątają mojej uwagi (znaki interpunkcyjne, plusiki, minusiki itp.). Interesuje mnie każde wystąpienie wymienionych elementów. Jak wiadomo, liczba możliwych elementów → nieznana. Liczba wystąpień każdego elementu → nieznana. Do „pamiętania” zostanie zaprzęgnięte drzewo binarne. Ten algorytm pozwala szybko lokalizować elementy będące w obszarze mego zainteresowania. Dodatkowo, końcowy wynik, jest uporządkowany alfabetycznie → nie będzie wymagał sortowania.
To wymaganie (notowania każdego wystąpienia) sugeruje, że do każdego elementu drzewa musi zostać podczepiona lista wskaźnikowa wystąpień. Strukturę elementu drzewa pokazuje rysunek:

tree06-01.png

Ze względu na zastosowanie drzew równoważonych w strukturze występuje wskaźnik zrównoważenia. Klucz Key jest stringiem 20-znakowym (dotychczas były ćwiczone liczby). Wskaźniki w lewo i w prawo mają typowe znaczenie. Dochodzi pole przeznaczone na „katalog biblioteczny” → wskazania, gdzie dany element występuje w pliku. Liczba wystąpień jest nieokreślona, więc całość będzie przechowywana jako lista liniowa. Taka lista zawiera ważne dane oraz wskazanie na kolejny element zawierający zgromadzone informacje. Komentarze i ich zawartość jest pomijana.
Program ilustrujący rozwiązanie jest... jaki jest. Zdaję sobie sprawę, że ma wady, ale nie to jest obecnie najważniejszym celem. Celem jest pokazanie sposobu rozwiązania. Na końcu dołączam aktualną postać programu, jak ktoś ma ochotę, może pójść moimi śladami i pociągnąć sprawę dalej.
Reasumując, struktury danych są następujące:Szczyt drzewa jest reprezentowany przez:Dodanie elementu ulega pewnej modyfikacji związanej z realizowaną funkcjąPierwsze wystąpienie elementu drzewa (przypadek: NodeEntry = nil) tworzy element drzewa oraz odnotowuje lokalizację gdzie określony element się znajduje. Kolejne wystąpienie (ostatni wariant ciągu if … else) to jedynie podczepienie kolejnego wystąpienia do istniejącej już listy.
Z punktu widzenia rozważań drzewiastych, siłą rzeczy rozbudowie musi ulec również operacja zwolnienia całego drzewa. Ze względu na obciążenie każdego elementu drzewa listą liniową, przed dezintegracją każdego elementu, konieczne staje się usunięcie całej listy. Ta operacja występuje zarówno w przypadku usunięcia całego drzewa, jak i pojedynczego jego elementu (przed „ubiciem” elementu węzła drzewa, należy usunąć listę liniową, jak się o tym zapomni, to zostaną bezpowrotnie stracone [dla programu] obszary pamięci).
Pozostałe operacje typowe dla rozwiązań drzewiastych nie ulegają zmianie. Wszelkie zachodzące modyfikacje właściwie należy interpretować jako „coś odnoszące się do siebie”. Przykładowo, przed akcją „usuń siebie” jest wykonana akcja „usuń listę wystąpień”. Podobnie ma się sprawa dotycząca wydrukowania zawartości drzewa. Algorytm jest rekurencyjny, jak w dotychczasowych rozwiązaniach. Natomiast akcja, którą można określić jako „drukuj siebie” jest nieco rozbudowana.Eksperymentując na sobie (program przetworzył sam siebie), uzyskuje się następujący wynik (plik zawiera ponumerowane wiersze tekstu wejściowego oraz na końcu ma załączony „alfabetyczny” zestaw wystąpień). Napisałem „alfabetyczny” bo nie jest to do końca prawdą (przykładowo litera 'a' jest alfabetycznie starsza od litery 'A'). Problem rozbija się w realizacji instrukcji porównania kluczy:ta realizacja nie bierze pod uwagę pisowni małymi i wielkimi literami. Inny problem to nie do końca poprawnie rozwiązane przetwarzanie napisów (znany problem apostrofa w apostrofach: w pascalu zapisuje się to Ch := '''' ;(4 znaki '), co program rozpozna jako dwa puste napisy). Również w ogóle nie rozpatruje liczb zmiennoprzecinkowych. To nie było moim celem, jak ktoś ma ochotę, … zapraszam do rozwinięcia tematu. Z tego może powstać całkiem interesujące narzędzie pomocne w analizie cudzych programów.


Dla tropicieli:

Inne spojrzenie


Nutahttps://www.youtube.com/watch?v=8a-HfNE3EIo

Choć dotychczas prezentacje algorytmów drzewiastych opierały się o zmienne wskaźnikowe i alokację dynamiczną, nie znaczy to, że tak być musi zawsze. Algorytmy drzewiaste mogą mieć zastosowanie nawet w świecie mikrokontrolerów. Tam mogą występować problemy z dynamiczną alokacją pamięci, więc...
Może warto przestawić myślenie na inne tory. Wyobraźmy sobie, że mamy dużą tablicę elementów o strukturze podobnej do struktury węzła w znaczeniu dotychczasowym. Leksykalnie w zapisie, to nawet może brzmieć identycznie, jednak warto dostrzec, że wskaźnik zmienił reprezentację na liczbę całkowitą.Pomijając (do celów rysunkowych) elementy mało istotne, można to sobie wyobrazić jako:

tree07-01.png

Zmieniam sens znaczenia wskaźników z reprezentacji wskaźnikowej (adres w pamięci) na liczbową (indeks do tablicy). Z tym wiąże się jeszcze jedna zmiana: pascalowa stała wskaźnikowa nil musi mieć swój odpowiednik w świecie integer. Wprowadzam stałą o nazwie NilConst o wartości 16-bitowych jedynek. Typowo nil ma wartość 0, jednak w tym zastosowaniu to najgorszy wariant. Skoro nasz wskaźnik jest liczbą (indeksem do tablicy), to wartość 0 nie jest dobrym wyborem. Realizacja algorytmów drzewiastych w świecie o ograniczonych zasobach może przedstawiać się następująco:

tree07-02.png

Dodanie elementu (3) do tak zmodyfikowanego drzewa może wyglądać następująco:

tree07-03.png

Kolejnych dwóch elementów (1), (5):

tree07-04.png

Problemy „tworzenia” elementów drzewa po przemyśleniach mogą okazać się pozornymi. Można zaproponować „własną” implementację tej operacji. Wyobraźmy sobie, że jest zmienna FirstFree, która wskazuje na pierwszy wolny element. Skoro cały czas tworzone są elementy struktury drzewa, a te mają identyczną wielkość, można stworzyć pulę „wolnych” elementów. Każda akcja typu New ( <element drzewa> ), będzie pobierać z tej puli element. Każda akcja typu Dispose ( <element drzewa> ), będzie dodawać element do puli. Może to być ta sama tablica. Początkowo wszystkie jej elementy będą należeć do puli wolnych elementów. By ta koncepcja zadziałała, wymagana jest wstępna inicjacja. Pierwszy wolny element jest wskazany przez zmienną globalną (FirstFree). Każdy element puli wskazuje na kolejny wolny. Tu zostało wykorzystane pole LeftLink. Ostatni element zamiast wskazania na kolejny wolny zawiera wartość NilConst. Jak się temu przyjrzeć, to to stanowi klasyczną listę liniową.Odpowiada to rysunkowi:

tree07-05.png

Akcja pobrania elementu z puli wolnych, może wyglądać następująco. Pobierany jest pierwszy wolny element: w zmiennej roboczej zapisane jest wskazanie na pierwszy wolny (już ten element nie zginie). Natomiast wskazanie na pierwszy wolny element jest zmodyfikowane, teraz wskazuje na następnika dotychczasowego pierwszego wolnego elementu. Program w wersji rysunkowej:

tree07-06.png

tree07-07.png

tree07-08.png

Akcja typu Dispose, może mieć następującą implementację:Sam program wymaga nieznacznej modyfikacji źródłowej. Oczywista, że można to zrobić na wiele sposobów. Jednym z możliwych jest zaproponowany poniżej:
NodeEntry ^ . Key := Key ; ….................................... → TreeArray [ NodeEntry ] . Key := Key ;
NodeEntry ^ . Balance := State2 ; …........................... → TreeArray [ NodeEntry ] . Balance := State2 ;
NodeEntry ^ . LeftLink := nil ; …............................... → TreeArray [ NodeEntry ] . LeftLink := NilConst ;
NodeEntry ^ . RightLink := nil ; …............................. → TreeArray [ NodeEntry ] . RightLink := NilConst ;
Postępując podobnie w całym programie otrzymujemy jego nową wersję, Algorytm dodania do drzewa wyważonego w wersji „tablicowej”:Program (w którym nie ma ani grama zmienneych wskaźnikowych) ilustrujący rozważania utworzy drzewo, wydrukuje je, po czym w całości je usunie, wydrukuje „stos” wolnych elementów, by pokazać, że nic nie zginęło.Na jakimś tam etapie, drzewo wygląda jak na rysunku.

tree07-09.png

Ciekawie wygląda pula wolnych elementów po akcji: biorę → oddaję. Oddało się w innej kolejności, co raczej nie powinno być niespodzianką. W sumie nie ma to żadnego znaczenia, istotne jest to, że na sztuki wszystko się zgadza (nic nie zginęło → sprawdziłem osobiście).„Tablicowe drzewo” niczym nie różni się od wskaźnikowego. To jest wyłącznie kwestia postrzegania i interpretacji. Jakkolwiek zrealizować poszczególne operacje atomowe, główna idea oraz istotne cechy nadał są te same. Pewnych własności nie da się wymazać.
Dla tropicieli:

Jeszcze inne spojrzenie

Nuta na dziśhttps://www.youtube.com/watch?v=UdPOCQGYwrk

W strukturze elementu drzewa w pierwotnej wersji jako link w lewo oraz link w prawo występują typy wskaźnikowe (jako informacje o charakterze adresu w pamięci operacyjnej). Co stoi na przeszkodzie interpretować je jako informacje o charakterze adresowym w zewnętrznym pliku. Dane o charakterze adresowym w systemach 8-bitowych to zwyczajowo dane 16-bitowe. Z pewnością zakres przechowywanej informacji będzie mizerny, więc może by tak 32-bity. Zamiast przechowywać samo drzewo w pamięci operacyjnej może by tak ulokować je w innym miejscu: pamięci zewnętrznej. Z technicznego punktu widzenia nie jest to zbyt skomplikowane. Przykładowym rozwiązaniem może być układ AT45DB161 – jako zasobnik typu DataFlash o pojemności 16-megabitów, czyli 2 megabajty. Taki teren, to całkiem spora piaskownica do zagospodarowania. Można by tam urządzić jakąś małą bazkę danych. Obecnie każdy zagadnięty hasłem „baza danych” wręcz odruchowo odpowie SQL. A może jest inne rozwiązanie? Przestawny własne wyobrażenia na inne tory.
Baza danych to coś takiego, co jest przeznaczone do gromadzenia informacji i do szybkiego wyszukiwania określonych danych w wyniku zaistnienia określonych potrzeb. Jak zaprząc do tego algorytmy drzewiaste? Rozpatrzmy przykład.
Wyobraźmy sobie, że jakiś mikrokontroler (przykładowo ATMEGA2560, któremu zostało dołożone jako zewnętrzna pamięć RAM 32kb pamięci statycznej oraz na SPI „powieszony” wspomniany DataFlash). To środowisko stanowi minimum zasobów. Pomijam kwestie interfejsu komunikacyjnego, bo to leży poza sferą aktualnego zainteresowania.
Przykładowy rekord bazy danych może mieć następującą postać:

tree08-01.png

gdzie każde z tych pól ma przewidzianą określoną liczbę znaków. Z tego wynika dosyć istotna cecha: rekordy takiej bazy danych są rekordami o stałej długości (zajmują powtarzalną stałą wielkość w przestrzeni adresowej).
Patrząc na obszar DataFlash, jako zewnętrzna (dla mikrokontrolera) pamięć musi zawierać w sobie jakąś organizację. Nie będę tu namawiał do implementacji systemu FAT czy jakiegokolwiek innego, niemniej jakieś podstawowe minimum organizacyjne musi zostać zachowane. Patrząc na temat tak całkiem z boku przez pryzmat systemów operacyjnych, to nasza bazka danych w najprostszym przypadku składałaby się z dwóch plików: samej bazki → pliku zawierającego wyłącznie zgromadzone dane oraz z pliku indeksowego → pliku pozwalającego na szybkie wyszukiwanie wymaganych danych (coś jak katalog w bibliotece).
Ponieważ jest jedna przestrzeń na przechowywane dane, to „wszystkie pliki” trzeba połączyć do jednej kupy. Z tego względu wydzielam trzy różne struktury, które za każdym razem muszą był łatwo pozyskiwalne, czyli mieć stały adres w przestrzeni. Pod pojęciem adresu w tym miejscu uznaję ofset w pamięci: jak daleko w stosunku do początku pamięci DataFlash znajduje się te <coś>. W każdym przypadku taki odpowiedni rekord danych będzie zawierał istotne informację z punktu widzenia określonej potrzeby.
Przykładowo: baza danych. Specyfiką tego jest to, że generalnie dane przyrastają. Dodając nowe dane przesuwa się granica umownego końca przestrzeni danych. Jednak czasami zachodzi potrzeba usunięcia czegoś. W takim przypadku, powstaje „dziura” w wypełnieniu pamięci DataFlash. Ponieważ nic nie może się zmarnować, to utworzona jest lista liniowa rekordów z odzysku. Dodając nowy rekord, należy sprawdzić, czy czegoś nie da się odzyskać. Skoro jest lista odzyskowych elementów, to koniecznością staje się przechowywanie wskazania na pierwszy wolny rekord (Wolny rekord → jako 32-bitowy ofset w przestrzeni adresowej DataFlash). W nim (gdzieś już daleko w przestrzeni) zapisany jest jego następnik.

tree08-02a.png

Podobnie, część logicznie związana z indeksem (strukturą drzewa) wymaga swojej części „technicznej” umieszczonej w dobrze znanym miejscu.

tree08-02b.png

Jak w każdym drzewie, tu również jest niezbędne wskazanie na szczyt drzewa. Jest to informacja, która z czasem ulega modyfikacji, toteż niezbędne jest przechowywanie tych danych w „dobrze znanym miejscu” w pamięci DataFlash. Podobnie, może zaistnieć problem odzysku danych. Jeżeli zaistnieje zwolnienie pojedynczego elementu, to by nie generować dziur, konieczne jest notowanie wolnych elementów ze struktury drzewa. Coś takiego było wyżej przedstawione przy okazji tablicowej realizacji drzewa. Samo drzewo może również przechowywać informacje o duplikatach. Dokładnie tej klasy problem był opisany wyżej przy okazji Cross Reference. Zatem w strukturze możliwych danych występuje mały rekord zawierający powiązanie kolejnych rekordów bazy danych o identycznym kluczu oraz wskazanie na kolejny element takiej listy (listy identycznych kluczy). Te minimum informacji właśnie jest pokazane na powyższej ilustracji.
Nowe wymagania oznaczają potrzebę stworzenia nowej struktury elementu drzewa. Obok dotychczas znanych elementów występuje nowy: DataLink. Jest to, jak każda informacja o charakterze link informacją 32-bitową jako ofset w pamięci DataFlash. Ta istotna informacja pozwala powiązać indeks (kartkę w katalogu bibliotecznym z uwzględnieniem ewentualnych duplikatów jako listy liniowej) z danymi bazy danych (wskazaniem na „której półce stoi książka”). Jeżeli rekord danych będzie reprezentowany przez adres w przestrzeni DataFlash (czyli 32-bitowy ofset), to przechowując takie wskazanie w strukturze każdego elementu drzewa, uzyskuje się powiązanie jednych danych z drugimi.

tree08-02c.png

Do kompletu należy dodać jeszcze dane organizujące całość (jako plik).

tree08-02.png

Tu minimum, to przechowywanie położenia końca „pliku”, by w operacjach rozszerzenia takiego specyficznego pliku było wiadomo, gdzie się on kończy.
Operacja dodania nowej informacji do bazy danych oznacza w pierwszej kolejności dopisanie samego rekordu danych. To może skończyć się rozszerzeniem „pliku” lub odzyskaniem jakiejś „dziury” w wyniku wyjęcia jej z listy wolnych miejsc. Finalnie, gdziekolwiek dane zostaną zapisane, informacją zwrotną z tej operacji jest ofset położenia rekordu danych. Mając ten ofset i klucz, realizowane jest dodanie elementu drzewa. Tu również może zaistnieć rozbudowanie drzewa (w wyniku rozszerzenia wielkości „pliku” lub odzysku danych z listy wolnych elementów struktury drzewa). Finalnie może to wyglądać jak na ilustracji (NilConst będzie $FFFFFFFF - 32-bity):

tree08-03.png

Odszukanie informacji (np. do kogo należy numer tel 229555777) teraz sprowadza się do:

• wczytanie porcji organizacyjnej indeksu, która zapisana jest w dobrze znanym miejscu w DataFlash,
• z wczytanej porcji uzyskuje się wskazanie na szczyt drzewa,
• mając szczyt drzewa rekurencyjnie odszukać taki element drzewa, który jest zgodny z poszukiwanym kluczem (wymienionym wyżej numerem telefonu),
• mając element drzewa, pozyskać z niego wskazanie na położenie rekordu danych (DataLink).

W rezultacie całej zadymy posiadamy informację gdzie jest zapisany rekord w DataFlash zawierający to co jest poszukiwane.
Oczywiście ze względu na zewnętrzny charakter pamięci do przechowywania wszystkich informacji, należy pamiętać, że algorytm obsługi drzewa przetwarza dane z „obcej” pamięci.
Pewnemu rozszerzeniu ulega struktura elementu drzewa:Dotychczasowa operacja poszukiwania danych w strukturze drzewa musi być zmodyfikowana przykładowo do postaci pokazanej poniżej. Pamiętając, że zmienna lokalna Node znajduje się w pamięci RAM a dane ją wypełniające znajdują się w innej przestrzeni (DataFlash), konieczne jest wczytanie obszaru DataFlash spod ofsetu NodeEntry (to jest inny „świat”):Również identycznym komplikacjom podlegają wszystkie inne operacje. W niektórych przypadkach jest to oczywiste, w niektórych można je przeoczyć na pierwszy rzut oka. W powyższym kawałku, naturalne jest, że DataFlash został wzbogacona o nowy rekord, więc konieczna jest aktualizacja zawartości DataFlash, tak by dane były konsystentne. Trudniej jest zauważyć, że parametr wywołania NodeEntry, również uległa zmianie. Ta nowa zawartości również musi mieć zwoje odbicie w DataFlash. Jednak ta informacja jest częścią składową elementu drzewa na poprzednim poziomie rekurencji, do którego w danej chwili nie ma dostępu. Dostęp ten jest natomiast na innym poziomie rekurencji, jednak w tym kontekście trudno jest określić, czy zaistniała zmiana zawartości pola. Dobrym rozwiązaniem jest zapamiętanie linku przez rekurencyjnym wywołaniem i po wyjściu z rekurencji sprawdzić, czy zaistniała odpowiednia zmiana i dokonać aktualizacji zawartości DataFlash. Również każda modyfikacja współczynnika zrównoważenia drzewa wymaga „odciśnięcia swego piętna” w zawartości DataFlash.
Taki indeks pozwala szybko lokalizować dane mając znany numer telefonu. Naturalnym jest, że zachodziłaby potrzeba znalezienia danych mając jedynie imię i nazwisko. W ten sposób dochodzimy powoli do idei „lasu”. Jeżeli dodawany element drzewa posiada pole wskazujące na położenie danych w przestrzeni DataFlash, to zmieńmy znaczenie tej informacji: niech będzie to wskazaniem na szczyt drzewa. Reasumując, powstaje drzewo drzew. Kiedyś w ramach żartu nazwałem do „lasem” i tak już zostało.
Dodanie kolejnego indeksu wymagałoby również dodania porcji organizacyjnej w „dobrze znanym miejscu”. Drugie drzewo, to również drugi szczyt drzewa, lista rekordów z odzysku (inna długość klucza to inna wielkość struktury rekordu drzewa a to prowadzi do innej wielkości „dziur” po usuniętych elementach w przestrzeni DataFlash).
Obrazkowo może to wyglądać następująco:

tree08-04.png

Teraz wyszukanie wszystkich Kowalskich sprowadza się do „wydruku” całego drzewa (w sensie algorytmu jest to wydruk drzewa, w sensie organizacyjnym jest to wydruk drzewa imion „przypiętego” do drzewa nazwisk).
Te rozwiązania stosowałem w rzeczywistych rozwiązaniach pod koniec lat 80-tych tworząc różne bazy danych z rekordami o stałej długości sortując tysiące rekordów i jakoś to się nie gubiło. Co prawa, to realizacja opierała się o komputery PC a pliki (jako rozdzielone) były w przestrzeni dysków. Czasy się trochę zmieniły, ewolucji ulegają możliwości technologiczne, jednak algorytmy, jako przepis na osiągnięcie celu pozostają takie same.
Na tym zakończę już dywagacje na temat drzew i czas przejść na wyższy level: B-drzewa. To jest „odlotowy” wynalazek.

gaweł pisze: Reasumując, powstaje drzewo drzew. Kiedyś w ramach żartu nazwałem do „lasem” i tak już zostało.

Używając "drewnianej" terminologii można element z dwoma nullami i rodzicem nazwać "liściem". I byłby to żart całkiem na miejscu

piotrek pisze:Używając "drewnianej" terminologii można element z dwoma nullami i rodzicem nazwać "liściem". I byłby to żart całkiem na miejscu

Okazuje się, że przyroda jest niedościgła ze swoimi rozwiązaniami
Kontynuacja rozważań przyrodniczo-ekologicznych jest B-drzewa