Optimální vyhledávací stromy

O většině binárních vyhledávacích stromů se ví, že v nich jde hledat v logaritmickém čase a že v porovnávacím modelu to obecně ani rychleji nejde, protože bychom pak mohli třídit rychleji než v O(n log n). Co kdybychom ale věděli, že nějaké prvky budeme vyhledávat často a nějaké skoro vůbec?

Je dána posloupnost různých prvků a₁ < … < a_n. Máme nějaký čas, abychom z nich postavili binární vyhledávací strom, a poté nám bude chodit plno dotazů tvaru "vyhledej prvek x ve stromě" (strom se tedy nebude v průběhu měnit). Navíc dopředu známe počty dotazů w₁, …, w_n na jednotlivé prvky. Chtěli bychom vybudovat takový vyhledávací strom, se kterým na dotazy dohromady odpovíme v co nejmenším čase. Na jeden dotaz na prvek x odpovíme v čase h(x), kde h(x) je hloubka vrcholu s prvkem x a kořen je v hloubce 1.

Jinými slovy, chceme z prvků a₁, …, a_n postavit binární vyhledávací strom tak, aby součet Σ w_i·h(a_i) byl co nejmenší. Strom musí pořád být binární a vyhledávací, tj. levý (resp. pravý) podstrom musí mít menší (větší) hodnotu než otec.

Příklad: Pro prvky 1, 2, 3 a počty dotazů 10, 2, 5 je optimální strom s 1 v kořeni a hranami 1 → 3 a 3 → 2. Jeho celková cena je 1·10 + 3·2 + 2·5 = 26. Kdyby byla kořenem dvojka, byla by celková cena 2·10 + 1·2 + 2·5 = 32.