1

Wykład 6

Drzewa poszukiwań

binarnych (BST)

2

O czym będziemy mówić

 Definicja
 Operacje na drzewach BST:

– Search
– Minimum, Maximum
– Predecessor, Successor
– Insert, Delete

 Struktura losowo budowanych drzew BST

3

Wprowadzenie

 Poszukujemy dynamicznego ADT, który efektywnie będzie

obsługiwał następujące operacje:

– Wyszukiwanie elementu (Search)
– Znajdowanie Minimum/Maximum
– Znajdowanie poprzednika/następnika (Predecessor/Successor)
– Wstawianie/usuwanie elementu (Insert/Delete)

 Wykorzystamy drzewo binarne! Wszystkie operacje powinny

zajmować czas Θ(lg n)

 Drzewo powinno być zawsze zbalansowane – inaczej czas

będzie proporcjonalny do wysokości drzewa (gorszy od O(lg
n))!

4

Drzewo poszukiwań binarnych (binary search
tree)

 Struktura drzewa z korzeniem
 Każdy węzeł x posiada pola left(x), right(x), parent(x), oraz

key(x).

 Własność drzewa BST:

Niech x będzie dowolnym węzłem drzewa, natomiast niech y

będzie należał do poddrzewa o korzeniu w x wtedy:.

– Jeżeli należy do lewego poddrzewa to: key(y) ≤ key(x)
– Jeżeli należy do prawego poddrzewa to : key(y) > key(x)

5

Przykład BST

5

3

5

5

7

8

2

3

7

2

8

5

Metody przechodzenia przez drzewo :

In-order, pre-order, post-order

6

Tree-Search(x,k)
if x = null or k = key[x]
then return x
if k < key[x]
then return Tree-Search(left[x],k)
else return Tree-Search(right[x],k)

Tree-Search(x,k)
while x ≠ null and k ≠ key[x]
do if k < key[x]
then x

 left[x]

else x

 right[x]

return x

Poszukiwanie w drzewie BST

rekurencyjnie

iteracyjnie

złożoność: O(h)

7

Przykład

Poszukiwany klucz: 13

8

Przechodzenie przez wszystkie węzły drzewa

Inorder-Tree-Walk(x)
if x ≠ null
then Inorder-Tree-Walk(left[x])
print key[x]
Inorder-Tree-Walk(right[x])

złożoność: Θ(n)

czas wykonania:

T(0) = Θ(1)
T(n)=T(k) + T(n – k –1) + Θ(1)

9

Tree-Minimum(x)
while left[x] ≠ null
do x

 left[x]

return x

Tree-Maximum(x)
while right[x] ≠ null
do x

 right[x]

return x

Odnajdowanie minimum i maksimum

złożoność: O(h)

10

Przykład – minimum

11

Odnajdowanie następnika



Następnikiem x nazywamy najmniejszy element y wśród
elementów większych od x



Następnik może zostać odnaleziony bez porównywania
kluczy. Jest to :

1. null jeśli x jest największym z węzłów.
2. minimum w prawym poddrzewie t jeśli ono istnieje.
3. najmniejszy z przodków x, dla których lewy potomek

jest przodkiem x.

12

Odnajdowanie następnika

x

minimum w prawym poddrzewie t

y

z

x

najmniejszy z przodków x,

dla których lewy potomek

jest przodkiem x

13

Odnajdowanie następnika

Tree-Successor(x)
if right[x] ≠ null // przypadek 2

then return Tree-Minimum(right[x])
y  parent[x]

while y ≠ null and x = right[y] // przypadek 3
do x  y

y  parent[y]

return y

14

Przykład

Poszukajmy następników dla 15 (przyp. 2), 13 (przyp. 3)

15

Wstawianie elementów

 Wstawianie jest bardzo zbliżone do odnajdowania

elementu:

– Odnajdujemy właściwe miejsce w drzewie, w które chcemy

wstawić nowy węzeł z.

 Dodawany węzeł z zawsze staje się liściem.
 Zakładamy, że początkowo left(z) oraz right(z) mają

wartość null.

16

Wstawanie – przykład

1
2

5

9

1
8

1
9

1
5

1
7

2

1
3

Wstawiamy 13 do drzewa

z

17

Wstawianie – pseudokod

Tree-Insert(T,z)
y  null
x  root[T]
while x ≠ null
do y  x
if key[z] < key[x]
then x  left[x]
else x  right[x]
parent[z]  y

// dla pustego drzewa
if y = null then root[T]  z
else if key[z] < key[y]
then left[y]  z
else right[y]  z

18

Usuwanie z drzewa BST

Usuwanie elementu jest bardziej skomplikowane niż

wstawianie. Można rozważać trzy przypadki usuwania węzła
z:

1. z nie ma potomków

2. z ma jednego potomka

3. z ma 2 potomków

przypadek 1: usuwamy z i zmieniamy u rodzica wskazanie na

null.

przypadek 2: usuwamy z a jego dziecko staje się dzieckiem

rodzica.

przypadek 3:najbardziej złożony; nie można po prostu usunąć

węzła i przenieść dzieci do rodzica – drzewo przestałoby być
binarne!

19

delete

Usuwanie z drzewa BST - przypadek 1

usuwamy

20

Usuwanie z drzewa BST przypadek 2

Usuwany

węzeł

21

Usuwanie z drzewa BST

przypadek 3

Rozwiązanie polega na zastąpieniu węzła jego następnikiem.

założenie: jeśli węzeł ma dwóch potomków, jego następnik

ma co najwyżej jednego potomka.

dowód: jeśli węzeł ma 2 potomków to jego następnikiem jest

minimum z prawego poddrzewa. Minimum nie może
posiadać lewego potomka (inaczej nie byłoby to minimum)

22

Usuwanie z drzewa BST – przypadek 3

z

α

β

δ

Usuwamy z

y

w

y

α

β

δ

w

23

Usuwanie z drzewa BST – przypadek 3

usuwamy

następnik

24

Usuwanie z drzewa BST – pseudokod

Tree-Delete(T,z)
if left[z] = null or right[z] = null /* p. 1 lub 2
then y  z
else y  Tree-Successor(z)
if left[y] ≠ null
then x  left[y]
else x  right[y]
if x ≠ null
then parent[x] parent[y]
if parent[y] = null
then root[T]  x
else if y = left[parent[y]]
then left[parent[y]]  x
else right[parent[y]]  x

if y ≠ z

then key[z]  key[y]

return y

25

Analiza złożoności

 Usuwanie: dwa pierwsze przypadki wymagają O(1) operacji:

tylko zamiana wskaźników.

 Przypadek 3 wymaga wywołania Tree-Successor, i dlatego

wymaga czasu O(h).

 Stad wszystkie dynamiczne operacje na drzewie BST

zajmują czas O(h), gdzie h jest wysokością drzewa.

 W najgorszym przypadku wysokość ta wynosi O(n)