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)