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.

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

Wyszukiwarka

Podobne podstrony:
Drzewa arytmetyczne Drzewa arytmetyczne - to drzewa (zwykle binarne) wykorzystane do zapisu operacji
stolarstwo0 żna rozmaicie drzewo zarzynać, stosownie do tego, czy chcemy, aby to ukośne spojenie z
Wstawiamy do pustego drzewa BST kolejno: 3 2 5 4 0 6 1. Wypisując wartości węzłów przy przejściu teg
ASD egzamin 09 rozw Wstawiamy do pustego drzewa BST kolejno: 3 2 5 4 0 6 1. Wypisując wartości węzł
ASD egzamin 09 rozw Wstawiamy do pustego drzewa BST kolejno: 3 2 5 4 0 6 1. Wypisując wartości węzł
•    Złożoność wyszukiwania w drzewach BST i AVL. •    Konstrukcja

więcej podobnych podstron