Тернарное дерево поиска: бор, который не тратит память на пустые ячейки

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

Как думаешь, сколько памяти съест бор

Словарь автодополнения на 18 тысяч слов. Бор с массивом детей на 26 букв: узлов 56 тысяч, ячеек под детей - 26 на узел, полтора миллиона. В каждом узле в среднем занят один-два ребёнка.

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

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

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

Механизм: три ссылки и два вида шагов

узел: символ ch, ссылки МЕНЬШЕ, РАВНО, БОЛЬШЕ, флаг «здесь конец слова»

найти(узел, слово, i):
    символ слова < ch  → идти в МЕНЬШЕ  (та же буква слова)
    символ слова > ch  → идти в БОЛЬШЕ  (та же буква)
    равны:  последняя буква → ответ - флаг конца
            иначе           → идти в РАВНО, следующая буква

вставка - тот же спуск; где ссылка пустая - новый узел

На уровне одной буквы узлы «меньше-больше» образуют обычное дерево поиска по символам, которые встречались в этом месте слов. Если вставлять вразнобой, это дерево в среднем сбалансировано, и на букву приходится около log₂(число вариантов) шагов. Если вставлять по алфавиту, каждый новый символ больше всех предыдущих и цепляется вправо - дерево буквы вырождается в цепочку, как обычное дерево поиска на возрастающих ключах.

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

Правило

Тернарное дерево поиска - бор, у которого выбор ребёнка устроен деревом поиска по символу: в узле один символ и ссылки МЕНЬШЕ, РАВНО, БОЛЬШЕ. Узлов столько же, сколько рёбер бора, а ячеек под детей - три на узел вместо размера алфавита. Поиск делает на каждой букве несколько шагов «меньше-больше» и один «равно». Порядок вставки важен: вразнобой дерево сбалансировано, по алфавиту вырождается. Все операции бора с началами слов - автодополнение, поиск по префиксу - сохраняются.

Разбор: четыре слова

вставляем: кот, код, кит, ток

к ─РАВНО─ о ─РАВНО─ т (конец «кот»)
│         │         │
│         │         МЕНЬШЕ: д (конец «код»;  д < т)
│         МЕНЬШЕ: и ─РАВНО─ т (конец «кит»;  и < о)
БОЛЬШЕ: т ─РАВНО─ о ─РАВНО─ к (конец «ток»;  т > к)

поиск «кит»:
  к: равно → следующая буква «и», узел о
  о: и < о → МЕНЬШЕ, узел и
  и: равно → буква «т», узел т
  т: равно, последняя → флаг конца есть: найдено
четыре шага на три буквы

Бор с массивом детей прошёл бы три перехода, но держал бы в каждом из десяти узлов (с корнем) по 26 ячеек - 260 ячеек под эти четыре слова; у тернарного - девять узлов по три, 27 ячеек.

Разбор: восемнадцать тысяч слов

Программа строит тернарное дерево на 18 тысячах случайных слов, считает узлы и ячейки под детей против бора с массивом на алфавит, а затем сравнивает число шагов поиска при вставке вразнобой и по алфавиту.

import random

rng = random.Random(30)
bukvy = "abcdefghijklmnopqrstuvwxyz"
slova = sorted({"".join(rng.choice(bukvy[:12])
                        for _ in range(rng.randint(3, 9)))
                for _ in range(20000)})
po_alfavitu = list(slova)
rng.shuffle(slova)                    # вставлять вразнобой


class Uzel:                           # узел тернарного дерева
    __slots__ = ("ch", "men", "rav", "bol", "konec")

    def __init__(self, ch):
        self.ch, self.konec = ch, False
        self.men = self.rav = self.bol = None


def vstavit(u, s, i=0):
    if u is None:
        u = Uzel(s[i])
    if s[i] < u.ch:
        u.men = vstavit(u.men, s, i)
    elif s[i] > u.ch:
        u.bol = vstavit(u.bol, s, i)
    elif i + 1 < len(s):
        u.rav = vstavit(u.rav, s, i + 1)
    else:
        u.konec = True
    return u


def najti(u, s):
    i, shagi = 0, 0
    while u is not None:
        shagi += 1
        if s[i] < u.ch:
            u = u.men
        elif s[i] > u.ch:
            u = u.bol
        elif i + 1 < len(s):
            u, i = u.rav, i + 1
        else:
            return u.konec, shagi
    return False, shagi


koren = None
for s in slova:
    koren = vstavit(koren, s)

uzly_bora = {""}                      # бор: узел на каждое начало слова
for s in slova:
    for k in range(1, len(s) + 1):
        uzly_bora.add(s[:k])
uzly_tst, stek = 0, [koren]
while stek:
    u = stek.pop()
    if u:
        uzly_tst += 1
        stek += [u.men, u.rav, u.bol]

print("слов", len(slova), " узлов бора", len(uzly_bora),
      " узлов тернарного", uzly_tst)
print("ячеек под детей: бор-массив", len(uzly_bora) * 26,
      " тернарное", uzly_tst * 3)
dlina = sum(len(s) for s in slova)
koren2 = None
for s in po_alfavitu:                 # вставка по алфавиту
    koren2 = vstavit(koren2, s)
for imya, k in (("вразнобой", koren), ("по алфавиту", koren2)):
    shagov = sum(najti(k, s)[1] for s in slova)
    print(f"вставка {imya}: шагов поиска на символ",
          round(shagov / dlina, 2))
assert all(najti(koren, s)[0] for s in slova)
assert not najti(koren, "zzz")[0]

слов 18356  узлов бора 56024  узлов тернарного 56023
ячеек под детей: бор-массив 1456624  тернарное 168069
вставка вразнобой: шагов поиска на символ 2.55
вставка по алфавиту: шагов поиска на символ 4.13

Узлов столько же, сколько у бора (без корня), ячеек под детей - в 8.7 раза меньше. Цена - 2.55 шага на букву вместо одного. При вставке по алфавиту шагов 4.13 на букву - деревья букв перекосились. Слова в программе из двенадцати букв; на полном алфавите разрыв в памяти ещё больше.

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

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

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

Автодополнение и проверка орфографии на больших словарях, когда бор с массивами не помещается в память, а хеш-таблицы не умеют искать по началу слова. Хранение таблиц маршрутизации и словарей символов в компиляторах. Тернарное дерево удобно и для «почти совпадений»: поиск с одной ошибкой или с подстановочным символом обходит ветви «меньше-больше» естественно, без перебора всего алфавита в каждом узле.

Теперь сам

В дерево из разбора вставили слово кол. Где появится новый узел и сколько шагов займёт поиск кол после вставки?