Algorytmy i struktury danych - wykład 6. strona: 1
Wykład 6. Drzewa (struktury drzewiaste)
Drzewa sÄ… jednÄ… z podstawowych struktur danych wykorzystywanych w
programach, które słu\
Ä… do przechowywania danych.
Przykładami drzew są:
" Struktura kartotek plików systemu operacyjnego
" KsiÄ…\
ka, rozdziały, podrozdziały, sekcje, paragrafy etc.
" Drzewo opisujÄ…ce wyra\
enie arytmetyczne
" Drzewo genealogiczne
" itd., itd. . . . .
Jako struktura danych  definicja klasyczna indukcyjna :
Drzewo to niepusty skończony zbiór wierzchołków T, z wyró\
nionym
wierzchołkiem r"T zwanym korzeniem, i pozostałymi wierzchołkami
podzielonymi na k>=0 rozłącznych podzbiorów T1,...,Tk, będących drzewami,
i nazywanych poddrzewami (korzenia) drzewa T.
T
r
.............
r1 r2 rk
T1 T2 Tk
Zauwa\
my  w myśl tej definicji:
" zbiór mo\
e być z powtórzeniami
" zbiór pusty nie jest drzewem
" zbiór jednoelementowy jest drzewem zło\
onym z samego korzenia (baza indukcji
w definicji)
" poddrzewa sÄ… uporzÄ…dkowane (ponumerowane)
Algorytmy i struktury danych - wykład 6. strona: 2
Terminologia:
" węzły (wierzchołki) - elementy zbioru T
" korzeń - wyró\
niony element x
" poddrzewo - podzbiór Ti (poddrzewo ma swój korzeń, który z kolei ma swoje
poddrzewa itd., zatem ka\
dy węzeł jest korzeniem pewnego poddrzewa)
" jeśli x jest korzeniem drzewa T, y korzeniem poddrzewa Ti, to y jest
następnikiem (dzieckiem, potomkiem) dla x, x jest poprzednikiem (rodzicem,
przodkiem) dla y; analogicznie, rozciągając te relacje, mówimy o przodkach i
potomkach w drzewie (jak w drzewie genealogicznym)
" krawędz
drzewa - zbiór dwuelementowy {x, y}, gdzie x jest poprzednikiem dla y
łącząca x i y (w domyśle: krawędz
skierowana od rodzica do dziecka)
" ście\
ka w drzewie - ciąg ró\
nych wierzchołków taki, \
e ka\
de dwa wierzchołki
sąsiednie w tym ciągu są połączone krawędzią
" długość ście\
ki - liczba krawędzi na ście\
ce (liczba węzłów na ście\
ce minus 1)
" stopień węzła x - liczba poddrzew w węz
le x
" liść - węzeł o stopniu równym zero
" wysokość drzewa - długość najdłu\
szej ście\
ki od korzenia do liścia
" głębokość węzła v w drzewie - długość ście\
ki od węzła v do korzenia drzewa
" las - skończony ciąg drzew (mo\
e być pusty)
Algorytmy i struktury danych - wykład 6. strona: 3
ADT Tree.
Operacje:
1. Parent(n, T) - funkcja zwracająca rodzica węzła n w drzewie T. Jeśli n jest
korzeniem, zwracana jest null. W tym kontekście null jest węzłem pustym,
2. LeftMost_Child(n, T) - zwraca pierwsze z lewej dziecko węzła n w drzewie T,
lub null gdy n jest liściem.
3. Right_Sibling(n, T) - zwraca pierwszego z prawej brata węzła n w T (lub null
gdy nie istnieje). Jest to ten węzeł m, który ma tego samego rodzica p co n i
występuje zaraz po n w uporządkowaniu dzieci p od lewej do prawej.
4. Label(n, T) - zwraca etykietę węzła n, (występuje gdy drzewo jest
etykietowane).
5. Create i (v, r, T1 & Ti) - jest jedną z nieskończonej rodziny funkcji (i=0, 1, 2, ).
Create i tworzy nowy węzeł r o etykiecie v i dodaje mu i dzieci będące
korzeniami drzew T1 ... Ti w porzÄ…dku od lewej do prawej. Zwracane jest
drzewo o korzeniu r.
Gdy i = 0, to r jest zarówno korzeniem jak i liściem.
6. Root(T) - zwraca korzeń T lub null je\
eli T jest puste.
7. MakeNull(T) - czyni T drzewem pustym.
Przeszukiwanie drzew.
Jest kilka u\
ytecznych sposobów uporządkowania wszystkich węzłów danego
drzewa.
Trzy najwa\
niejsze to:
1. preorder (wzdłu\
ny)
2. inorder (poprzeczny)
3. postorder (wsteczny)
Rekursywna definicja tych porządków jest następująca:
" Jeśli drzewo T jest puste, to lista pusta jest listą elementów tego drzewa
wypisanych w dowolnym porzÄ…dku: preorder, inorder lub postorder
" Jeśli T składa się z jednego węzła, to węzeł ten stanowi listę elementów T
wypisanych w porzÄ…dku preorder, inorder lub postorder (dowolnym).
W innym wypadku:
Algorytmy i struktury danych - wykład 6. strona: 4
niech T będzie drzewem o korzeniu n i poddrzewach T1 ... Tk, jak na rysunku:
T
r
.............
r1 r2 rk
T1 T2 Tk
wtedy:
1. Listą elementów drzewa T wypisanych w porządku preorder jest korzeń n,
po którym występują, wypisane w porządku preorder, elementy drzew: T1 ,
następnie T2 itd. a\
do Tk.
2. Listą elementów drzewa T wypisanych w porządku inorder są węzły
poddrzewa T1 wypisane w porządku inorder, po nich korzeń n, a następnie
wszystkie węzły poddrzew T2 ... Tk, wypisane równie\
w porzÄ…dku inorder.
3. Listę elementów drzewa T wypisanych w porządku postorder stanowią węzły
poddrzew T1 ... Tk wypisane w porządku postorder. Na końcu listy występuje
węzeł n.
Oto metody przeglÄ…du drzewa:
void Preorder(Node n);
{
Wypisz(n);
For(ka\
de dziecko c węzła n, je\
eli istnieje, w porzÄ…dku od lewej do prawej)
Preorder(c);
} // end preorder}
void Inorder(Node n);
{
If ( n jest liściem ) Wypisz(n);
else
{
Inorder(pierwsze z lewej dziecko n);
Wypisz(n);
Algorytmy i struktury danych - wykład 6. strona: 5
For(ka\
de dziecko c węzła n, poza pierwszym z lewej, w porządku od lewej)
Inorder(c);
}
} // end inorder
Przykład:
WykorzystujÄ…c operacje ADT Tree napiszemy metodÄ™ rekursywnÄ…
wypisywania etykiet wierzchołków drzewa w porządku preorder.
Poni\
sza metoda wypisze w porzÄ…dku preorder wszystkie etykiety poddrzewa o
korzeniu n.
Aby otrzymać wszystkie etykiety drzewa T nale\
y wywołać: Preorder(T.Root()).
public void Preorder(node n)
// wypisuje etykiety potomków wierzchołka n w porządku preorder
{
node c;
System.out.print(T.Label(n));
c = T.LeftMost_Child(n);
while (c != null )
{
Preorder(c);
c = T.Right_Sibling(c);
}
}; //end preorder
Algorytmy i struktury danych - wykład 6. strona: 6
Drzewa binarne
Definicja klasyczna:
Drzewo binarne (nad uniwersum U)
1. zbiór pusty jest drzewem binarnym (nad U)
2. jeśli T1, T2 są drzewami binarnymi (nad U), r "U, to trójka T = (r, T1, T2) jest
drzewem binarnym (nad U), r jest korzeniem drzewa T, T1 jest lewym
poddrzewem drzewa T, T2 jest prawym poddrzewem drzewa T.
T
r
r1 r2
T1 T2
ADT Binary Tree
Operacje:
1. ROOT(T) : zwraca korzeń drzewa T (lepiej - referencję do korzenia)
2. MAKENULL : tworzy puste drzewo binarne (czyli zwraca null)
3. CREATE(v, T1, T2) : krełuje nowe drzewo binarne, o podrzewach T1 i T2
4. LEFT(v, T) : zwraca (referencję do) lewego następnika węzła v w drzewie T
5. RIGHT(v, T) : zwraca (referencję do) prawego następnika węzła v w drzewie T
6. PARENT(v, T) : zwraca (referencję do) poprzednika węzła v w drzewie T
Własności kombinatoryczne:
1. maksymalna mo\
liwa liczba wierzchołków na głębokości d: 2d
2. maksymalna moc drzewa o wysokości h: 2h+1  1
3. wysokość drzewa o n wierzchołkach:
ðÅ‚log2 nûÅ‚ <= h <= n-1
Algorytmy i struktury danych - wykład 6. strona: 7
Podstawowa metoda reprezentacji drzewa binarnego
(reprezentacja referencyjna)
Węzeł: struktura zawierającą:
" pole 'info' (element, ustalonego typu)
" referencję 'left' do korzenia lewego poddrzewa (równy null jeśli lewe poddrzewo
puste)
" referencję 'right' do korzenia prawego poddrzewa (null jeśli puste)
Ponadto niekiedy:
" referencję 'up' do poprzednika (równy null w korzeniu)
oraz referencjÄ™ do korzenia: root
root = null oznacza drzewo puste
ReprezentacjÄ™ referencyjnÄ… drzewa binarnego mo\
na w naturalny sposób
zrealizować wykorzystując zmienne referencyjne: root, left, right.
Algorytmy i struktury danych - wykład 6. strona: 8
Reprezentacja drzew binarnych w Javie
Ka\
dy węzeł w drzewie binarnym będzie obiektem klasy Node, którą
definiujemy następująco:
class Node {
public int info; // element danych (klucz)
public Node left; // lewy potomek
public Node right ; // prawy potomek
public void displayNode() // wyświetlanie zawartości węzła
{
// kod
}
} // end class Node
Samo drzewo będzie obiektem klasy Tree, która zawiera tylko jedno pole,
zmienną root typu Node słu\
ącą do przechowywania odwołania do korzenia drzewa.
Klasa Tree zawiera szereg metod słu\
Ä…cych do odnajdowania, wstawiania oraz
usuwania węzłów, trawersowania (przeglądania) drzewa na ró\
ne sposoby, jak te\

do graficznej prezentacji całego drzewa.
class Tree {
private Node root;;
public Node search (int key)
{
// kod
}
public void insert (int id)
{
// kod
}
public void delete (int id)
{
// kod
}
// ró\
ne inne metody
} // koniec klasy Tree
Algorytmy i struktury danych - wykład 6. strona: 9
Na końcu wykładu zostanie przedstawiony program ilustrujący operacje na drzewie
binarnym .
PrzeglÄ…d (trawersacja) drzewa binarnego
Podana jest referencja do korzenia drzewa binarnego. Nale\
y w systematyczny
sposób przeglądnąć strukturę drzewa i  zbadać wszystkie jego węzły. Algorytmy
przeglądu stanowią bazę większości algorytmów przetwarzających informację w
strukturach drzewiastych.
Przykłady procedury "badanie węzła":
" drukowanie (lub wyświetlenie) zawartości pola info
" sprawdzenie czy jest to wartość szukana
" modyfikacja zawartości
" obliczenie funkcji zale\
nej od wartości w węz
le oraz od wartości poprzednika i/lub
następników (obliczanie wyra\
enia), lub zale\
nej od czasu (np. numerowanie
węzłów)
Trzy podstawowe porzÄ…dki przeglÄ…du drzewa binarnego:
(I) Przegląd w porządku zstępującym (prefiksowy, "preorder") - KLP
Jeśli drzewo jest puste to nic nie rób, w przeciwnym przypadku:
1. zbadaj korzeń
2. (rekurencyjnie) przeglądnij lewe poddrzewo w porządku zstępującym
3. (rekurencyjnie) przeglądnij prawe poddrzewo w porządku zstępującym
Prosta natychmiastowa realizacja w konkretnym języku programowania: za
pomocÄ… rekurencyjnej procedury (funkcji).
(II) PorzÄ…dek symetryczny (infiksowy, "inorder") - LKP
Główne zastosowanie: w strukturach dla wyszukiwania informacji.
Jeśli drzewo jest puste to nic nie rób, w przeciwnym przypadku:
1. (rekurencyjnie) przeglÄ…dnij lewe poddrzewo w porzÄ…dku symetrycznym
2. zbadaj korzeń
3. (rekurencyjnie) przeglÄ…dnij prawe poddrzewo w porzÄ…dku symetrycznym.
Algorytmy i struktury danych - wykład 6. strona: 10
(III) Porządek wstępujący (postfiksowy, "postorder") - LPK
Jeśli drzewo jest puste to nic nie rób, w przeciwnym przypadku:
1. (rekurencyjnie) przeglądnij lewe poddrzewo w porządku wstępującym
2. (rekurencyjnie) przeglądnij prawe poddrzewo w porządku wstępującym
3. zbadaj korzeń
Algorytm dla przeglÄ…du preorder:
(a) rekurencyjny:
void preorder (Node p ) {
if ( p != null ) {
zbadaj (p); // System.out. print(p.info +   );
preorder ( p.left );
preorder ( p.right );
}
}
Wywołanie funkcji: preorder(root)
Uwaga "estetyczna": wygodniej testować czy null po wywołaniu ni\
przed. Równie\
z
powodu zgodności z definicją.
ZÅ‚o\
oność algorytmu przeglądu drzewa wynosi Ś(n).
Dokładniej:
Jest to liczba wywołań procedury preorder() i wynosi liczba węzłów + liczba pustych
referencji = n + n + 1 = 2n +1
(b) A
atwa wersja iteracyjna ze stosem  algorytm dla porzÄ…dku inorder:
Algorytmy i struktury danych - wykład 6. strona: 11
S = new Stack(); // tworzenie stosu pustego
p = T.Root(); // p jest referencjÄ… bie\
Ä…cÄ…
while ( p != null || ! S.is_empty() )
{
if ( p != null ) {
S.push ( p);
p = p. left; // przejście do lewego poddrzewa
}
else {
p = S.pop(); //wierzchołek stosu
zbadaj(p) ;
p = p.right; //przejście do prawego poddrzewa
}
}
ZÅ‚o\
oność: jak poprzednio  liniowa.
Po\
yteczne uwagi:
" powy\
szy algorytm iteracyjny dla inorder bardzo Å‚atwo "przerabia siÄ™" na
preorder i nieco trudniej dla postorder;
" jeśli dana jest lista węzłów drzewa binarnego w którymkolwiek z powy\
szych
porządków, to oczywiście nie definiuje ona drzewa jednoznacznie
" jeśli dana jest lista w preorder oraz druga lista w inorder, to one obie definiują
jednoznacznie drzewo binarne (przy zało\
eniu \
e zawartości pól info nie
powtarzajÄ… siÄ™).
Algorytmy i struktury danych - wykład 6. strona: 12
Tablicowe reprezentacje drzewa binarnego
w wybranym porządku (ale nie dowolnym) wypisana zawartość pola info
wierzchołków plus dodatkowe informacje pozwalające zakodować strukturę.
Przykład:
reprezentacja zstępująca ze znacznikami poddrzew w kolejności preorder, lista
trójek u = (info, L, R), gdzie
" 'info' jak w węz
le
" L jest równe 1 jeśli węzeł ma niepuste lewe poddrzewo, w przeciwnym
przypadku 0
" R jest równe 1 jeśli węzeł ma niepuste prawe poddrzewo, w przeciwnym
przypadku 0
Jednoznaczność reprezentacji wynika z poni\
szego twierdzenia o podobieństwie
drzew binarnych.
Def.
Drzewa binarne T, T' są podobne, jeśli
1. T = T' = ", lub
2. T `" ", T' `" ", oraz lewe poddrzewo T jest podobne do lewego poddrzewa T' oraz
prawe poddrzewo T jest podobne do prawego poddrzewa T'.
Algorytmy i struktury danych - wykład 6. strona: 13
Twierdzenie
Niech
u1, ..., un  węzły drzewa T w porządku preorder
u'1, ..., u'n'  węzły drzewa T' w porządku preorder
Wówczas T i T' są podobne wtedy i tylko wtedy gdy
1. n = n'
2. L[ui] = L[u'i], R[ui] = R[u'i], i=1,...,n.
Wniosek:
poprawny jest poni\
szy algorytm kopiowania drzewa binarnego:
// utwórz T' = kopia drzewa T
if ( T.is_empty() ) return null ;
w = pusta struktura wierzchołka;
T' = (w, ", ") ; // tylko korzeń
// przeglÄ…daj preorder synchronicznie (jeden algorytm) drzewa T, T', stosujÄ…c
// następująca metodę visit(p)
void visit(Node p, Node p') // p jest w T, p' jest w T'
{
p'.info = p.info;
if ( L[p] )
utwórz węzeł i dowią\
z lewej do p'
if ( R[p] )
utwórz węzeł i dowią\
z prawej do p'
} // end visit
return T'
ZÅ‚o\
oność algorytmu kopiowania drzewa wynosi Ś(n).
Algorytmy i struktury danych - wykład 6. strona: 14
Drzewo reprezentujÄ…ce wyra\
enia algebraiczne
Za pomocÄ… drzew binarnych mo\
na reprezentować wyra\
enia algebraiczne
składające z dwuargumentowych operatorów arytmetycznych, takich jak +, -, * oraz /.
W takim przypadku korzeń przechowuje operator u\
yty w wyra\
eniu, a pozostałe
węzły  nazwy zmiennych, np. A, B lub C bądz
tez kolejny operator. Ka\
de
poddrzewo stanowi poprawne wyra\
enie algebraiczne.
Na przykład wyra\
enie: A*(B+C) jest reprezentowane przez poni\
sze drzewo.
*
A +
B C
DokonujÄ…c przeglÄ…du powy\
szego drzewa w trzech poznanych porzÄ…dkach
otrzymamy następujące listy węzłów:
Preorder: * A + B C  notacja polska (NP)
Inorder: A * ( B + C )  notacja infiksowa
Postorder: A B C + * - odwrotna notacja polska (ONP)
Algorytmy i struktury danych - wykład 6. strona: 15
Drzewa BST (binary search tree) drzewa poszukiwań binarnych
Wykorzystywane jako realizacja słownika:
" search(x)
" insert(x)
" delete(x)
" construct
Definicja
Drzewo BST to drzewo binarne, w którym dla dowolnych węzłów x, y
zachodzi:
" jeśli x jest w lewym poddrzewie o korzeniu y, to x" jeśli x jest w prawym poddrzewie o korzeniu y, to x>y
Fakt.
Drzewo binarne jest BST wtedy i tylko wtedy gdy lista jego węzłów
w porzÄ…dku inorder jest ciÄ…giem rosnÄ…cym.
Dopuszczalne jest równie\
stosowanie nieostrej nierówności.
Zanim zostanÄ… przedstawione algorytmy realizujÄ…ce podstawowe
operacje na drzewach BST, poka\
emy jak Å‚atwo mo\
na w takich drzewach
wyznaczyć wartość minimalną i maksymalną.
Algorytmy i struktury danych - wykład 6. strona: 16
Aby znalez
ć wartość minimalną, zaczynając od korzenia, nale\
y przejść
jego lewego potomka, następnie do lewego potomka tego potomka itd.
Czynność ta jest powtarzana, a\
do momentu gdy kolejny węzeł nie
będzie miał lewego potomka. Ten węzeł będzie poszukiwaną wartością
minimalnÄ… drzewa.
public Node minimum() // zwraca węzeł o minimalnej wartości
// klucza
{
Node curr, last;
curr = root; // zaczynamy od korzenia
while( curr != null) // a\
do skrajnie lewego potomka
{
last = curr; // zapamiętujemy węzeł
curr = curr.left;// przechodzimy do lewego potomka
}
return last;
}
Znajdowanie maksymalnej wartości w drzewie BST jest realizowane w
analogiczny sposób, przy czym w tym przypadku nale\
y przejść do prawego
potomka i kontynuować proces a\
do momentu napotkania węzła, który nie ma
prawego potomka.
Operacja wyszukiwania  search (x)
we:
referencja root do korzenia drzewa BST w reprezentacji
referencyjnej, oraz element x
wy:
referencja p do węzła zawierającego x, równy NULL jeśli elementu x
nie ma w drzewie
Algorytmy i struktury danych - wykład 6. strona: 17
Node search(int x);
{
Node p = root;
while (p != NULL) && ( x != p.info) {
if (x < p. info) p = p.left
else p = p.right;
}
return p;
}
wywołanie
Node ref = search(x); // ref == null jeśli brak x
ZÅ‚o\
oność obliczeniowa:
" mierzona jest liczbą wykonanych porównań pól info w węzłach (są
instrukcjami dominujÄ…cymi)
" w najgorszym przypadku ich liczba jest proporcjonalna do wysokości
drzewa
" wysokość drzewa w najgorszym przypadku jest równa n-1, gdzie n jest
liczbą węzłów
" zatem pesymistyczna zło\
oność algorytmu wyszukiwania w drzewie
BST wynosi Ś(n) (zło\
oność średnia jest znacznie lepsza).
Operacja wstawiania  insert(x).
Zauwa\
my, \
e n węzłów drzewa BST wypisanych w kolejności rosnącej
a(1) a(2) a(3) . . . a(n)
dzieli przestrzeń pozostałych elementów na n+1 przedziałów:
" przedział 0: elementy mniejsze ni\
a(1)
" przedział 1: elementy większe ni\
a(1), mniejsze ni\
a(2)
" . . . .
" przedział n-1:elementy większe ni\
a(n-1), mniejsze ni\
a(n)
" przedział n: elementy większe ni\
a(n)
Algorytmy i struktury danych - wykład 6. strona: 18
Ka\
dy przedział odpowiada jednej referencji NULL w jakimś węz
le
drzewa BST; na tej referencji kończy się poszukiwanie elementu nie
istniejÄ…cego w drzewie.
Zatem element nowy nale\
y zapisać w nowym liściu dowiązanym w
miejscu, na którym zakończy się wyszukiwanie tego elementu.
W tym celu podczas wyszukiwania nale\
y pamiętać referencja do
poprzednika aktualnego węzła na ście\
ce.
Na poprzednim rysunku pole v.left, równe NULL, reprezentuje wartości
większe ni\
12 i mniejsze ni\
15.
//we: root, x jak poprzednio; zakładamy, \
e x nie ma w drzewie,
//wy: drzewo z dodanym nowym liściem zawierającym x
void insert (int x) {
Node s, p, prev; // zmienne referencyjne
s = new Node() ; // utwórz nowy węzeł
s.info = x ; s.left= NULL; s.right= NULL;
if (root == null) root = s; // drzewo puste
else {
p = root; prev = NULL; // bie\
Ä…cy i poprzednik
while ( p != NULL ) {
Algorytmy i struktury danych - wykład 6. strona: 19
prev = p;
if ( x < p.info )
p = p.left
else
p = p.right;
}
// dowiÄ…\
nowy węzeł do prev
if (x < prev.info ) prev.left= s
else prev.right= s
}
}
ZÅ‚o\
oność obliczeniowa jak dla operacji search.
Elegancka wersja rekurencyjna operacji insert(x):
Node insert_r (Node p, int x) {
// rekurencyjna wersja algorytmu operacji insert
// istotny jest sposób przekazania pierwszego parametru: przez referencję
if (p == NULL) {
p = new Node(); //new node
p.info = x;
p.left = NULL;
p.right = NULL;
return p;
}
else
if ( x < p.info )
insert_r (p.left, x)
else
insert_r (p.right, x)
}
Wywołanie metody: q = insert_r (root, x)
Algorytmy i struktury danych - wykład 6. strona: 20
Operacja delete (x)
Nale\
y odłączyć od drzewa węzeł zawierający x.
1. Wyszukaj węzeł p taki, \
e p.info == x
Niech p = q.left
(jeśli p = q.right to postępowanie symetryczne).
2. Rozwa\
przypadki:
2.1. p ma oba poddrzewa puste (p jest liściem):
q
t
p
x y
q.left = NULL;
koniec.
2.2. p ma dokładnie jedno poddrzewo niepuste,
niech p.left != NULL
(jeśli p.right != NULL to symetrycznie):
q
t
p
x y
z
q.left = p.left;
koniec.
Algorytmy i struktury danych - wykład 6. strona: 21
2.3. Oba poddrzewa węzła p są niepuste:
2.3.1: wyznacz węzeł s zawierający klucz następny w kolejności rosnącej po
kluczu x (od węzła p idz
raz w prawo i do końca w lewo)
2.3.2: p.info = s.info (wartość x skasowana)
2.3.4: usuń węzeł s (s ma puste lewe poddrzewo,
mo\
na zastosować 2.1 lub 2.2).
// zamiast s = następny_w_bst(x)
// mo\
na s = poprzedni_w_bst(x)
Liczba operacji proporcjonalna do długości ście\
ki od korzenia do węzła p
oraz s (jest to jedna ście\
ka), zatem zło\
oność obliczeniowa jest taka jak
dla operacji search oraz insert.
Komentarz
dotyczący zło\
oności obliczeniowej operacji słownika dla drzewa binarnych
poszukiwań:
Jeśliby pod uwagę brać tylko zło\
oność pesymistyczną, to posługiwanie
się strukturą BST byłoby nieopłacalne (dla listy osiągamy tę samą
zło\
oność).
Zachodzi jednak następujące twierdzenie:
Algorytmy i struktury danych - wykład 6. strona: 22
Twierdzenie:
Jeśli drzewo BST jest puste i wykonujemy wstawienie n ró\
nych
elementów w losowej kolejności, to oczekiwana wysokość drzewa wynosi
Åš(log2 n).
Fakty:
" Operacje delete wykonane po ciÄ…gu operacji insert zachowujÄ…
losowość drzewa BST (w sensie losowej permutacji wstawianych
elementów)
" Operacje insert wykonane po operacjach delete powodujÄ… \
e drzewo
BST przestaje być losowe, empirycznie, średni czas operacji wzrasta do
n1/2.
" (empiryczny) Jeśli w operacji delete w przypadku 2.3 losujemy czy
przepisywać następny element s czy poprzedni, to oczekiwana
długość ście\
ki dostępu jest logarytmiczna.
Przykład.
// tree.java
// Program demonstruje operacje na drzewach binarnych BST
import java.io.*;
import java.util.*; // potrzebne bo u\
ywamy klasy Stack
class Node
{
public int info; // element danych (klucz)
public Node left; // lewy potomek węzła
public Node right; // prawy lewy potomek węzła
public void displayNode() // wyświetlenie zawartości węzła
{
System.out.print('{');
System.out.print(info);
System.out.print("} ");
}
} // koniec klasy Node
////////////////////////////////////////////////////////////////
class Tree
{
public Node root; // pierwszy węzeł drzewa
// -------------------------------------------------------------
public Tree() // konstruktor
{ root = null; } // na razie drzewo jest puste
// -------------------------------------------------------------
Algorytmy i struktury danych - wykład 6. strona: 23
public Node search(int key)// odszukanie węzła o podanej wartości klucza
{ // (zakładamy, \
e drzewo nie jest puste)
Node p = root; // zaczynamy od korzenia drzewa
while(p.info != key) // dopóki nie odnaleziono,
{
if(key < p.info) // przechodzimy na lewo?
p = p.left;
else // czy na prawo?
p = p.right;
if(p == null) // jeśli brak potomka,
return null; // nie odnaleziono węzła
}
return p; // odnaleziono węzeł
} // koniec metody search()
// -------------------------------------------------------------
public void insert (int x) {
s = new Node() ; // utwórz nowy węzeł
s.info = x ;
s.left = null;
s.right= null;
if (root == null) root = s; // drzewo puste
else
{
p = root; prev = null; // bie\
Ä…cy i poprzednik
while ( p != null ) {
prev = p;
if ( x < p.info )
p = p.left;
else
p = p.right;
}
// dowiÄ…\
nowy węzeł do prev
if (x < prev.info ) prev.left= s;
else prev.right= s;
}
} // koniec metody insert()
// -------------------------------------------------------------
public boolean delete(int key) // usunięcie węzła o podanej wartości
// klucza
{ // (zakładamy \
e drzewo nie jest puste)
Node p = root;
Node parent = root;
boolean isLeft = true;
while(p.info != key) // szukamy węzła
{
parent = p;
if(key < p.info) // czy w lewo?
{
isLeft = true;
p = p.left;
}
else // czy w prawo?
{
isLeft = false;
p = p.right;
}
if(p == null) // koniec,
return false; // nie znaleziono węzła
Algorytmy i struktury danych - wykład 6. strona: 24
} // koniec pętli while
// znaleziono węzeł do usunięcia
// jeśli nie ma potomków, usuwamy węzeł
if(p.left==null && p.right==null)
{
if(p == root) // jeśli to korzeń,
root = null; // opró\
niamy drzewo
else if(isLeft)
parent.left = null; // odłączamy węzeł
else // od rodzica
parent.right = null;
}
// jeśli brak prawego potomka, zastępujemy węzeł lewym poddrzewem
else if(p.right==null)
if(p == root)
root = p.left;
else if(isLeft)
parent.left = p.left;
parent.right = p.left;
// jeśli brak lewego potomka, zastępujemy węzeł prawym poddrzewem
else if(p.left==null)
if(p == root)
root = p.right;
else if(isLeft)
parent.left = p.right;
else
parent.right = p.right;
else
// węzeł ma dwa potomki, zastępujemy go zatem jego następnikiem
{
// określamy następnika usuwanego węzła (p)
Node succ = getSuccessor(p);
// łączymy rodzica węzła p z węzłem successor
if(p == root)
root = succ;
else if(isLeft)
parent.left = succ;
else
parent.right = succ;
// dołączamy następnika do węzła p jako lewego potomka
succ.left = p.left;
} // koniec else - (gdy węzeł ma dwa potomki)
// (następnik nie mo\
e mieć lewego potomka)
return true; // udało się
} // koniec metody delete()
// -------------------------------------------------------------
// metoda zwraca węzeł o kolejnej wartości większej od wartości
// węzła przekazanego jako argument delNode
// metoda przechodzi do prawego potomka, a następnie do lewego
// potomka tego węzeła i kolejnych węzłów
private Node getSuccessor(Node delNode)
{
Node succParent = delNode;
Algorytmy i struktury danych - wykład 6. strona: 25
Node succ = delNode;
Node p = delNode.right; // przechodzimy do prawego potomka
while(p != null) // do momentu gdy ju\
nie będzie
{ // lewych potomków,
succParent = succ;
succ = p;
p = p.left; // przechodzimy do lewego potomka
}
// jeśli następnik nie jest
if(succ != delNode.right) // prawym potomkiem,
{ // dołączamy go
succParent.left = succ.right;
succ.right = delNode.right;
}
return succ;
}
// -------------------------------------------------------------
public void traverse()
{
System.out.println("Preorder: ");
preOrder(root);
System.out.println("\nInorder: ");
inOrder(root);
System.out.println("\nPostorder: ");
postOrder(root);
System.out.println();
}
// -------------------------------------------------------------
private void preOrder(Node p)
{
if(p != null)
{
System.out.print(p.info + " ");
preOrder(p.left);
preOrder(p.right);
}
}
// -------------------------------------------------------------
private void inOrder(Node p)
{
if(p != null)
{
inOrder(p.left);
System.out.print(p.info + " ");
inOrder(p.right);
}
}
// -------------------------------------------------------------
private void postOrder(Node p)
{
if(p != null)
{
postOrder(p.left);
postOrder(p.right);
System.out.print(p.info + " ");
}
}
// -------------------------------------------------------------
public void displayT(Node p, int h)
Algorytmy i struktury danych - wykład 6. strona: 26
{
if(p != null)
{
displayT(p.right, h+2);
for(int j=0; j System.out.println(p.info);
displayT(p.left, h+2);
}
}
// -------------------------------------------------------------
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
"......................................................");
while(isRowEmpty==false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j=0; j System.out.print(' ');
while(globalStack.isEmpty()==false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
System.out.print(temp.info);
localStack.push(temp.left);
localStack.push(temp.right);
if(temp.left != null ||
temp.right != null)
isRowEmpty = false;
}
else
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for(int j=0; j System.out.print(' ');
} // koniec pętli while (globalStack nie jest pusty)
System.out.println();
nBlanks /= 2;
while(localStack.isEmpty()==false)
globalStack.push( localStack.pop() );
} // koniec pętli while (czy isRowEmpty wynosi false)
System.out.println(
"......................................................");
} // koniec metody displayTree()
Algorytmy i struktury danych - wykład 6. strona: 27
// -------------------------------------------------------------
} // koniec klasy Tree
////////////////////////////////////////////////////////////////
class TreeApp
{
public static void main(String[] args) throws IOException
{
int value, op;
Tree T = new Tree();
T.insert(50);
T.insert(25);
T.insert(75);
T.insert(12);
T.insert(37);
T.insert(43);
T.insert(30);
T.insert(33);
T.insert(87);
T.insert(93);
System.out.println(" Utworzono drzewo wstawiajac kolejno: ");
System.out.println(" 50, 25, 75, 12, 37, 43, 30, 33, 87, 93");
System.out.println(
"......................................................");
T.displayTree();
System.out.println(
"......................................................");
T.displayT(T.root,1);
do
{
System.out.println("Operacje na drzewie BST");
System.out.println(
"......................................................");
System.out.println("(i)-wstaw ");
System.out.println("(f)-wyszukaj");
System.out.println("(d)-usun");
System.out.println("(t)-trawersowanie: ");
System.out.println("(s)-wypisywanie ");
System.out.println("(k)-koniec ");
System.out.println("Wpisz litere by wykonac polecenie, ");
System.out.println(
"......................................................");
op = getChar();
switch(op)
{
case 's':
T.displayTree();
break;
case 'i':
System.out.print("Wpisz wartosc klucza wstawianego wezla: ");
value = getInt();
T.insert(value);
T.displayTree();
break;
case 'f':
System.out.print("Wpisz wartosc klucza poszukiwanego wezla: ");
value = getInt();
Node found = T.search(value);
if(found != null)
Algorytmy i struktury danych - wykład 6. strona: 28
{
System.out.print("Znaleziono wezel: ");
found.displayNode();
System.out.print("\n");
}
else
System.out.print("Nie udalo sie znalezc wezla o kluczu ");
System.out.print(value + '\n');
break;
case 'd':
System.out.print("Podaj wartosc klucza usuwanego wezla: ");
value = getInt();
boolean didDelete = T.delete(value);
if(didDelete)
System.out.print("Usunieto wezel " + value + '\n');
else
System.out.print("Nie udalo sie usunac wezla o kluczu ");
System.out.print(value + '\n');
break;
case 't':
T.traverse();
break;
case 'k':
System.out.println("Koniec ");
break;
default:
System.out.print("Nieprawidlowe dane\n");
} // koniec instrukcji switch
}while (op != 'k'); // koniec petli while
} // koniec metody main()
// -------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// -------------------------------------------------------------
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
// -------------------------------------------------------------
} // koniec klasy TreeApp
////////////////////////////////////////////////////////////////