5270659527

Drzewa BST

Binarne drzewo poszukiwań (BST, Binary Search Tree) - to drzewo binarne stosowane do szybkiego wyszukiwania. Drzewa BST często służą do modelowania bardziej abstrakcyjnych struktur danych, np. zbiorów czy słowników.

W każdym z węzłów drzewa BST przechowywany jest unikatowy klucz, którego wartość klucza jest zawsze nie niniejsza niż wartości wszystkich kluczy z lewego poddrzewa, a nie większa niż wartości wszystkich kluczy z prawego poddrzewa. Relacje niemniejszości i niewiększości można zamienić odpowiednio na relacje większości i mniejszości, ale ograniczamy się wówczas do przypadku unikalności kluczy (wykluczamy klucze, które mogą się powtarzać). Przechodząc drzewo metodą inorder, uzyskuje się ciąg wartości posortowanych niemalejąco (lub rosnąco w przypadku unikatowych kluczy).

Pesymistyczny koszt każdej z operacji na drzewie BST (o liczbie węzłów ń), tj. wyszukiwania, dodania lub usunięcia klucza, zależy od wysokości drzewa i wynosi:

■    log₂« - dla drzewa zrównoważonego (najlepszy przypadek)

■    n - dla drzewa zdegenerowanego do listy, tj. takiego, w którym każdy z węzłów oprócz liścia ma tylko jednego potomka.

Wykład 6. Strona 11.

PODSTAWY INFORMATYKI, Adrian Horzyk, http://home.agh.edu.pl/--horzyk