5270659526

Drzewa decyzyjne

Każdy węzeł w drzewie decyzyjnym ma etykietę a₍-: a_y- dla pewnych i oraz j z przedziału 1 < i,j < n, gdzie n jest liczbą elementów w ciągu wejściowym. Z każdym liściem związana jest jedna permutacja n(1), n(2), ... , ti(N). Wykonanie algorytmu sortującego odpowiada przejściu ścieżki od korzenia drzewa decyzyjnego do jednego z jego liści, tj. znalezieniu poprawnej permutacji elementów ciągu.

W każdym węźle wewnętrznym zostaje wykonane porównanie typu a₍. < a-. W lewym poddrzewie znajdują się porównania wykonywane przez algorytm, jeśli okaże się, że a,- < a-, a prawe poddrzewo zawiera możliwe scenariusze dla przeciwnego przypadku, tj. a,- > a_;. Jeśli algorytm sortujący działa poprawnie, to każda z n! permutacji musi wystąpić jako jeden z liści drzewa decyzyjnego.

Wykład 6. Strona 10.

Długość najdłuższej ścieżki od korzenia drzewa decyzyjnego do dowolnego z jego liści odpowiada pesymistycznej liczbie porównań wykonywanych przez algorytm sortujący.

Wszystkie algorytmy sortowania za pomocą porównań można prezentować w postaci drzew decyzyjnych! Każde drzewo decyzyjne, odpowiadające algorytmowi poprawnie sortującemu n elementów, ma wysokość Q(n log n).

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