5755073844

Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011

Drzewa przeszukiwania binarnego

□    Jest to zaetykietowane drzewo binarne dla którego etykiety należą do zbioru w którym możliwe jest zdefiniowanie relacji mniejszości.

□    Dla każdego węzła x spełnione są następujące własność:

■    wszystkie węzły w lewym poddrzewie maja etykiety mniejsze od etykiety węzła x

■    wszystkie w prawym poddrzewie maja etykiety większe od etykiety węzła x.

□    Wyszukiwanie elementu:

■    Podstawa:

□    Jeśli drzewo T jest puste, to na pewno nie zawiera elementu x.

□    Jeśli T nie jest puste i szukana wartość x znajduje się w korzeniu, drzewo zawiera x.

■    Indukcja:

□    Jeśli T nie jest puste, ale nie zawiera szukanego elementu x w korzeniu, niech y będzie elementem w korzeniu drzewa T.

□    Jeśli x<y, szukamy wartości x tylko w lewym poddrzewie korzenia y.

□    Jeśli x>y, szukamy wartości x tylko w prawym poddrzewie korzenia y.

□    Własność drzewa przeszukiwania binarnego gwarantuje, że szukanej wartości x na pewno nie ma w poddrzewie, którego nie przeszukujemy.

Wyszukiwarka

Podobne podstrony:
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Drzewa przeszukiwania
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Drzewa przeszukiwania
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Drzewa binarne □
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Drzewa binarne Zdegene
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Drzewa zaetykietowane
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Modele danych języka C
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Modele danych języka C
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Modele danych języka C
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Modele danych języka C
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Modele danych języka C
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Tablica wskaźników jak
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Reprezentacje drzewa □
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Reprezentacje drzewa □
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Reprezentacje drzewa
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Reprezentacje drzewa □
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Rekurencja w drzewach
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Model danych oparty na
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Podstawowa terminologi
Teoretyczne Podstawy Informatyki - Rok I - kierunek IS w IFAilS UJ - 2010/2011Konstrukcja drzew wyra

więcej podobnych podstron