Оптимальное дерево поиска: частые ключи ближе к корню

Если ты умеешь записать переход для оптимального дерева поиска, понимаешь, откуда в нём сумма частот, и знаешь, почему жадность ошибается, листай до «Теперь сам».

Как думаешь, кого ставить в корень

Словарь из двенадцати слов. Три слова спрашивают по сто раз в день, остальные - единицы. Сбалансированное дерево поставит в корень середину алфавита - скорее всего, редкое слово - и каждый частый запрос пройдёт три-четыре сравнения.

Прежде чем читать дальше, попробуй угадать: если поставить в корень самое частое слово, а в каждом поддереве снова самое частое, будет ли дерево лучшим? Что может помешать?

На что это похоже

Раскладка инструментов в мастерской. Молоток и отвёртку вешают у верстака, а редкий ключ - на дальнюю полку. Но полки упорядочены по размеру, и самое нужное нельзя повесить в любое место: порядок держится. Отсюда тонкость: поставив в центр самый ходовой инструмент, можно оттолкнуть сразу несколько почти таких же ходовых на дальние полки, тогда как чуть менее популярный в центре оставил бы их всех рядом.

Механизм: корень на отрезке и сумма частот

ключи по возрастанию k_1 < … < k_n, частоты f_1 … f_n
цена дерева = Σ f_i · глубина(k_i)    (глубина корня - 1)

e[i][j] - лучшая цена дерева на ключах i..j
w(i, j) = f_i + … + f_j

переход: корень r, слева ключи i..r−1, справа r+1..j
    e[i][j] = min по r ( e[i][r−1] + e[r+1][j] ) + w(i, j)
    пустой отрезок стоит 0

откуда w: поддеревья, подвешенные под r, опускаются на уровень -
    каждый их ключ платит ещё одно сравнение; корень платит своё одно.
    Вместе - ровно по одной частоте на каждый ключ отрезка: w(i, j)

порядок: по возрастанию длины отрезка; Θ(n³)

Ускорение Кнута: если root[i][j] - лучший корень, то root[i][j−1] ≤ root[i][j] ≤ root[i+1][j]. Перебирать r можно только между этими границами, и суммарная работа падает до Θ(n²). Почему так - тема урока об оптимизациях динамики в следующей главе.

Правило

Оптимальное дерево поиска строится динамикой по отрезкам: e[i][j] = min по корню r (e[i][r−1] + e[r+1][j]) + w(i, j), где w(i, j) - сумма частот отрезка: поддеревья опускаются на уровень, и каждый ключ платит одно сравнение. Θ(n³), с монотонностью корня Кнута - Θ(n²). Жадность «самый частый в корень» не оптимальна: она игнорирует, сколько частых ключей при этом уйдёт вглубь.

Разбор: три ключа

ключи 1, 2, 3, частоты 5, 1, 4

e[1][1] = 5   e[2][2] = 1   e[3][3] = 4
e[1][2]: корень 1: 0 + e[2][2] + w = 1 + 6 = 7
         корень 2: e[1][1] + 0 + w = 5 + 6 = 11      → 7
e[2][3]: корень 2: 0 + 4 + 5 = 9;  корень 3: 1 + 0 + 5 = 6   → 6
e[1][3], w = 10:
         корень 1: 0 + e[2][3] + 10 = 16
         корень 2: e[1][1] + e[3][3] + 10 = 19
         корень 3: e[1][2] + 0 + 10 = 17                 → 16

дерево: 1 в корне, справа 3, под ним слева 2
проверка: 5·1 + 4·2 + 1·3 = 16
сбалансированное (2 в корне): 1·1 + 5·2 + 4·2 = 19

Здесь жадность «самый частый в корень» угадала бы - 1 и в корне, и самый частый. Ошибается она там, где самый частый ключ стоит на краю, а рядом с серединой - группа почти таких же частых.

Разбор: двенадцать слов и все 208 012 деревьев

Программа строит оптимальное дерево для двенадцати ключей со случайными частотами, сравнивает его со сбалансированным и с жадным и проверяет перебором ВСЕХ деревьев поиска на этих ключах - их число Каталана, 208 012.

import random
from functools import lru_cache

rng = random.Random(25)
klyuchi = sorted(rng.sample(range(1000), 12))
chastota = [rng.choice((1, 1, 2, 3, 5, 40, 100)) for _ in klyuchi]
n = len(klyuchi)
pref = [0]
for c in chastota:
    pref.append(pref[-1] + c)
ves = lambda i, j: pref[j + 1] - pref[i]        # сумма частот i..j


def optimalnoe():                     # e[i][j]: лучшая цена ключей i..j
    e = [[0] * (n + 1) for _ in range(n + 1)]
    koren = [[0] * n for _ in range(n)]
    for dlina in range(1, n + 1):
        for i in range(n - dlina + 1):
            j = i + dlina - 1
            luchshe = None
            for r in range(i, j + 1): # кого поставить в корень
                c = (e[i][r - 1] if r > i else 0) + \
                    (e[r + 1][j] if r < j else 0)
                if luchshe is None or c < luchshe:
                    luchshe, koren[i][j] = c, r
            e[i][j] = luchshe + ves(i, j)   # все ключи на уровень ниже
    return e[0][n - 1], koren


def cena(i, j, vybor, glub=1):        # цена дерева с правилом выбора
    if i > j:
        return 0
    r = vybor(i, j)
    return glub * chastota[r] + cena(i, r - 1, vybor, glub + 1) + \
        cena(r + 1, j, vybor, glub + 1)


@lru_cache(None)
def vse_derevya(i, j, glub):          # цены ВСЕХ деревьев на i..j
    if i > j:
        return [0]
    return [glub * chastota[r] + a + b
            for r in range(i, j + 1)
            for a in vse_derevya(i, r - 1, glub + 1)
            for b in vse_derevya(r + 1, j, glub + 1)]


opt, koren = optimalnoe()
print("частоты:", chastota)
print("сбалансированное:", cena(0, n - 1, lambda i, j: (i + j) // 2))
print("частый в корень: ",
      cena(0, n - 1, lambda i, j: max(range(i, j + 1),
                                      key=lambda r: chastota[r])))
vse = vse_derevya(0, n - 1, 1)
print("оптимальное:     ", opt)
print("перебор", len(vse), "деревьев: лучшее", min(vse))
print("сравнений на запрос: оптимум", round(opt / ves(0, n - 1), 2))

частоты: [100, 100, 2, 1, 2, 5, 3, 1, 5, 100, 1, 5]
сбалансированное: 1166
частый в корень:  724
оптимальное:      599
перебор 208012 деревьев: лучшее 599
сравнений на запрос: оптимум 1.84

Перебор подтвердил: 599 - лучшее из 208 012 деревьев. Сбалансированное вдвое хуже (1166), жадное - на 20% хуже оптимума (724): частоты здесь резко неравные (три ключа по 100), и жадность, поставив одного «стотысячника» в корень, отправила двух других вглубь. Оптимальному дереву хватает в среднем 1.84 сравнения на запрос.

Что ломается без этого

Первая ошибка - забыть слагаемое w(i, j) или считать вместо него частоту одного корня: тогда глубина поддеревьев не учитывается, и «оптимум» получается бессмысленным. Вторая - строить оптимальное дерево по прошлым частотам и не перестраивать при их изменении: дерево, идеальное для вчерашних запросов, может быть хуже сбалансированного сегодня. Третья - путать оптимальное дерево с кодом Хаффмана: у Хаффмана порядок листьев свободен, здесь ключи обязаны стоять по порядку - поэтому жадное слияние двух редких не работает, а нужна динамика.

Зачем это в работе

Статичные словари с известной статистикой: таблицы ключевых слов в компиляторах, словари в программах проверки орфографии, справочники кодов в учётных системах, дерево решений «по частоте случаев» в службе поддержки. Где частоты меняются, ту же идею реализуют адаптивно: splay-дерево из этого же раздела само подтягивает частые ключи к корню и, как доказано, в долгую не хуже оптимального статического дерева больше чем в константу раз.

Теперь сам

Ключи 1, 2, 3, частоты 2, 10, 3. Посчитай таблицу и найди оптимальный корень.