Binarne

drzewo

poszukiwa

ń

Przegląd zagadnień

Definicja binarnego drzewa poszukiwań
Dodawanie elementów do drzewa
Wyszukiwanie w drzewie binarnym
Przeglądanie drzewa (tree traversal)
Usuwanie węzła



Usuwanie przez złączanie



Usuwanie przez kopiowanie

Podsumowanie
Pytania sprawdzające
Laboratorium

Węzeł typu Node ze

skończoną liczbą

dowiązanych rozłącznych

struktur, będących również

drzewami o typie

podstawowym Node.

Definicja binarnego drzewa

poszukiwań

Root

Struktura pusta

null

100

P

L

60

P

L

200

P

L

160

P

L

40

P

L

70

P

L

10

P

L

50

P

L

500

P

L

90

P

L

80

P

L

null null null null

null

300

P

L

120

P

L

150

P

L

900

P

L

null null null null

null null

null null

null null

Liść

Węzeł wewnętrzny

null

null

null

null

null

null

null

null

null

null

null

null

null

null

null

null

Dodawanie elementów do drzewa

60

P

L

100

P

L

10

P

L

null null

40

P

L

50

P

L

null null

70

P

L

null

300

P

L

null null

900

P

L

null null

200

P

L

80

P

L

null null

150

P

L

null null

90

P

L

null

120

P

L

null

500

P

L

Root

10

0
,

6

0
,

70, 200, 40, 160, 120, 150, 500, 10, 50,

90, 80, 900, 300

160

P

L

null

Wyszukiwanie w drzewie

binarnym

Root

100

P

L

60

P

L

200

P

L

160

P

L

40

P

L

70

P

L

10

P

L

50

P

L

500

P

L

90

P

L

80

P

L

null null null null

null

300

P

L

120

P

L

150

P

L

900

P

L

null null null null

null null

null null

null null

null

12

0

95

Przeglądanie drzewa (tree

traversal)

Przechodzenie wszerz
Przechodzenie w głąb



przechodzenie z wyprzedzeniem (preorder)
- odwiedzamy korzeń przed poddrzewami



przechodzenie bezpośrednie (inorder)
- odwiedzamy najpierw lewe
poddrzewo, później korzeń i na końcu
prawe poddrzewo



przechodzenie z opóźnieniem (postorder) -
korzeń jest odwiedzany po obu
poddrzewach

Usuwanie węzła - węzeł ma

najwyżej jedno dziecko

Root

100

P

L

60

P

L

200

P

L

160

P

L

40

P

L

70

P

L

10

P

L

50

P

L

500

P

L

90

P

L

80

P

L

null null null null

null

300

P

L

120

P

L

150

P

L

900

P

L

null null null null

null null

null null

null null

null

Usuwanie przez złączanie

Root

100

P

L

60

P

L

Węzeł do

usunięcia - node

Skrajny prawy
węzeł lewego
poddrzewa

poddrzewo

prawe

poddrzewo

70

P

L

lewe

poddrzewo

40

P

L

50

P

L

null

prawy
węzeł

lewy węzeł

50

60

Usuwanie przez kopiowanie

Root

100

P

L

P

L

Węzeł do

usunięcia - node

Skrajny prawy
węzeł lewego
poddrzewa

poddrzewo

prawe

poddrzewo

70

P

L

lewe

poddrzewo

40

P

L

50

P

L

null

prawy
węzeł

lewy węzeł

48

P

L

Podsumowanie

Definicja binarnego drzewa poszukiwań
Dodawanie elementów do drzewa
Wyszukiwanie w drzewie binarnym
Przeglądanie drzewa (tree traversal)
Usuwanie węzła



Usuwanie przez złączanie



Usuwanie przez kopiowanie

Podsumowanie
Pytania sprawdzające
Laboratorium

Pytania sprawdzające

Co to jest drzewo?
Co to jest drzewo binarne?
Co to jest binarne drzewo poszukiwań?
Jakie znasz metody usuwania węzła z

drzewa?

Laboratorium

Ćwiczenie 1:



Implementacja drzewa
binarnego - baza danych.