двоичное дерево поиска с рандомизированной вставкой против красного черного дерева

Question

Я прочитал на красных черных деревьях, и я понимаю, что они пытаются решить проблему неуравновешенности дерева. Однако, что, если вы будете использовать рандомизированное вложение. Например:

Рассмотрим следующие отсортированных чисел, которые должны быть вставлены:

1,2,3,4,5,6,7,8,9,10

Если мы наивно вставляется BST дерево будет выглядеть следующим образом: ..

В этом случае дерево будет супер несбалансированным и поиск будет линейный O (N)

Однако, если ш e рандомизированное вложение, оно может выглядеть более сбалансированным (но, вероятно, не сбалансированным как красное черное дерево в среднем случае?). Если бы мы использовали красное черное дерево, это обеспечит почти сбалансированный BST, но с небольшим количеством накладных расходов. Когда один начертить линию желающего эту дополнительную нагрузки на эффективность по сравнению с использованием рандомизированного вставки BST Кроме того, для «онлайн алгоритмов» (self balancing binary search trees)

Answer 1

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

В Википедии есть статья here.

Answer 2

Существует такая линия. Вы всегда помните о мотивации использования любой динамической структуры данных (например, BST и Red-Black Tree). Мотивация довольно простая: сохранить данные в определенной форме (упорядоченные в случае BST). Итак, если вы не хотите, чтобы держал, вы можете использовать что-то вроде отсортированного массива. Сортировка массива может быть выполнена на O(n log n). И вы можете делать все с отсортированными данными (например, min/max/nth) в постоянное время! Это экстремально быстро! Но, если вы планируете добавлять новое значение в отсортированный массив. Здесь все становится интересным. Итак, у вас есть shift ваш массив и вставьте новое значение в нужное место. Требуется O(n). И это не похоже на правильный путь. Но хорошие новости. Есть деревья, которые могут обрабатывать вставку и удаление в O(log n) времени.

Так как насчет линии. Я бы сказал. Если вы планируете только вставлять новые элементы в дерево. И входные значения являются случайными. Таким образом, BST отлично подходит для этой задачи. Но если вы планируете сделать какое-то удаление, вам нужно создать новое дерево для балансировки, такое как RBTree, потому что дисбаланс BST из-за удаления (операция удаления на BST несимметрична и создает дерево с высотой sqrt(n)).

Существует третий случай. Вы можете попытаться найти алгоритм симметричного удаления для BST (который не решается в течение 50 лет) и стать рок-звездой информатики. Goog повезло с этими вещами!