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

Question

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

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

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

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

Спасибо

Dave

Answer 1

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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