рандомизированные двоичные деревья поиска

Question

Рандомизированные деревья двоичного поиска, такие как treap, дают хорошую производительность (в порядке O (log n)) с высокой вероятностью, избегая при этом сложных (и дорогостоящих) операций перебалансировки, которые необходимы для детерминированных сбалансированных деревьев, таких как AVL, red-blackm, АА и т. Д.

Мы знаем, что если мы добавим случайные ключи к простому BST, мы можем ожидать, что он достаточно сбалансирован. Простая причина заключается в том, что число сильно несбалансированных деревьев для n узлов намного меньше, чем количество «почти сбалансированных» деревьев, и, следовательно, случайный порядок вставки ключей, скорее всего, закончится приемлемым деревом.

В этом случае в «Искусстве компьютерного программирования» Кнут дает чуть более 1,3 * lg2 (n) как среднюю длину пути, что довольно неплохо. Он также говорит, что удаление случайного ключа из случайного дерева сохраняет его случайность (и, следовательно, хорошую среднюю балансировку).

Таким образом, представляется, что двоичное дерево поиска, в котором ключи вставляются и удаляются в случайном порядке, скорее всего, даст производительность в порядке O (log n) для всех трех операций: поиск, вставка и удаление.

Тем не менее, мне интересно, даст ли следующий подход те же хорошие свойства:

• взять хеш-функцию h (x), которая, как известно, является «хорошей» (например, она обеспечивает равномерное распределение ключей)
• использовать порядок, установленный h (x) на клавишах вместо порядка на k.
• в случае столкновения, заказать по ключу. Это должно быть редкостью, если хеш-ключ достаточно хорош и диапазон хеш-функции намного больше, чем набор ключей.

Чтобы привести пример BST для ключа {4, 3, 5, 1, 2}, вставленного в таком порядке, будет:

                  4
                 / \
                3   5
               /\
              1  2

Предполагая, что хеш-функция отобразит их (соответственно) {221,142,12,380,18), мы получим.

                    221(4)
                   /   \
              142(3)  380(1)
             /    \
           12(5) 18(2)

Ключевым моментом является то, что «обычный» BST может вырождаться, потому что ключи вставляются в соответствии с тем же отношением порядка, которое используется для их сохранения в дереве (их «естественный» порядок, например, в алфавитном порядке строки), но хеш-функция вызывает упорядочение ключей, совершенно не связанное с «естественным», и, следовательно, должно давать такие же результаты, как если бы ключи были вставлены в случайном порядке.

Сильное предположение, что хеш-функция "хорошая", но я думаю, что она не является необоснованной.

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

Видите ли вы какие-либо недостатки в моих рассуждениях? Кто-нибудь уже пытался это сделать?

Answer 1

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

Причина, по которой мы не видим, чтобы другие люди использовали что-то подобное, IMO, заключается в том, что если вы упорядочиваете по хеш-функции, ваша структура данных больше не сортируется. Да, он все еще сортируется по хеш-функции, но элемент с наименьшей хеш-функцией обычно не является тем элементом, который вам нужно искать, тогда как поиск, например, наименьший / самый большой / k-й элемент, часто бывает полезен. Поскольку структура данных больше не будет иметь этого свойства, имеет больше смысла иметь хеш-таблицу, которая использует хеш-функцию для хранения в массиве, чтобы получить производительность O (1) вместо O (log n).

Answer 2

Звучит разумно для меня. Вы искали, чтобы увидеть, было ли это уже оформлено или хотя бы отмечено?

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

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

Answer 3

Хотя обычно для хранения используется что-то вроде B-дерева, обычно это похоже на расширяемое хеширование. И да, это обычно работает довольно хорошо.

Answer 4

Разве это не единственный способ сохранить хеш-таблицу?