Оптимални дървета за търсене

Има ситуации, в които можете да получите информация за вероятността за достъп до отделни ключове. Обикновено в такива случаи дървото за търсене се изгражда веднъж, има неизменяема структура, не включва нови ключове и не изключва съществуващите ключове от него. Пример за съответно приложение е скенер на компилатор, една от задачите на който е да се определи дали следващият идентификатор принадлежи към набор от ключови думи на езика за програмиране. Въз основа на събирането на статистически данни с множество компилации от програми, е възможно да се получи доста точна информация за честотите на търсене за отделни клавиши.

Нека дървото за търсене съдържа n върха и обозначи с pi вероятността за достъп до i-тия връх, съдържащ ключа ki. Сумата на всички pi е естествено равна на 1. Нека сега се опитаме да организираме дървото за търсене по такъв начин, че да гарантираме, че общият брой стъпки за търсене, изчислен за достатъчно голям брой обаждания, е минимален. Ще приемем, че коренът на дървото има височина 1 (а не 0, както преди) и ще определим претеглената дължина на пътя на дървото като сума pi * hi (1

---