Drzewa : budowa i przetwarzanie.

 

Drzewo ukorzenione jest to graf skierowany, nie zawierający cykli i spełniający następujące warunki:

1.Istnieje dokładnie jeden wierzchołek (węzeł) do którego nie dochodzi żadna krawędź - korzeń drzewa

2.Dla każdego wierzchołka grafu istnieje droga (jedyna) od korzenia do tego wierzchołka

3.Każdy wierzchołek nie będący korzeniem ma jedyną krawędź dochodzącą do niego.

 

Jeśli w grafie istnieje krawędź (gałąź) od węzła w do węzła v, to w nazywamy poprzednikiem (przodkiem, ojcem) v, a v nazywamy następnikiem (potomkiem, synem) w. Wierzchołek bez potomków nazywamy liściem. Wierzchołek mający co najmniej jednego potomka nazywamy węzłem wewnętrznym. Wierzchołek reprezentujący elementy nie występujące w drzewie (oznaczony przez NULL) nazywamy węzłem zewnętrznym (w niektórych książkach te węzły są nazywane liśćmi). Wierzchołek v razem z jego potomkami nazywamy poddrzewem o korzeniu v. Głębokość (poziom) wierzchołka v jest to długość drogi (liczba krawędzi) od korzenia do v (korzeń ma głębokość 0). Wysokość drzewa jest to maksymalna długość drogi od korzenia do liści (czyli największa z głębokości liści, wysokość drzewa pustego wynosi -1, a drzewa jednowęzłowego 0).

 

Drzewo uporządkowane - drzewo w którym następniki każdego wierzchołka są uporządkowane (na rysunku - od lewej do prawej).

 

W programowaniu najważniejsze znaczenie mają uporządkowane drzewa binarne. Binarne drzewo poszukiwań (B inary S earch T ree) - drzewo uporządkowane spełniające warunki:

1. wśród następników każdego wierzchołka wyróżniamy lewy i prawy następnik

2. każdy wierzchołek ma co najwyżej jeden prawy i jeden lewy następnik

3. w lewym poddrzewie znajdują się wartości mniejsze od korzenia, a w prawym większe.

4. klucze się nie powtarzają.

Podstawowe działania na uporządkowanych drzewach binarnych (patrz BST.java).

Najprostsza postać węzła drzewa (można ją wzbogacić o dodatkowe informacje):

 

class Node{

Object value;

Node left;

Node right;

Node(Object x)

{ value=x; left = right = null; }

}

 

Do podstawowych działań na drzewach możemy zaliczyć:

 

1. Przechodzenie przez wszystkie wierzchołki drzewa (w określonej kolejności) - przetwarzanie całego drzewa

2. Wyszukiwanie - sprawdzanie czy w drzewie występuje węzeł o zadanym kluczu

3. Wstawianie - dołączanie nowego węzła do drzewa

4. Usuwanie węzła z drzewa.

 

1. Przechodzenie przez wszystkie wierzchołki drzewa (o korzeniu t):

 

Przejdź(Wsk t)

Przejdź(t->lewe);

przetwórz(t); // wykorzystaj węzeł t

Przejdź(t->prawe);

Ponieważ trzy czynności - przejdź lewe, przetwórz korzeń i przejdź prawe możemy ustawić na 6 różnych sposobów tyle też jest sposobów przechodzenia drzewa. Dla BST jest najważniejszy sposób pokazany wyżej ponieważ daje wierzchołki od najmniejszego do największego.

 

Przykład przechodzenia in-order (PLW) w celu pokazania struktury drzewa jest w BST.java (metoda toString).

 

 

2. Wyszukiwanie węzła (o zadanej wartości) w drzewie. Jeśli węzła nie ma zwraca NULL.

 

public Object find(Object x)

{Node t = search(x);

return t!=null? t.value: null;

}

 

private Node search(Object value) {

Node node = _root;

int cmp=0;

while (node!= null &&(cmp = _comparator.compare(value, node.value))!=0)

node = cmp < 0? node.left: node.right;

return node;

}

 

Jest to przykład jednej z nielicznych iteracyjnych metod dla drzew.

 

3. Wstaw węzeł do drzewa.

Należy przeszukać drzewo, i jeśli dodawanego węzła w nim nie ma - dołączyć go (zawsze jako liść). Jeśli jest to zgłaszany jest wyjątek.

 

public void insert(Object x)

{ _root= insert(x,_root); }

 

protected Node insert(Object x, Node t) {

if(t== null) t=new Node(x);

else { int cmp=_comparator.compare(x,t.value);

if(cmp<0) t.left=insert(x,t.left);

else if(cmp>0) t.right=insert(x,t.right);

else throw new DuplicateItemException(x.toString());

}

return t;

}

 

 

4. Usuń węzeł (o podanej wartości) z drzewa.

 

Znajdź węzeł w drzewie - możliwe są dwa przypadki

- węzła nie ma (błąd) - zgłaszany jest wyjątek

- węzeł jest - i tu rozróżniamy 3 przypadki:

- a) węzeł jest liściem - zwyczajnie go usuwamy

- b) ma tylko jednego syna - zastępujemy go lewym lub prawym poddrzewem

- c) ma dwóch synów (najgorszy przypadek)

- znajdujemy skrajnie lewy węzeł w prawym poddrzewie (bezpośredni następnik - może mięć co najwyżej jednego syna więc jest łatwy do usunięcia; można wybierać największy w lewym poddrzewie),zastępujemy nim usuwany węzeł i usuwamy go.

 

 

public void delete(Object x)

{_root=delete(x,_root); }

 

protected Node delete(Object x, Node t) {

if(t==null) throw new ItemNotFoundException(x.toString());

else { int cmp=_comparator.compare(x,t.value);

if(cmp<0) t.left=delete(x,t.left);

else if(cmp>0) t.right=delete(x,t.right);

else if(t.left!=null &&t.right!=null)

t.right=detachMin(t.right,t);

else t = (t.left!= null)? t.left: t.right;

}

return t;

}

 

//zastąp usuwany element jego następnikiem i usuń następnik

 

protected Node detachMin(Node t, Node del) {

if(t.left!=null) t.left=detachMin(t.left,del);

else {del.value=t.value; t=t.right;}

return t;

}

 

Drzewa BST wyradzają się przy nielosowej kolejności wstawiania elementów (np. uporządkowane).

Zbudowanie optymalnego (gwarantującego minimalną liczbę porównań) jest bardzo trudne - patrz Aho,Hopcroft,Ullman - "Projektowanie i analiza algorytmów komputerowych. Dlatego zazwyczaj zadowalamy się prawie optymalnymi drzewami gwarantującymi logarytmiczną wysokość (złożoność wyszukiwania).

 

1. drzewa wyważone AVL (Adelson-Velski, Landis) - dla każdego węzła wysokości poddrzew różnią się co najwyżej o 1. Stosunkowo proste działania (wystarczy dodać wskaźnik wyważenia). Gwarantowana wysokość 1.45log n.

2. inne: BB-drzewa (2-3 drzewa), drzewa czerwono-czarne (SBB drzewa, 2-3-4 drzewa) - obecnie najczęściej stosowane, opracowane przez Bayera.

 

Drzewa wyważone AVL (patrz AVL.java).

 

// nie będą omawiane na wykładzie (lekko się zestarzały od 1962 roku

// zamiast nich będzie omówiona implementacja 2-3-4 drzew w postaci drzew czerwono-czarnych.

//aby ułatwić porównanie pozostawiam AVL w treści wykładu

Wyszukiwanie odbywa się jak w zwykłym drzewie BST. Wstawianie i usuwanie węzłów komplikują się, ponieważ trzeba kontrolować wyważenie i czasami przebudowywać drzewo. Wskaźnik wyważenia dla każdego z węzłów może przyjmować jedną z trzech wartości

L- lewe poddrzewo jest wyższe od prawego

R- oba drzewa mają tę samą wysokość

P- prawe poddrzewo jest wyższe

 

 

Przebudowa drzewa jest realizowana za pomocą rotacji - tym razem również podwójnych:

 

//Prosta zamiana węzła z jego lewym potomkiem

 

Node RotRight(Node t)

{ Node t1=t.left;t.left = t1.right; t1.right=t; return t1;}

 

// Prosta zamiana węzła z jego prawym potomkiem

Node RotLeft(Node t)

{ Node t1=t.right; t.right =t1.left; t1.left = t; return t1;}

 

//Podwójna rotacja LewaPrawa:

// 1. lewy potomek węzła ze swoim prawym potomkiem

// 2. węzeł z lewym potomkiem(po zamianie 1.)

 

Node RotLeftRight(Node t)

{ t.left = RotLeft(t.left); return RotRight(t);}

 

// rotacja PrawaLewa - Symetryczna do rotacji LewaPrawa

 

Node RotRightLeft(Node t)

{ t.right=RotRight(t.right); return RotLeft(t); }

 

 

Wstawianie elementu x do drzewa o korzeniu t, h - wskaźnik czy drzewo zmieniło wysokość,

jeśli już był zgłaszany jest wyjątek.

 

 

Należy rozpatrzyć następujące przypadki w zależności od wskaźnika ojca wstawianego węzła przed wstawieniem (zakładamy że nowy węzeł jest dołączany jako lewy syn - przy wstawianiu do prawego poddrzewa sytuacja jest w pełni symetryczna)

- P - oba poddrzewa wyrównują się, nowy wskaźnik ojca jest R

- R - urosło lewe poddrzewo ale warunek wyważenia jest zachowany nowy współczynnik ojca jest L

- L - najgorszy przypadek - urosło wyższe drzewo, należy przywrócić wyważenie, postępowanie zależy od

wyważenia lewego poddrzewa wyważanego węzła:

- L - prosta zamiana węzła z jego lewym potomkiem

- P lub R - podwójna zamiana (LewoPrawo)

1. lewy potomek z prawym potomkiem lewego potomka węzła

2. węzeł z lewym potomkiem (po zamianie 1.) }

 

W przypadkach R i L należy skontrolować wyważenie przodka wstawianego węzła.

 

 

Usuwanie węzła (parametry jak wyżej) odbywa się jak w BST plus wyważanie drzewa.

 

Tym razem poddrzewo mogło ulec skróceniu - łato zauważyć podobieństwo sytuacji: urosło lewe poddrzewo i prawe poddrzewo uległo skróceniu.

Podobnie jak przy wstawianiu sytuacja zależy od wyważenia ojca usuwanego węzła (do opisu przyjmijmy że usuwany węzeł był w lewym poddrzewie, jeśli usunęliśmy z prawego poddrzewa sytuacja jest symetryczna).

- L - wyższe drzewo uległo skróceniu, nowy wskaźnik - R

- R - skróciło się lewe poddrzewo ale warunek wyważenia jest zachowany nowy wskaźnik - P

- P - obcięte zostało niższe drzewo, trzeba przywrócić wyważenie, sprawdzamy wskaźnik wyważenia prawego

poddrzewa wyważanego węzła

- P lub R - prosta zamiana węzła z jego prawym potomkiem

- L - podwójna zamiana (PrawoLewo)

1. prawy potomek z lewym potomkiem prawego potomka

2. węzeł z prawym potomkiem

 

2-3-4 drzewa i ich implementacja w postaci drzew czerwono-czarnych przechylonych w lewo (LLRBTree Sedgevick 2007) (patrz LLRB.java).

 

Koncepcję 2-3-4 drzew opracował w 1972 roku Bayer. Są to prawie optymalne drzewa poszukiwań - gwarantują logarytmiczną złożoność wyszukiwania. W węźle może być zapisane do 3 elementów. Wszystkie liście są na tym samym poziomie.

- wyszukiwanie odbywa się podobnie jak w BST

- wstawianie zawsze do liścia; gdy liść jest 4-węzłem następuje jego podział i przeniesienie elementu dzielącego do ojca. Jest to bardzo kłopotliwe, więc częściej stosuje się eliminację 4-węzłów przy schodzeniu do liścia. Ciekawostka: drzewo rośnie w stronę korzenia.

- usuwanie jest bardziej złożone, należy rozróżnić dwie sytuacje:

n usuwanie z liścia; czasem połączone z pożyczką elementu od sąsiedniego węzła lub połączeniem węzłów

n usuwanie z węzła wewnętrznego - zastępujemy usuwany element jego bezpośrednim następnikiem lub poprzednikiem (znajduje się on w liściu więc jest łatwy do usunięcia)

 

Bezpośrednia realizacja węzłów w postaci tablicy elementów byłaby bardzo nieefektywna, dlatego 2-3-4 drzewa implementuje się jako drzewa czerwono-czarne (Guibas i Sedgewick 1978).

Jest prosty sposób przedstawienia 2-,3- i 4-węzłów za pomocą węzłów binarnych z dodanym polem koloru.

Własności drzew czerwono czarnych:

- każdy węzeł jest albo czerwony albo czarny

- korzeń i wszystkie węzły zewnętrzne są czarne

- jeśli węzeł jest czerwony to jego synowie są czarni (nie ma dwóch czerwonych wezłów pod rząd)

- każda ścieżka od ustalonego węzła do liścia ma tyle samo czarnych węzłów.

 

Drzewa czerwono-czarne mimo dużej złożoności metod realizujących poszczególne działania (co jest spowodowane dużą liczbą różnych sytuacji) są powszechnie stosowane - ze względu na gwarantowaną logarytmiczną złożoność i szybkość działania. Dopiero Sedgewick w 2007 zaproponował ograniczenie sposobów przedstawienia węzłów co doprowadziło do znaczącego uproszczenia kodu - bez pogorszenia szybkości wyszukiwania. Opracowane przez niego LLRBTree (Left Lean Red Black Tree - drzewa czerwono-czarne przechylone w lewo) dopuszczają występowanie 4-węzłów tylko chwilowo (w czasie wykonywania operacji) i pozwalają na jedną reprezentację 3- węzłów. Przykładowa implementacja:

 

package rbtree;

 

public class LLRBTree<Elem extends Comparable<Elem>> {

static final boolean RED=true;

static final boolean BLACK =false;

 

private Node _root;

 

public LLRBTree()

{ _root=null;}

 

private boolean isRed(Node x)

{return x!= null && x.color==RED;}

 

public Elem find(Elem x)

{Node t = search(x);

return t!=null? t.value: null;

}

 

private Node search(Elem value) {

Node node = _root;

int cmp=0;

while (node!= null &&(cmp = value.compareTo(node.value))!=0)

node = cmp < 0? node.left: node.right;

return node;

}

 

 

private Node rotateL(Node t)

{ Node x=t.right;

t.right=x.left;

x.left=t;

x.color=t.color;

t.color=RED;

return x; }

 

private Node rotateR(Node t)

{ Node x=t.left;

t.left=x.right;

x.right=t;

x.color=t.color;

t.color=RED;

return x; }

 

private void colorFlip(Node t)

{t.color=!t.color; t.left.color=!t.left.color; t.right.color=!t.right.color; }

 

 

public void insert(Elem x)

{ _root= insert(x,_root); _root.color=BLACK;}

 

protected Node insert(Elem x, Node t) {

if(t== null) t=new Node(x);

else { int cmp=x.compareTo(t.value);

if(isRed(t.left) && isRed(t.right))

colorFlip(t);

if(cmp<0) t.left=insert(x,t.left);

else if(cmp>0) t.right=insert(x,t.right);

else throw new RuntimeException("Duplicate "+x.toString());

t=fixUp(t);

}

return t;

}

 

private Node fixUp(Node t)

{ if(isRed(t.right))

t=rotateL(t);

if(isRed(t.left) && isRed(t.left.left))

t=rotateR(t);

if(isRed(t.left) && isRed(t.right))

colorFlip(t);

return t; }

 

private Node moveRedR(Node t)

{ colorFlip(t);

if(isRed(t.left.left))

{ t=rotateR(t); colorFlip(t); }

return t; }

 

private Node moveRedL(Node t)

{ colorFlip(t);

if(isRed(t.right.left))

{ t.right=rotateR(t.right); t=rotateL(t); colorFlip(t);}

return t;}

 

public void delete(Elem x)

{_root=delete(x,_root);

if(_root!=null) _root.color=BLACK;}

 

protected Node delete(Elem x, Node t) {

if(t==null) throw new RuntimeException("Not found "+x.toString());

else { int cmp=x.compareTo(t.value);

if(cmp<0)

{ if(!isRed(t.left) &&!isRed(t.left.left))

t=moveRedL(t);

t.left=delete(x,t.left);

}

else{if(isRed(t.left)) t=rotateR(t);

if(x.compareTo(t.value)==0&&t.right == null) return null;

else { if(!isRed(t.right) &&!isRed(t.right.left))

t=moveRedR(t);

if(x.compareTo(t.value)>0)

t.right=delete(x,t.right);

else t.right=detachMin(t.right, t);

}

}

}

return fixUp(t);

}

 

protected Node detachMin(Node t, Node del) {

if(t.left==null) {del.value=t.value; t=null;}

else { if(!isRed(t.left) &&!isRed(t.left.left))

t=moveRedL(t);

t.left=detachMin(t.left,del);

t=fixUp(t); }

return t;

}

 

 

public String toString()

{return toString(_root,0);}

 

private String toString(Node t,int pos) {

String result="";

String spaces=" ";

if(t!=null) result=result+toString(t.right,pos+4)+spaces.substring(0,pos)

+String.format("%s%s",t.value,(t.color? "/R":"/B"))+toString(t.left,pos+4);

else result=result+String.format("%n");

return result;

}

 

class Node{

Elem value;

Node left;

Node right;

boolean color;

Node(Elem x)

{ value=x; left = right = null; color = RED;}

}

 

}

 

B-drzewa.

Są to zrównoważone drzewa wielokierunkowe - naturalne uogólnienie 2-3-4 drzew.

Stosowane są w przypadku dużych słowników - nie mieszczących się w pamięci operacyjnej. Węzły tych drzew zawierają więcej niż jeden obiekt (element słownika) co zmniejsza liczbę odczytów z dysku, przez zmniejszenie

głębokości drzewa, a przez to przyspiesza działanie (odczyt z dysku odbywa się zazwyczaj większymi porcjami więc odczytanie 1 bajta i odczytanie kilkuset bajtów zabiera praktycznie tyle samo czasu).

Ponieważ różni autorzy przedstawiają nieco różne warianty tych drzew, wybrałem rozwiązania przedstawione przez Cormena ("Wprowadzenie do algorytmów").

 

Węzeł (strona) B-drzewa rzędu M zawiera od M-1 do 2M-1 kluczy (czyli ma od M do 2M potomków, lub jest liściem). Wyjątkiem jest korzeń (może mieć mniej kluczy). Wszystkie liście drzewa leżą na tym samym poziomie.

 

Węzeł B-drzewa rzędu M ma następującą strukturę:

class Node

{ static int Size=... // 2* (rząd drzewa)-1

int numItems; // liczba kluczy na stronie

Object [ ]itemArray =new Object[size]; // tablica kluczy (mogą być kompletne obiekty)

Node[ ] childArray =new Node[size+1] // tablica potomków i-ty element to strona

} // zawierająca klucze mniejsze itemArray[i]

 

Klasa BTree ma tylko pole root - korzeń drzewa.

Wygodnie jest przyjąć, że puste drzewo to drzewo złożone z pustej (n==0) strony korzenia.

 

Przechodzenie przez drzewo w kolejności rosnących kluczy (np. w celu wydrukowania wartości):

 

void printBTree (Node t)

{ for (int i=0; i< t.numItems;i++)

{ if (t.childArray[i]!=null) printBTree (t.childArray[i]);

print(t.itemArray[i]);

}

}

 

Szukanie obiektu o kluczu k w B-drzewie o korzeniu t (sprawdzanie czy jest):

 

boolean (Node t, Object item)

{ int i=0;

int cmp=0;

while (i<t.numItems && ((cmp=comparator.compare(item,t.itemArray[i])) >0))

i++; // szukaj klucza >=item

if(i<t.numItems && cmp= =0) return true; // znaleziono

if (t.childArray[i]==null) return false; // doszliśmy do liścia, item nie ma

return find(t.childArray[i],item); // szukaj na stronie potomnej

}

 

Wstawianie nowego obiektu na stronę C. Możliwe są dwa przypadki:

 

1. Na stronie jest mniej niż 2M-1 kluczy - wstawiamy nowy klucz na odpowiednie miejsce tablicy kl;

2. Strona jest pełna (zawiera 2M-1 kluczy)

- przydzielamy pamięć na nową stronę D

- rozdzielamy 2M kluczy równo (prawie) na strony C i D, klucz środkowy wstawiamy do strony będącej teraz ojcem stron C i D (powtarzamy krok 2 aż do usunięcia przepełnienia stron).

 

Ponieważ przenoszenie klucza w górę jest dość kłopotliwe, zastosujemy inne rozwiązanie. Ilekroć przy wyszukiwaniu miejsca wstawienia mamy wejść na pełną stronę od razu ją dzielimy. Fizyczne wstawianie odbywa się wtedy na niepełną stronę.

 

Usuwanie elementu nie jest proste ze względu na możliwość powstania niedomiaru (strony mającej mniej niż M-1 kluczy), mamy trzy główne przypadki:

 

1. Usuwamy klucz k ze strony t będącej liściem (jest to zwykłe usunięcie elementu z tablicy)

2. Usuwamy klucz k ze strony t nie będącej liściem.

a. Niech y będzie synem t poprzedzającym k. Jeśli y ma co najmniej M kluczy, to w poddrzewie o korzeniu y wyznacz poprzednik k' klucza k. Rekurencyjnie usuń k" i w węźle t zastąp k przez k'.

b. Symetrycznie, jeśli syn z występujący po k w węźle t, ma co najmniej M kluczy, to wyznacz następnik k' dla k w poddrzewie o korzeniu z. Rekurencyjnie usuń k' i zastąp w x k przez k'.

c. Jeśli obaj synowie y i z mają tylko po M-1 kluczy, to przenieś k i wszystko z węzła z do y. Zwolnij pamięć przydzieloną z i usuń rekurencyjnie k z y.

3. Jeśli klucz k nie występuje w wewnętrznym węźle t, to wyznacz korzeń ws[i] poddrzewa w którym musi znajdować sie k. Jeśli ws[i] ma tylko M-1 węzłów to wykonaj podkrok 3a lub 3b aby zapewnić, że zejdziemy rekurencyjnie do węzła z co najmniej M kluczami. Usuń rekurencyjnie k z właściwego poddrzewa.

a. jeśli w węźle ws[i] jest tylko M-1 kluczy, ale jeden z jego sąsiednich braci ma >=M kluczy, to umieść w ws[i] dodatkowy klucz, przesuwając odpowiedni klucz z t, a w jego miejsce przenosząc klucz z lewego lub prawego brata - tego który ma >=M kluczy (trzeba również przenieść odpowiadający mu wskaźnik na syna)

b. jeśli ws[i] i sąsiedni bracia mają po M-1 kluczy to połącz ws[i] z jednym z sąsiednich braci, przesuwając odpowiedni klucz z x do nowo powstałego węzła (zwolnij pamięć opróżnionej strony).

 

Tu są (a może będą) realizacje odpowiednich funkcji.

 

Przedstawione wcześniej 2-3-4 drzewa są odpowiednikami BDrzewa rzędu 2.

 

 

Drzewa pozycyjne.

 

Na koniec przedstawiam przykład pozycyjnego (cyfrowego) drzewa poszukiwań - w literaturze można znaleźć inne drzewa pozycyjne: TRIE, PATRICIA, TST itd.

Mogą one być stosowane gdy klucz jest ciągiem symboli z niewielkiego alfabetu. Np. ciąg liter, ciąg cyfr, ciąg niewielkich liczb, czy też kreska-kropka (jak w alfabecie Morse'a). Zakładamy, że łatwo możemy przetworzyć każdy symbol na wartość liczbową.

 

Korzeń pustego drzewa stanowi węzeł bez wartości (dane = wartość pusta) który wszystkie adresy ma ustawione na NULL.

 

Jak wyglądają poszczególne działania na takim drzewie?

 

1. Szukanie węzła o danym kluczu (kl) w drzewie o korzeniu t:

 

Schodzimy po gałęziach drzewa wyznaczonych przez kolejne pozycje klucza - możliwe są trzy zakończenia:

 

1. doszliśmy do końca drzewa, a nie wykorzystaliśmy wszystkich pozycji klucza

- węzła o takim kluczu nie ma w drzewie

2. Wyczerpaliśmy klucz (sprawdzamy pole dane w osiągniętym węźle)

a. ma wartość - jest to szukany węzeł

b. ma wartość nieokreśloną (0) nasz klucz jest przedrostkiem klucza istniejącego w drzewie węzła ale

sam nie ma wartości

 

2. Wstawianie węzła o kluczu kl do drzewa o korzeniu t.

 

Najpierw schodzimy po drzewie (tak jak przy szukaniu):

1.Skończyl się klucz na węźle w

a. w ma ustawioną wartość - węzeł już jest w drzewie (błąd?)

b. węzeł nie ma wartości - wpisujemy do węzła wskaźnik wartości

2.Skończyło się drzewo - musimy wytworzyć ciąg węzłów odpowiadający niewykorzystanym pozycjom klucza (wszystkie oprócz ostatniego maja wartość pusta, ostatni ma wartość)

 

3. Usuwanie z drzewa o korzeniu t węzła o kluczu kl. (zakładamy że węzeł jest w drzewie)

 

Najpierw schodzimy do usuwanego węzła (rekurencyjnie) i ustawiamy mu wartość pusta. Wracając sprawdzamy czy dany węzeł jest liściem z pustą wartością: jeśli tak to go usuwamy (nie wolno usunąć korzenia).

 

Charakterystyczną cechą drzew cyfrowych jest to że czas znalezienia węzła nie zależy od liczby wierzchołków a jedynie od długości klucza (zazwyczaj jest mniejszy niż w drzewach binarnych). Każdy zbiór kluczy ma jedyną reprezentację - nie ma drzew gorszych i lepszych. Niestety wymagają one sporo pamięci - możliwe są różne rozwiązania kombinowane redukujące tę wadę.

Jako ciekawostkę można dodać, że tak naprawdę to drzewo pozycyjne nie jest drzewem ale lasem (a jeśli wszystkie klucze mają jednakową długość to nawet żywopłotem).

 

 

Zadania:

24) Jaką kolejność przechodzenia drzewa wykorzystasz do zapisania elementów drzewa w pliku. Po odczytaniu z pliku i wykonaniu ciągu wstawień powinna zostać odtworzona struktura drzewa.Nie wykorzystuj możliwości serializacji.

25) Wytwarzany w przykładzie (BST.java) wydruk wymaga przechylania głowy przy czytaniu. Opracuj metodę drukującą drzewo wierszami. Podpowiedź: rozważ przydatność wykorzystania kolejki.

26) Jak wygląda drzewo binarne reprezentujące wyrażenie. Jaką kolejność przechodzenia zastosujesz do obliczania wartości tego wyrażenia.

27) Zaimplementuj inne metody przetwarzające drzewo, których wynikiem będzie:

- liczba węzłów drzewa

- liczba węzłów wewnętrznych

- liczba węzłów z jednym (dwoma) potomkiem

- liczba liści

- liczba węzłów zewnętrznych

- liczbę węzłów mniejszych od korzenia

- głębokość węzła

- wysokość poddrzewa którego korzeniem jest dany węzeł itp.

28) Zaimplementuj metody wpisującemu każdemu węzłowi drzewa (w dodatkowym polu) wartości z poprzedniego zadania.

29) Znajdź w drzewie największy z węzłów nie większych (mniejszych) od danego.

30) Utwórz BDrzewo (rzędu 2) wstawiając do niego kolejne wartości od 1 do 13. Zwróć uwagę na sytuacje wymagające przebudowy drzewa. Z tak zbudowanego drzewa usuwaj kolejno elementy: 8, 9, 1, 2, 3 itd.

 

 

Tablice haszowane.

Gdyby wszystkie klucze były różne i miały wartości z niewielkiego zakresu 0..M-1, można by było zastosować prostą tablicę indeksowaną kluczem elementów.

Najczęściej jednak możliwych wartości klucza jest zbyt wiele, wówczas stosujemy haszowanie (mieszanie).

Stosujemy je jeśli potrafimy zbudować funkcję przyporządkowującą każdemu kluczowi wartość z przedziału 0..M-1. Zazwyczaj zbiór możliwych wartości kluczy jest bardzo duży, o wiele większy od liczby pamiętanych elementów. Np. zbiór słów o długości mniejszej od 15 liter (polskiego alfabetu) ma liczność około 2E24, podczas gdy duże słowniki zawierają około 100000 haseł, duże zbiory indeksowane nazwiskiem mogą mieć np. 10000000 elementów. Idea polega na tym by element el zapisać w tablicy na pozycji h(el). Oczywiście h nie jest funkcją różnowartościową, więc pojawiają się kolizje (dwa lub więcej kluczy daje tę samą wartość h(el)) sposób ich rozwiązywania zależy od realizacji tablicy haszowanej.

a) tablica statyczna

 

Zapis elementu do tablicy:

IF (pozycja h(el) jest wolna) zapisz element

ELSE znajdź pierwszą wolną pozycję (od h(el) cyklicznie)

zapisz element na wolnej pozycji

 

Wyszukanie (dla uproszczenia - zawsze istnieje jedna wolna pozycja):

IF (na pozycji h(el) jest właściwy element) znalazłeś

ELSE szukaj cyklicznie do znalezienia lub trafienia na wolną

IF (koniec na wolnej pozycji) nie ma

ELSE znalazłeś

 

Wyszukiwanie może być (w najgorszym przypadku) czasochłonne, ale jest proste, trochę gorzej jest z usuwaniem elementu.

 

Przedstawiony powyżej algorytm rozstrzygania konfliktów nazywa się adresowaniem (sondowaniem) liniowym. Jeśli oznaczymy przez k klucz szukanego elementu,H funkcję mieszającą, N- liczbę elementów (rozmiar) tablicy oraz h_i pozycję sprawdzana w i-tym kroku, to ciąg h_i wygląda następująco:

h₀=H(k)

h_i=(h₀+i) mod N

 

Ta metoda nie zabezpiecza jednak przed grupowaniem się elementów. Lepsze efekty daje mieszanie podwójne (H’ oznacza drugą funkcję haszującą):

h₀=H(k)

h_i=(h₀+i*H’(k)) mod N

 

W tym przypadku krok H' i rozmiar tablicy N powinny być względnie proste. Niestety nie ma prostego sposobu usuwania elementów. W razie konieczności usuwania można zastosować znacznik dla elementów usuniętych. Taki element jest traktowany jako wolny przy wstawianiu, a jako zajęty ale o wartości pustej przy wyszukiwaniu. Niestety może to prowadzić do szybszego zapełniania tablicy.

 

Inną możliwością, jest stworzenie (wspólnego dla wszystkich pozycji tablicy) obszaru przeniesień, przeszukiwanego liniowo w przypadku wystąpienia kolizji. Jest to rozwiązanie nieco lepsze (dające prostsze algorytmy) lecz wymagające większej pamięci.

 

Istnieje jeszcze trzecie rozwiązanie - można przyspieszyć wyszukiwanie łącząc pozycje zawierające elementy o tej samej wartości w listę.

 

Naturalnym rozszerzeniem ostatniego podejścia jest:

 

B. tablica list

 

Takie rozwiązanie zdecydowanie upraszcza algorytmy (szczególnie usuwanie elementu) dając o wiele lepsze wykorzystanie pamięci.

 

Haszowanie jest skuteczną metodą reprezentacji słownika jeśli potrafimy dobrze dobrać funkcję haszującą (tak aby dawała równomierny rozrzut elementów w tablicy - niestety nie jest to proste). Można to zrobić eksperymentalnie dla słownika stałego (bez Wstaw i Usun). Przy zmiennym słowniku sytuacja jest gorsza (najgorsza gdy wszystkie elementy mają taką samą wartość h(el)). Dodatkowo na efektywność tej metody wpływa stopień zapełnienia tablicy (czym mniej wolnych miejsc tym gorzej).

Oznaczając przez a stopień zapełnienia tablicy (liczba zapisanych elementów / rozmiar) otrzymujemy następujące wyniki:

 

 

algorytm liczba prób dla el Î słownika liczba prób dla el Ï słownika

tablica list 1+a/2 1+a

adresowanie liniowe 0.5+ 1/(2*(1-a)) 0.5+1/(2*(1-a)²)

mieszanie podwójne -ln(1-a)/a 1/(1-α)

 

Przykładowe wartości liczby sondowań w zależności od

wypełnienia tablicy - a 1/2 2/3 3/4 9/10

 

tablica list – trafione 1,25 1,33 1,38 1,45

tablica list – chybione 1,5 1,67 1,75 1,9

adresowanie liniowe – trafione 1,5 2,0 3,0 5,5

adresowanie liniowe – chybione 2,5 5,0 8,5 55,5

podwójne mieszanie – trafione 1,4 1,6 1,8 2,6

podwójne mieszanie – chybione 2.0 3,0 4,0 9,0

 

Widać, że liczba prób nie zależy od wielkości tablicy lecz tylko od stopnia jej zapełnienia.

 

 

Porównanie złożoności poszukiwania dla różnych sposobów implementacji słownika:

 

pesymistyczny średni

wstawianie wyszukiwanie wstawianie wyszukiwanie

trafione chybione

tablica indeksowana kluczem 1 1 1 1 1

tablica (lista) uporządkowana n n n/2 n/2 n/2

tablica (lista) nieuporządkowana 1 n 1 n/2 n

wyszukiwanie binarne n lg n n/2 lg n lg n

BST n n lg n lg n lg n

AVL lub czarno-czerwone lg n lg n lg n lg n lg n

BST randomizowane n* n* lg n lg n lg n

mieszanie 1 n* 1 1 1

 

* - oznacza sytuację możliwą ale bardzo mało prawdopodobną

 

 

Zadania:

31) Dla wybranego przez siebie ciągu elementów, wielkości tablicy i funkcji haszujących zbadaj różnice w liczbie konfliktów przy sondowaniu liniowym i podwójnym haszowaniu.

 

 

Temat 9. Algorytmy grafowe.

Zbiory rozłączne

Dane jest n elementów pogrupowanych w pewną liczbę zbiorów rozłącznych. Każdy zbiór jest identyfikowany przez swojego reprezentanta. Wykonujemy na nich tylko dwie operacje: znajdowanie zbioru do którego należy dany element oraz łączenie dwóch zbiorów.

 

MAKE_SET(x) - tworzy zbiór, którego jedyny element jest wskazany przez x.

UNION(x,y) - łączy dwa zbiory zawierające odpowiednio x i y, w jeden.

FIND(x) - zwraca wskaźnik do reprezentanta zbioru zawierającego x.

 

A. Prosta realizacja lasu zbiorów rozłącznych.

Struktura elementu: class Elem { Object val; Elem parent;...};

 

void MAKE_SET(Elem x)

{x.parent = x; }

void UNION (Elem x, Elem y)

{ LINK(FIND(x),FIND(y)); }

 

void LINK (Elem x, Elem y)

{ y.parent = x; }

 

Elem FIND(Elem x)

{ return x = = x.parent? x: FIND(x.parent);}

 

B. Realizacja lasu z równoważeniem wysokości drzew.

Struktura elementu: class Elem {Object val; Elem parent; int height;};

 

void MAKE_SET(Elem x)

{x.parent = x; x.height=0; }

 

void UNION (Elem x, Elem y)

{ LINK(FIND(x),FIND(y)); }

 

void LINK (Elem x, Elem y)

{ if (x.height > y.height) y.parent=x;

else {x.parent=y;

if (x.height == y.height)

y.height++;

}

 

 

Elem FIND(Elem x)

{ return x == x.parent? x: FIND(x.parent);}

 

 

C. Realizacja lasu z kompresją ścieżki.

Struktura elementu: class Elem {Object val; Elem parent; };

 

void MAKE_SET(Elem x)

{x.parent = x; }

 

void UNION (Elem x, Elem y)

{ LINK(FIND(x),FIND(y)); }

 

void LINK (Elem x, Elem y)

{ y.parent = x; }

 

 

Elem FIND(Elem x)

{ if (x!= x.parent) x.parent = FIND(x.parent);

return x.parent;}

 

Można połączyć rozwiązania B i C.

 

Grafy - reprezentacje grafów, podstawowe algorytmy grafowe

 

Reprezentacje grafów:

1. Lista sąsiedztwa (LS)

2. Macierz sąsiedztwa (MS)

3. Lista krawędzi (LK)