POLITECHNIKA WARSZAWSKA
Instytut Automatyki i Robotyki
ZASADY PROGRAMOWANIA KOMPUTERÓW
ZAP  zima 2013/2014
Język programowania: C/C++
Środowisko programistyczne: Qt
Wykład 12 : Drzewa zrównoważone, kopce, B-drzewa.
2
Drzewa zrównoważone - wprowadzenie
" Struktura drzewa BST zależy od kolejności, w jakiej zostały utworzone węzły.
" Nowe węzły wstawiane są jako liście drzewa
1
5
2
3 8 3
4
2 4 6 9 5
6
7
1 7
8
Kolejność tworzonych
Kolejność tworzonych węzłów drzewa BST:
9
węzłów:
5, 3, 8, 2, 6, 4, 9, 1, 7
1, 2, 3, 4, 5, 6, 7, 8, 9
lub 5, 8, 9, 3, 6, 2, 4, 7, 1 lub . . .
Ilość poziomów (wysokość drzewa): 4 Ilość poziomów (wysokość drzewa): 9
Drzewa wyważone ( zrównoważone )
Zapewniają optymalny stosunek ilości poziomów do ilości węzłów
2
Przykłady: drzewa AVL, drzewa czerwono-czarne (RBT).
Operacje rotacji - przywracanie wyważenia węzła drzewa
3
a, b, d - dowolne poddrzewa
// rotacja w prawo względem Q
if (Q->Lewy == P) {
Q->Lewy = P->Prawy;
P-> Prawy = Q;
Q = P; // nowym korzeniem
// tego poddrzewa będzie teraz P
}
// rotacja w lewo względem P
if (P->Prawy == Q) {
P-> Prawy = Q-> Lewy;
Q-> Lewy = P;
P = Q; // nowym korzeniem
// tego poddrzewa będzie teraz Q
}
Operacje rotacji zachowują porządek
inorder
Aplet  Drzewo binarne - równoważenie drzewa
4
Wskaz
niki wyważenia w
węzłach (bezwzględna
różnica wysokości) uzyskuje
się zaznaczając opcję  wagi
Rys. 2. Drzewo zrównoważone - po
wykonaniu rotacji w prawo względem
węzła=4 (bo zaznaczamy prawym
przyciskiem myszki prawego potomka
węzła 4, czyli węzeł =7)
Rys. 1. Drzewo początkowe -
niezrównoważone
Bardzo często trzeba wykonać
więcej rotacji, by uzyskać drzewo
zrównoważone. Maksymalna liczba
koniecznych rotacji dla drzewa o n
węzłach jest rzędu lg(n).
5
Definicja drzewa AVL (Adelson-Velskij i Landis, 1962 r.)
Drzewo dokładnie wyważone
Dla każdego węzła ilość węzłów jego lewego i prawego poddrzewa może różnić się tylko
o jeden
Drzewo wyważone AVL
Dla każdego węzła wysokość jego lewego i prawego poddrzewa może się
różnić tylko o jeden
Wskaz
nik wyważenia węzła
w w w
Wsk = HP  HL
Wskaz
nik wyważenia węzła, czyli różnica
HL HL HP HP
wysokości dla lewego i prawego jego
HP HL
Wsk > 0 Wsk = 0 Wsk < 0
poddrzewa, jest pamiętany w węz
le.
Przykłady
5 +1
5 0 5 +2 5 +1
3 +1 8 -1
3 -1 8 -1 3 0 8 -1 3 +1 8 -2
4 0 6 +1 9 0
2 -1 4 0 6 +1 9 0 6 +1 9 0 4 0 6 +1
7 0
1 0 7 0 7 0 7 0
Drzewo AVL
Drzewo niewyważone Drzewo niewyważone
5
Drzewo AVL
Drzewa czerwono-czarne (RBT - Red Black Tree),
6
1972-78 r. (R. J. Guibas, R. Sedgewick)
Drzewo czerwono-czarne
Drzewo wyszukiwań binarnych, w którym każdy węzeł zawiera dodatkowe pole
Kolor (1 bit), który może być czerwony (Red) lub czarny (Black). Narzucenie
odpowiednich warunków na kolory w węzłach gwarantuje, że drzewo jest w
przybliżeniu zrównoważone, a przywrócenie jego własności wymaga co
najwyżej dwóch operacji rotacji (!).
Własności drzew RBT
Drzewo BST jest drzewem czerwono-czarnym
(RBT), jeśli ma następujące własności
czerwono-czarne:
* każdy węzeł jest albo czerwony, albo
czarny
* korzeń jest czarny
* każdy liść (NULL) jest czarny
* jeśli węzeł jest czerwony, to obaj jego
synowie są czarni (a zatem każdy czerwony
węzeł ma czarnego ojca)
* każda prosta ścieżka z ustalonego węzła
do dowolnego liścia ma tyle samo czarnych
węzłów (jest to tzw. czarna głębokość węzła).
7
Drzewa czerwono-czarne pochylone w lewo - 2008 r.
Autor: Robert Sedgewick, Princeton University
Drzewa LLRBT (Left Leaning Red
Black Trees)  algorytmy bardzo
uproszczone względem RBT (kosztem
większej liczby koniecznych rotacji),
dzięki dodatkowej własności:
Prostszy sposób rysowania drzew RBT - bez liści, bo * Prawy syn jest czerwony tylko i
wiadomo, że wszystkie liście są czarne i nie zawierają
wyłącznie wtedy, gdy czerwony jest
istotnych danych.
również lewy syn.
Najkrótsza ścieżka w drzewach RBT ma wszystkie
węzły czarne, najdłuższa- czarne i czerwone na
przemian. Każda gałąz
jest więc co najwyżej dwa
razy dłuższa niż dowolna inna (bo na każdej musi
być tyle samo czarnych węzłów).
" Wysokość drzewa RBT o n węzłach wewnętrznych wynosi co najwyżej 2lg (n+1)
" Operacje wstawiania węzła i usuwania węzła wykonują się w czasie
proporcjonalnym do lg n
" Przewaga drzew czerwono-czarnych nad drzewami AVL polega na tym, że RBT w
tych najgorszych przypadkach wymagają mniej operacji rotacji podczas wstawiania
lub usuwania węzła. Natomiast drzewa AVL lepiej się sprawdzają w operacjach
wyszukiwania (bo są lepiej wyważone).
8
Zastosowanie drzew binarnych - drzewa wyrażeń
Bryły CSG - reprezentowane przez
drzewa wyrażeń (bryły
podstawowe w liściach + operacje
logiczne w węzłach)
9
Kopiec czyli sterta
Jeśli i oznacza indeks węzła, to
" indeks ojca wynosi część całkowitą z połowy wartości i
" indeks lewego potomka wynosi 2i
" indeks prawego potomka wynosi 2i+1
" Służy do implementacji kolejki priorytetowej, która pozwala usunąć z kolejki
element o największym kluczu
" Każdy element w węz
le ma wartość nie większą niż jego ojciec 
największy element jest więc zawsze na pozycji korzenia, a elementy w kopcu
mogą się powtarzać
" Każdy poziom drzewa poza ostatnim jest całkowicie wypełniony
Wstawianie elementu do kopca i przywracanie
10
własności kopca (1)
wstaw  krok 1
wstaw  krok 2
" najpierw dodajemy wstawiany element jako nowy liść na najniższym poziomie
" następnie, w razie potrzeby, przesuwamy ten element na wyższe poziomy
(zamieniając z kolejnymi ojcami), aż do momentu, gdy całe drzewo będzie
posiadało własność kopca
Wstawianie elementu do kopca i przywracanie
11
własności kopca (2)
wstaw  krok 3
Sortowanie przez kopcowanie (heapsort)
" pobranie największego elementu i zamiana z ostatnim elementem
" zmniejszenie rozmiaru kopca i przywrócenie jego własności (zamiana ojca z
większym z synów  wykonywana rekurencyjnie od korzenia w dół)
" pobranie największego elementu itd.
12
Drzewa wielokierunkowe: B-drzewa (1970)
Powszechnie używane w systemach dużych baz danych, przechowywanych na
dysku; węzły - jednostki o jednoczesnym dostępie do pamięci dyskowej.
n =3 (n - stopień
drzewa)
" Korzeń zawiera od 1 do 2n-1 obiektów (kluczy)
pamiętanych w porządku
niemalejącym
" Każdy inny węzeł zawiera od n-1 do 2n-1 obiektów
" Każdy węzeł o k obiektach albo jest liściem (nie ma potomków) albo ma k+1
potomków (zatem węzły mogą mieć od n do 2n potomków)
" Wszystkie liście pojawiają się na tym samym poziomie
" Jeśli B-drzewo spłaszczymy do jednego poziomu poprzez  wciśnięcie potomków
pomiędzy klucze (obiekty) ich przodków, to klucze utworzą ciąg niemalejący od
lewej do prawej.
13
B - drzewa (c.d.)
Przykład: wstawianie wartości 33 do drzewa
n =3
korzeń: 1-5 obiektów
inne węzły : 2-5 obiektów
z
ródło: http://www.bluerwhite.org/btree/ - zobacz animację
B-drzewa wysokiego stopnia mogą być bardzo niskie i dlatego służą do
organizacji pamięci dyskowej: np. drzewo stopnia n=256 o wysokości
h= 3 zawiera co najmniej 1+(2+2*256+2*256*256)*255, czyli ok. 33.5 mln kluczy
(ogólnie: 2nh-1 kluczy) - co oznacza, że w najgorszym przypadku przy wyszukiwaniu
będą potrzebne tylko 3 odwołania do dysku (!).
14
Drzewa 2-3-4 a drzewa LLRBT
B-drzewo stopnia 2
jest 2-3-4 drzewem
Drzewa 2-3-4 w sposób jednoznaczny
można zapisać jako drzewa LLRBT:
15
Przykłady innych drzew - drzewa ósemkowe (octree)
http://www.emeraldinsight.com/journals.htm?articleid=874
931&show=html
Analogicznie w przestrzeni 2D -
drzewa czwórkowe (quadtree)
Przykłady map zajętości przestrzeni 3D utworzonych na
podstawie drzew ósemkowych 16
Mapy otoczenia robota
mobilnego zbudowane na
podstawie pomiarów
skanerem laserowym.
Opracował Maciej
Przybylski, R57, praca
magisterska, styczeń 2008
optymalny rozmiar
elementarnego
sześcianu
Giga-voxele  najnowsze osiągnięcia grafiki
komputerowej (Cyril Crassin, 2011-2012, NVIDIA) 17
http://maverick.inria.fr/Membres/Cyril.Crassin
1024^3 voxeli, 80 FPS na rekonstrukcja CT, 32 GB na dysku,
NVIDIA GTX 480 20 FPS na NVIDIA GTX 280