Optymalne drzewo BST

Witam,
Mam problem z zadaniem. Otóż na zajęciach nauczyłem się jak budować drzewo BST, usuwać elementy z niego, przechodzic po nim na 3 sposoby (inorder, preorder, postorder) a potem na kolokwium dostałem takie zadanie i kompletnie nie wiem jak je ugryźć :

Wyszukujemy z 6 elementów o kluczac : a, b, c, d, e, f. Prawdopodobieństwo wyszukania elementu o danym kluczu są podane w nawiasach: a(0,3), b(0,1), c(0,2), d(0,2), e(0,1), f(0,1). Zbuduj optymalne drzewo BST, które pozwoli zminimalizować koszt wyszukania jednego elementu.

Prosiłbym o rady, linki itd.
Z góry dzięki

Nie wiem jakie jest oficjalne rozwiązanie (nie szukałem), ale posortował bym wartości po prawdopodobieństwie malejąco i użył takiego strumienia do zapełnienia drzewa.

vpiotr napisał(a):

Nie wiem jakie jest oficjalne rozwiązanie (nie szukałem), ale posortował bym wartości po prawdopodobieństwie malejąco i użył takiego strumienia do zapełnienia drzewa.

To na pewno nie jest rozwiązanie optymalne ponieważ jeśli wszystkie elementy są równie prawdopodobne i akurat podane w posortowanej kolejności to drzewo zdegeneruje ci się do listy, a optymalniejsze będzie zbudowanie drzewa o dowolnym innym korzeniu z wyjątkiem ostatniego klucza.

Nie wiem czy to nie było pytanie na splay tree w sumie, dawno na uczelni nie byłem...

https://pl.wikipedia.org/wiki/Kodowanie_Huffmana

Zimny Jeleń napisał(a):

https://pl.wikipedia.org/wiki/Kodowanie_Huffmana

To by miało zastosowanie jeśli mógłbyś naruszyć warunki narzucone na klucze. Tutaj nadal chcesz zachować własności BST.

A co to jest optymalne drzewo? Ja bym to rozumiał przez zminimalizowanie ∑ d(i) * w(i), gdzie w(i) to prawdopodobieństwo klucza, a d(i) to ilość porównań potrzebna by znaleźć klucz.

Wtedy metodą prób i błędów wykonując rotacje na naiwnie skonstruowanym drzewie optymalne rozwiązanie to chyba:
((a, (b)), c, (d, (e, (f))))

A średni czas wyszukania klucza to 2.2.

Też mi się wydaje, że to jest zadanie na kombinowanie ze zrozumieniem. Wybór elementu c jako korzenia narzuca się (ma dużą wagę i dzieli drzewo na dość równe połowy), reszta wymaga niewielkich obliczeń. Staramy się tak umieszczać elementy, żeby te bardziej prawdopodobne były bliżej korzenia.

Na początek warto sobie zrobić zadanie dla samych elementów d, e, f z prawdopodobieństwami 50%, 25%, 25%. Tu najlepiej wybrać na środku e. Nie do końca rozumiem zapis @nalik -a, ale chyba zrobił tak samo, bo też wychodzi 2.2.

Drzewo wygląda tak:

  b   d   f
 /     \ /
a       e
  \   /
    c

I daje 0,2*1 + 0,4*2 + 0,4*3 = 2,2.

Inaczej, ale z takim samym wynikiem.

            f
           /
  b       e
 /       /
a       d
 \     /
    c

1*0.2 + 2*0.5 + 3*0.2 + 4*0.1 = 2.2

Odkopię trochę temat.

Obliczenie kosztu optymalnego drzewa wyszukiwania binarnego da się zautomatyzować, nie musi być to proces intuicyjnych zmian.
A algorytm, który to robi jest przykładem programowania dynamicznego.

Referencje:
https://en.wikipedia.org/wiki/Optimal_binary_search_tree
http://www.geeksforgeeks.org/dynamic-programming-set-24-optimal-binary-search-tree/