Создайте сбалансированное двоичное дерево поиска из потока целых чисел

Я только что закончил собеседование, и я боролся с этим вопросом, который кажется мне очень сложным вопросом для интервью на 15 минут.

Вопрос был: Напишите функцию, которая задает поток целых чисел (неупорядоченный), строит сбалансированное дерево поиска. Теперь вы не можете дождаться окончания ввода (это поток), поэтому вам нужно сбалансировать дерево на лету.

Мой первый ответ заключался в том, чтобы использовать дерево Red-Black, которое, конечно же, выполняет эту работу, но я должен предположить, что они не ожидали, что я смогу реализовать красное черное дерево за 15 минут.

Итак, есть ли какое-нибудь простое решение для этой проблемы, о котором я не знаю?

Спасибо,

Dave

Ответ 1

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

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

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

Другим вариантом, который может работать, будет использование splay tree. Это другой тип быстрого BST, который может быть реализован при условии, что у вас есть стандартная функция вставки BST и возможность делать вращения деревьев. Важно отметить, что на практике игры на деревьях чрезвычайно быстры, и они знают, что они (с постоянным коэффициентом), по крайней мере, так же хорошо, как и любое другое статическое дерево двоичного поиска.

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

Надеюсь, это поможет!

Ответ 2

Деревья AA немного проще, чем красно-черные деревья, но я не мог реализовать его с головы.

Ответ 3

Одним из простейших сбалансированных двоичных деревьев поиска является BB (α) -tree. Вы выбираете константу α, которая говорит, насколько неуравновешенным может получить дерево. Во все времена #descendants(child) <= (1-α) × #descendants(node) должен выполняться. Вы рассматриваете его как обычное двоичное дерево поиска, но если формула больше не применяется к некоторому node, вы просто восстанавливаете эту часть дерева с нуля, чтобы он был абсолютно сбалансированным.

Амортизированная временная сложность для вставки или удаления по-прежнему равна O (log N), как и для других сбалансированных двоичных деревьев.