Algorytmy i struktury danych
Temat: Metody równowa
Ŝ
enia drzew BST
Algorytmy i struktury danych
Temat: Metody równowa
Ŝ
enia drzew BST
2
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
K
B
P
R
M
D
B
M
K
P
R
D
RóŜne drzewa BST zawierające te same dane
a)
b)
c)
B
M
D
K
R
P
3
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Ile maksymalnie w
ę
złów mo
Ŝ
e mie
ć
drzewo binarne w zale
Ŝ
no
ś
ci
od wysoko
ś
ci h?
...
...
...
n= 2
h
-1
2
h-1
h
...
...
...
16383= 2
14
-1
2
13
=8192
14
...
2047= 2
11
-1
2
10
=1024
11
...
...
...
15= 2
4
-1
2
3
=8
4
7= 2
3
-1
2
2
=4
3
3= 2
2
-1
2
1
=2
2
1= 2
1
-1
2
0
=1
1
W
ę
złów
w drzewie
W
ę
złów na
poziomie h
Wysoko
ść
dla np. n=10 000
14
3
,
13
10001
log
)
1
(
log
2
2
=
=
=
=
+
≤
n
h
4
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Sposoby równowa
Ŝ
enia drzewa BST:
1.
Uporz
ą
dkowanie danych przed tworzeniem drzewa
(wybór na korze
ń
elementu ze
ś
rodka listy danych)
2.
Stałe poprawianie drzewa w miar
ę
wstawiania w
ę
złów
(np. z wykorzystaniem rotacji; przykład: drzewa AVL,
drzewa czerwono-czarne))
5
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Tworzenie drzewa po uprzednim posortowaniu jego
elementów:
przed utworzeniem drzewa dane porz
ą
dkowane s
ą
w tablicy;
na korze
ń
drzewa wybierany jest element bliski warto
ś
ci
ś
rodkowej; element ten wyznacza podział tablicy na lew
ą
i praw
ą
podtablic
ę
;
lewy nast
ę
pnik korzenia:
ś
rodek lewej podtablicy;
prawy nast
ę
pnik korzenia:
ś
rodek prawej podtablicy;
otrzymane drzewo jest dobrze zrównowa
Ŝ
one
( liczba elementów na drodze od korzenia do dowolnego
li
ś
cia jest rz
ę
du log
2
n );
6
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Tworzenie drzewa po uprzednim posortowaniu jego
elementów (idea algorytmu):
void balance(T data[ ], int first, int last) {
if (first<=last) {
int mid=(first+last)/2;
insert(data[mid]);
balance(data, first, mid-1);
balance(data, mid+1, last);
}
}
7
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Przykład u
Ŝ
ycia funkcji balance
9
8
7
6
5
4
3
2
1
0
Strumie
ń
uporz
ą
dkowany
6
4
3
2
0
7
8
9
1
5
Strumie
ń
danych
9
8
7
6
5
4
3
2
1
0
9
8
7
6
5
4
3
2
1
0
9
8
7
6
5
4
3
2
1
0
9
8
7
6
5
4
3
2
1
0
4
1
7
8
5
2
0
3
6
9
8
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Metoda poprawiania struktury drzewa:
Zasadnicza wada poprzedniej metody: przed utworzeniem
drzewa dane nale
Ŝ
ało posortowa
ć
;
Inny sposób (bez sortowania): rozło
Ŝ
y
ć
niezrównowa
Ŝ
one
drzewo i zło
Ŝ
y
ć
je ponownie;
Stosunkowo efektywny mo
Ŝ
e okaza
ć
si
ę
algorytm DSW
(C.
D
ay, Q.
S
tout, B.
W
arren):
1)
przekształcenie drzewa w winoro
ś
l;
2)
przekształcenie winoro
ś
li w drzewo zrównowa
Ŝ
one
(z wykorzystaniem rotacji).
9
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Przekształcenie drzewa w winoro
ś
l:
UtwórzWinoro
ś
l (root, n ) {
tmp=root;
while ( tmp != 0 )
if ( tmp ma lewy nast
ę
pnik) {
obró
ć
lewy nast
ę
pnik w prawo wokół tmp;
ustaw tmp na nast
ę
pnik, który stał si
ę
poprzednikiem;
}
else
ustaw tmp na jego prawy nast
ę
pnik;
}
10
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Przykład przekształcenia drzewa w winoro
ś
l
5
10
20
30
40
15
25
28
23
tmp
5
10
20
30
40
15
25
28
23
tmp
5
10
20
15
tmp
30
40
28
23
25
5
10
20
15
tmp
30
40
28
25
23
5
10
20
15
tmp
28
40
25
23
30
11
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Zło
Ŝ
ono
ść
tworzenia winoro
ś
li
Przypadek optymistyczny (drzewo jest ju
Ŝ
winoro
ś
l
ą
):
p
ę
tla while wykonuje si
ę
n razy, nie s
ą
wykonywane
Ŝ
adne
rotacje (tylko n instrukcji podstawienia); zatem T(n)=O(n)
Przypadek pesymistyczny (korze
ń
nie ma prawego nast
ę
pnika):
p
ę
tla while wykonuje si
ę
2n – 1 razy, w tym wykonywanych jest
n – 1 rotacji; zatem: T(n)=O(n)
PokaŜ algorytm
12
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Tworzenie drzewa zrównowa
Ŝ
onego
UtwórzDrzewoZrównowa
Ŝ
one( n ) {
wykonaj n-m rotacji w lewo, zaczynaj
ą
c od prawego nast
ę
pnika
korzenia winoro
ś
li;
while (m>1) {
m =
m/2
;
wykonaj m rotacji w lewo, zaczynaj
ą
c od prawego nast
ę
pnika
korzenia winoro
ś
li;
}
}
;
1
2
m
)
1
n
(
log
2
−
=
+
13
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Przykład tworzenia drzewa zrównowa
Ŝ
onego
40
5
15
28
25
23
30
10
20
5
15
10
28
23
20
40
25
30
30
10
15
20
28
23
25
40
5
winorośl: n=9
m=2
3
-1=7
n-m=9-7=2
40
20
23
25
28
10
5
15
30
drzewo zrównowaŜone
14
Algorytmy i struktury danych
Zło
Ŝ
ono
ść
przekształcania winoro
ś
li w drzewo
zrównowa
Ŝ
one
Liczba rotacji w ramach p
ę
tli while:
Ł
ą
czna liczba rotacji:
)
1
n
(
log
n
)
1
2
(
1
3
7
15
...
)
1
2
(
1
)
1
n
(
log
1
i
2
i
1
)
1
n
(
log
2
2
∑
−
+
=
−
+
+
−
=
−
=
=
+
+
+
+
+
−
)
1
n
(
log
m
n
2
)
)
1
n
(
log
n
(
m
n
2
2
+
−
−
=
=
+
−
+
−
T(n)=O(n)
1
q
1
q
a
S
n
1
n
−
−
=
PokaŜ algorytm
15
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Zło
Ŝ
ono
ść
równowa
Ŝ
enia drzewa
T(n) = max { O(n), O(n) } = O(n)
1.
Przekształcenie drzewa niezrównowa
Ŝ
onego w winoro
ś
l: O(n)
2.
Przekształcenie winoro
ś
li w drzewo zrównowa
Ŝ
one: O(n)
16
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Metoda poprawiania drzewa w miar
ę
wstawiania
w
ę
złów
Idea: elementy (dane), które wykorzystywane s
ą
najcz
ęś
ciej
przesuwane s
ą
w gór
ę
drzewa (blisko korzenia)
1. Drzewa samonaprawiaj
ą
ce si
ę
2. Ukosowanie (ang. splaying) drzewa
17
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Drzewa samonaprawiaj
ą
ce si
ę
Idea:
Przy si
ę
ganiu do elementu nast
ę
puje korekta struktury drzewa
poprzez:
a) pojedyncz
ą
rotacj
ę
(wokół poprzednika)
b) przesuni
ę
cie elementu do korzenia
18
Algorytmy i struktury danych
Rotacja
Lewa rotacja (lub „rotacja w lewo”) w
ę
zła
y
wokół w
ę
zła
x
Polega na obrocie w
ę
zła
y
wokół wyró
Ŝ
nionego w
ę
zła
x
przeciwnie do ruchu wskazówek zegara;
W wyniku rotacji w
ę
zeł
y
staje si
ę
nowym korzeniem
poddrzewa, w
ę
zeł
x
zostaje jego lewym synem, a lewy syn
w
ę
zła
y
zostaje prawym synem w
ę
zła
x
;
Mo
Ŝ
na j
ą
wykona
ć
, je
Ŝ
eli prawy syn w
ę
zła
y
nie jest NULL;
x
α
y
γ
β
y
x
γ
β
α
19
Algorytmy i struktury danych
Rotacja
Prawa rotacja (lub „rotacja w prawo”) w
ę
zła
x
wokół w
ę
zła
y
:
Polega na obrocie w
ę
zła
x
wokół wyró
Ŝ
nionego w
ę
zła
y
zgodnie z ruchem wskazówek zegara;
W wyniku rotacji w
ę
zeł
x
staje si
ę
nowym korzeniem
poddrzewa, w
ę
zeł
y
zostaje jego prawym synem, a prawy syn
w
ę
zła
x
zostaje lewym synem w
ę
zła
y
;
Mo
Ŝ
na j
ą
wykona
ć
, je
Ŝ
eli lewy syn w
ę
zła
x
nie jest NULL;
x
α
y
γ
β
y
x
γ
β
α
20
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Ilustracja idei: si
ę
gni
ę
cie do w
ę
zła D
P
F
E
D
A
H
Q
a) rotacja w prawo w
ę
zła D
P
D
A
F
H
E
Q
21
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Ilustracja idei: si
ę
gni
ę
cie do w
ę
zła R
b) przesuni
ę
cie w
ę
zła D do korzenia
(metod
ą
podwójnej rotacji w prawo)
D
A
Q
F
H
E
P
P
F
E
D
A
H
Q
P
D
A
F
H
E
Q
22
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Ukosowanie (1985)
Jest to modyfikacja strategii naprawiania drzewa poprzez
przenoszenie do korzenia.
Korekta
struktury
drzewa
nast
ę
puje
poprzez
stosowanie
pojedynczych rotacji parami, w kolejno
ś
ci zale
Ŝ
nej od powi
ą
zania
dziecka, rodzica i rodzica rodzica.
Wyró
Ŝ
nia si
ę
trzy przypadki (dost
ę
p do w
ę
zła R, którego rodzicem
jest Q, którego z kolei rodzicem jest P:
1.
Rodzic Q w
ę
zła R jest korzeniem.
2.
Układ jednorodny: w
ę
zeł R jest lewym dzieckiem Q, za
ś
Q
jest lewym dzieckiem P (lub kiedy w obu relacjach chodzi
o prawe dziecko).
3.
Układ niejednorodny: w
ę
zeł R jest lewym dzieckiem Q, za
ś
Q jest prawym dzieckiem P (lub kiedy R jest prawym
dzieckiem, natomiast Q lewym).
23
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Ukosowanie – przykład (po si
ę
gni
ę
ciu do w
ę
zła B)
Przypadek 1. Rodzic węzła B jest korzeniem
(rotacja w prawo węzła B)
Q
B
A
C
R
B
A
R
C
Q
24
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Ukosowanie – przykład (po si
ę
gni
ę
ciu do w
ę
zła F)
Przypadek 2. Układ jednorodny
(rotacja w prawo węzła K oraz rotacja w prawo węzła F)
F
A
Q
L
K
P
G
P
K
F
L
Q
G
A
K
F
G
A
P
Q
L
25
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Ukosowanie – przykład (po si
ę
gni
ę
ciu do w
ę
zła N)
Przypadek 2. Układ niejednorodny
(rotacja w lewo węzła N oraz rotacja w prawo węzła N)
P
K
A
N
Q
O
M
P
N
K
O
Q
M
A
N
K
M
A
P
Q
O
26
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Idea algorytmu ukosowania
(przenoszenia w
ę
zła do korzenia)
Ukosowanie ( P, Q, R ) {
while (R nie jest korzeniem)
if (rodzic R jest korzeniem)
wykonaj pojedyncze ukosowanie: rotacj
ę
R wokół jego
rodzica;
else
if (R jest ze swoimi przodkami w układzie jednorodnym)
wykonaj ukosowanie jednorodne: najpierw rotuj Q
wokół P, potem R wokół Q;
else
// R jest ze swoimi przodkami w układzie niejednorodnym
wykonaj ukosowanie niejednorodne: najpierw rotuj R
wokół Q, potem R wokół P;
}
27
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Przykład ukosowania (po dost
ę
pie do w
ę
zła E)
P
N
K
O
E
L
I
A
Q
J
F
P
N
E
O
I
A
Q
F
J
K
L
E
A
P
I
N
F
J
K
L
Q
O
Stan po pierwszej parze rotacji
Stan po drugiej parze rotacji
28
Algorytmy i struktury danych
Techniki równowaŜenia drzew BST
Przykład ukosowania c.d. (dost
ę
p do w
ę
zła K)
K
E
N
A
I
Q
O
F
J
L
P
E
A
P
I
N
F
J
K
L
Q
O
Algorytmy i struktury danych
Temat:
Zastosowania drzew binarnych
Drzewa wyra
Ŝ
e
ń
arytmetycznych
30
Algorytmy i struktury danych
Binarne drzewa wyraŜeń
Jednym z zastosowa
ń
drzew binarnych jest jednoznaczny
zapis wyra
Ŝ
e
ń
arytmetycznych lub logicznych (bez u
Ŝ
ywania
nawiasów);
Drzewa wyra
Ŝ
e
ń
konstruuje si
ę
, wykorzystuj
ą
c nast
ę
puj
ą
ce
zało
Ŝ
enia:
ka
Ŝ
dy li
ść
zawiera operand (argument) wyra
Ŝ
enia;
ka
Ŝ
dy w
ę
zeł wewn
ę
trzny zawiera operator np.: *, /, +, - itp.;
wyra
Ŝ
enie powstaje w wyniku realizacji procedury
przechodzenia drzewa jedn
ą
z trzech metod:
bezpo
ś
redniej (inorder),
z wyprzedzeniem (preorder),
z opó
ź
nieniem (postorder).
31
Algorytmy i struktury danych
Przykład drzewa wyraŜeń
+
–
5
2
*
3
4
Wynik przej
ś
cia drzewa metod
ą
:
bezpo
ś
redni
ą
(inorder):
2 – 3 * 4 + 5
z wyprzedzeniem (preorder):
+ – 2 * 3 4 5
z opó
ź
nieniem (postorder):
2 3 4 * – 5 +
Binarne drzewa wyraŜeń
= -5
= -5
= -5
32
Algorytmy i struktury danych
Mnemotechniczna metoda przechodzenia drzewa:
wyruszamy z korzenia, okrąŜając drzewo w kierunku
przeciwnym do ruchu wskazówek zegara;
staramy się być jak najbliŜej mijanych węzłów (niektóre węzły
odwiedzamy wielokrotnie);
chcą otrzymać listę węzłów odpowiadającą kolejności:
preorder, naleŜy wypisywać kaŜdy węzeł przy pierwszym jego
odwiedzeniu;
postorder, naleŜy wypisywać kaŜdy węzeł przy ostatnim jego
odwiedzeniu;
inorder, naleŜy wypisywać kaŜdy węzeł przy pierwszym jego
odwiedzeniu jeŜeli jest liściem, natomiast przy drugim
odwiedzeniu, jeŜeli jest węzłem wewnętrznym.
Binarne drzewa wyraŜeń
33
Algorytmy i struktury danych
Mnemotechniczna metoda przechodzenia drzewa:
Binarne drzewa wyraŜeń
+
–
5
2
*
3
4
Wynik przej
ś
cia drzewa:
+ – 2 – * 3 * 4 * – + 5 +
Kolejność preorder:
+
–
2 * 3 4 5
Kolejność postorder:
2 3 4 * – 5 +
Kolejność inorder:
2 – 3 * 4 + 5
UWAGA
NiezaleŜnie od metody kaŜdy liść odwiedzany jest dokładnie jeden raz
(i w tej samej kolejności)
34
Algorytmy i struktury danych
Binarne drzewa wyraŜeń
Z uwagi na sposób przechodzenia drzewa wyróŜniamy notację wyraŜeń:
przedrostkową (prefiksową), np.
+
–
2 * 3 4 5
wzrostkową (infiksową), np.
2 – 3 * 4 + 5
przyrostkową (postfiksową), znanej jako notacja polska odwrotna,
np.
2 3 4 * – 5 +
35
Algorytmy i struktury danych
Przykłady drzew wyraŜeń
Zapis wyra
Ŝ
enia metod
ą
:
wzrostkow
ą
(inorder):
Binarne drzewa wyraŜeń
*
–
+
2
3
4
5
przedrostkow
ą
(preorder):
przyrostkow
ą
(postorder):
2 – 3 * 4 + 5
2 3 – 4 5 + *
* – 2 3 + 4 5
= -9
= -9
= -9
36
Algorytmy i struktury danych
Przykłady drzew wyraŜeń
Zapis wyra
Ŝ
enia metod
ą
:
wzrostkow
ą
(inorder):
Binarne drzewa wyraŜeń
–
2
+
3
4
*
5
przedrostkow
ą
(preorder):
przyrostkow
ą
(postorder):
2 – 3 * 4 + 5
2 3 4 * 5 + –
– 2 + * 3 4 5
= -15
= -15
= -15
37
Algorytmy i struktury danych