Бинарные деревья поиска

В разделе Поиск сравнениями мы убедились, что деревья облегчают понимание бинарного поиска и его модификаций. Деревья там вводились не явно, а как иллюстрация дерева решений при выполнении алгоритмов. Явная структура дерева помогает обрести дополнительные возможности в виде быстрой вставки и удаления элементов.

Бинарное дерево поиска

Бинарное дерево поиска (BST, binary search tree) — бинарное дерево, в котором для каждого узла все узлы левого поддерева меньше его, и все узлы правого поддерева больше его. BST позволяет добавлять, удалять и искать элементы за время $O(\text{высота дерева})$ .

Бинарное дерево поиска построить на любом отношении тотального порядка. Это отношение порядка может быть задано не на самих данных, а на их ключах.

Обходы бинарного дерева

Обход по порядку (inorder)

Необходимо вывести все узлы BST в отсортированном порядке. Для этого, по свойству BST, необходимо обойти в отсортированном порядке левое от корня поддерево, затем пройти по корню, затем обойти в отсортированном порядке правое от корня поддерево. Временная сложность $\Theta(n)$ при $O(1)$ на итерацию.

iterator inorder(node root):
    if root == none:
        stop

    yield from inorder(root.left)
    yield root
    yield from inorder(root.right)

Прямой обход (preorder)

Необходимо вывести все узлы BST в порядке: вершина, все левое поддерево, все правое поддерево. Временная сложность $\Theta(n)$ при $O(1)$ на итерацию.

iterator preorder(node root):
    if root == none:
        stop

    yield root
    yield from preorder(root.left)
    yield from preorder(root.right)

Обратный обход (postorder)

Необходимо вывести все узлы BST в порядке: все левое поддерево, все правое поддерево, вершина. Временная сложность $\Theta(n)$ при $O(1)$ на итерацию.

Такой обход полезен, например при удалении всех вершин, ведь сначала обходятся вершины без детей, а дети всех последующих вершин гарантированно были выведены ранее. Поэтому можно освобождать память без риска словить nullptr.

iterator postorder(node root):
    if root == none:
        stop

    yield from postorder(root.left)
    yield from postorder(root.right)
    yield root

Оптимальные деревья

Построение оптимальных деревьев

Как мы уже убедились, эффективность алгоритмов сильно зависит от структуры дерева. А поскольку бинарных деревьев поиска, построенных на заданном массиве длины $n$ много, аж целых $\binom{2n}{n} \big/ (n+1)$ штук, встаёт вопрос о выборе оптимального бинарного дерева поиска для ключей с заданными частотами.

Давайте для начала поймём, как считать оптимальность. Пусть $n = 3$ , то есть массив состоит из $3$ ключей $K_1, K_2, K_3$ , и $K_1 < K_2 < K_3$ . Пусть также вероятности ключей $p_1, p_2, p_3$ соответственно. Всего возможно $5$ деревьев

наверное картинка

Интересует нас как успешный, так и неудачный поиск. В некоторых специфических задачах неудачный поиск даже являются определяющим, причём настолько, что при анализе эффективности успешным поиском пренебрегают.

Итак, мы ищем в бинарном дереве поиска с $n$ ключами $K_1, K_2, \dotsc, K_n$ ключ $K$

Определим $2n+1$ вероятностей $p_1, p_2, p_3, \dotsc, p_{n-1}, p_n$ и $q_0, q_1, q_2, \dotsc, q_{n-1}, q_n$ :

\align{ p_j &= \prob ( K_j = K \bigr)\\[0.4em]q_j &= \prob ( K_j < K < K_{j+1} ) \quad \text{при этом}~ K_0 = -\oo ~\text{и}~ K_{n+1} = +\oo }

Получается, что

p_1 + p_2 + \dotsb + p_n + q_0 + q_1 + \dotsb + q_n = 1

Обозначим за $C$ ожидаемое количество сравнений при поиске, а точнее сумму количеств сравнений при успешном и неудачном поиске. Получаем формулу

C = \sum\limits_{j=1}^n p_j \cdot \bigl( \depth \boxed{j} + 1 \bigr) + \sum\limits_{k=0}^n q_k \cdot \depth \weakboxed{k}

здесь $\boxed{j}$ — узел с номером $j$ при in-order обходе дерева, и $\weakboxed{k}$ — фиктивный лист с номером $k+1$ .

Ожидаемое количество сравнений при поиске $C$ будем называть ценой дерева. Оптимальное дерево будет иметь наименьшую цену. При этом можно убрать требование на то, что сумма вероятностей должна быть $1$ , и рассматривать произвольный набор чисел $(p_1, p_2, \dotsc, p_n,~ q_0, q_1, \dotsc, q_n)$ , который далее буду именовать весами дерева.

Как же находить оптимальные деревья? В лоб минимизировать $C$ не получится — задача вычислительно очень сложная.

Важный факт, делающий возможным достаточно эффективные алгоритмы: все поддеревья оптимального дерева тоже оптимальны. Запахло динамикой.

Пусть $c(i, j)$ — цена оптимального поддерева, содержащего ключи с $i+1$ по $j$ с весами $(p_{i+1}, p_{i+2}, \dotsc, p_j,~ q_i, q_{i+1}, \dotsc, q_j)$ . Пусть также $w(i, j) = p_{i+1} + p_{i+2} + \dotsb + p_j + q_i + q_{i+1} + \dotsb + q_j$ — сумма этих весов. Оба показателя определены для $0 \le i \le j \le n$ .

Минимально возможная цена дерева с корнем $\boxed{k}$ равна $w(i, j) + c(i, k-1) + c(k, j)$ . Значит

\align{ c(i, i) &= 0 \\ c(i, j) &= w(i, j) + \min\limits_{i < k \;\! \le \;\! j} \bigl( c(i, k-1) + c(k, j) \bigr) \quad \text{при}~ i < j }

Обозначим за $R(i, j)$ при $i < j$ множество всех $k$ , при которых достигается минимум в формуле динамики. Это множество определяет корни оптимальных поддеревьев.

Теперь можем вычислять значения $c(i, j)$ с помощью восходящего динамического программирования, рассматривая интервалы $j - i$ в порядке от $1$ до $n$ .

Нам нужно посчитать значения $c(i, j)$ для всех $0 \le i \le j \le n$ . Всего нам потребуется ячеей памяти

\sum\limits_{0 \;\! \le \;\! i \le j \le n} 1 = \sum\limits_{i=0}^n \sum\limits_{j=i}^n 1 = \frac{(n+1)(n+2)}{2}

Каждый подсчёт $\min\limits_{i < k \;\! \le \;\! j} (\cdots)$ требует $j - i$ выполнений блока минимизации, значит всего для вычисления всей динамики понадобится операций

\sum\limits_{i=0}^{n-1} \sum\limits_{j=i+1}^n (j-i) = \frac{n (n+1) (n+2)}{6}

Итого на подсчёт динамики нам нужно $(n+1)(n+2)/2 = O \bigl( n^2 \bigr)$ ячеек памяти и время $n (n+1) (n+2) / 6 = O \bigl( n^3 \bigr)$ .

Мы можем использовать оптимизацию Кнута и добиться временной сложности $O \bigl( n^2 \bigr)$ .

Введём для произвольных множеств действительных чисел $A$ и $B$ отношение $\le$ :

A \le B \defequiv (a \in A \land b \in B \land a < b) \implies (a \in B \land b \in A)

На русский язык это отношение можно перевести так: «если какой-то элемент $b$ из множества $B$ меньше какого-то элемента $a$ из множества $A$ , то эти два элемента должны принадлежать обоим множествам одновременно». Другими словами, минимальный элемент объединения $A \union B$ лежит в $A$ , если $A \le B$ .

По индукции по $j-i$ доказывается следующее «неравенство» для $R(i, j)$

R(i, j-1) \le R(i, j) \le R(i+1, j) \quad \text{для}~ j - i \ge 2

Можно не хранить всё $R(i, j)$ , а брать только одного представителя $r(i, j) \in R(i, j)$ . Наше «неравенство» для множеств $R$ превращается в неравенство для представителей $r$ :

r(i, j-1) \le r(i, j) \le r(i+1, j) \quad \text{для}~ j - i \ge 2

Получается, что в рекуррентной формуле при вычислении минимального $k$ можно брать всего $r(i+1, j) - r(i, j-1) + 1$ значений от $r(i, j-1)$ до $r(i+1, j)$ вместо $j-i$ значений от $i+1$ до $j$ .

Для интервала фиксированной длины $j-i = d$ общее количество проверяемых значений $k$ при вычислении всех $c(i, j)$ равно

T(d) = \sum\limits_{i=0}^{n-d} \bigl( r(i+1, i+d) - r(i, i+d-1) + 1 \bigr) = r(n-d+1, n) - r(0, d-1) + (n-d+1)

Тогда общее количество проверяемых значений $k$ равно

T = \sum\limits_{d=1}^n T(d) = \sum\limits_{d=1}^n r(n-d+1, n) - \sum\limits_{d=1}^n r(0, d-1) + \frac{n \, (n+1)}{2}

Точное значение зависит от $r(i, j)$ , поэтому в общем виде его вычислить нельзя. Грубую оценку можно получить, оценив величину $T(d) \le 2n$ , поэтому $T \le 2n^2$ .

Давайте теперь составим алгоритм.

Нам даны $2n+1$ весов $(p_1, p_2, \dotsc, p_n,~ q_0, q_1, \dotsc, q_n)$ . Алгоритм будет строить оптимальное бинарное дерево поиска, при этом дерево будет представлено как каскад вложенных поддеревьев.

function knuth_bst(array[real] p, array[real] q)
               -> (matrix[real] c, matrix[int] r, matrix[real] w):

    # p: array of n probabilities for successful search [p1, p2, ..., pn]
    # q: array of n+1 probabilities for unsuccessful search [q0, q1, ..., qn]

    # Returns
    # c: cost matrix
    # r: root matrix
    # w: weight matrix

    matrix[real] c[n+1, n+1]
    matrix[int] r[n+1, n+1]
    matrix[real] w[n+1, n+1]

    for int i = 0; i <= n; i++:
        c[i][i] = 0
        w[i][i] = q[i]

        for int j = i+1; j <= n; j++:
            w[i][j] = w[i][j-1] + p[j-1] + q[j]

    for int j = 1; j <= n; j++:
        int i = j - 1
        c[i][j] = w[i][j]
        r[i][j] = j

    real current_val
    real min_val
    int min_k

    for int d = 2; d <= n; d++:
        for int j = d; j <= n; j++:
            int i = j - d

            min_val = inf
            min_k = -1

            for int k = r[i][j-1]; k <= r[i+1][j]; k++:
                current_val = c[i][k-1] + c[k][j]
                if current_val < min_val:
                    min_val = current_val
                    min_k = k

            c[i][j] = w[i][j] + min_val
            r[i][j] = min_k

    return c, r, w

struct tree:
    int root
    tree left
    tree right

function build_optimal_tree(matrix[int] r, int i, int j) -> tree:
    # r: root matrix
    # i, j: subtree indexes

    if i == j:
        return empty

    return tree(
        root = r[i][j],
        left = build_optimal_tree(r, i, r[i][j] - 1),
        right = build_optimal_tree(r, r[i][j], j)
    )

input array[real] p[n]
input array[real] q[n+1]

c, r, w = knuth_optimal_bst(p, q)
tree bst = build_optimal_tree(r, 0, n)
output bst

Алгоритм рабочий, но, к сожалению, для больших $n$ не подходит. Поскольку алгоритм требует $(n+1)(n+2)/2$ ячейки памяти для хранения цен, в $8$ ГБ оперативной памяти сможет поместиться расчёт для $n \le 65\,535$ .