Какой самый эффективный алгоритм добавления элемента в дерево?
Имеется входящая возрастающая последовательность (каждый следующий элемент строго больше предыдущего). Необходимо добавлять элементы последовательности в дерево таким образом, чтобы оно оставалось сбаланисрованным. Какой наиболее эффективный алгоритм?
По идее в таком случае просто нет смысла использовать дерево, эффективнее будет динамически растущий массив с бинарным поиском по нему.
Еще если сначала сохранить последовательность в массив, то можно потом из нее построить сбалансированное бинарное дерево за O(N), просто обойдя массив рекурсивно в правильном порядке.
>эффективнее будет динамически растущий массив с бинарным поиском по нему
Спорно. Поиск по сбаллансированному дереву эффективней бинарного поиска по отсортированному массиву. А в моем случае дерево создается один раз, для последующего многократного поиска. Даже ради небольшого выигрыша в эффективности поиска готов жертвовать медленной инициализацией.
Насчет правильного обхода массива понятно. Я подумал, что может существовать какой-то эффективный алгоритм добавления элемента, если мы знаем, что он больше всех предыдущих, но, похоже, я ошибался.
> Поиск по сбаллансированному дереву эффективней бинарного поиска по отсортированному массиву
почему это? и там и там — O(log(n)). асимптотика одинаковая.
но отсортированный массив аналогичен идеально сбалансированному дереву, а авл или красночерные такими не являются и выше идеального в среднем в 1.3-1.4 раза.
второе преимущество массива — локальность данных. чем глубже вы в дереве, тем меньше ваш working set (а в случае с деревом память соседние элементы могут отстоять далеко в адресном пространстве; тут можно сделать node pool и выделять память для элементов оттуда)
>Какой самый эффективный алгоритм добавления элемента в дерево
и
>Даже ради небольшого выигрыша в эффективности поиска готов жертвовать медленной инициализацией
Мне тут видится противоречие. Если важна скорость поиска, а скорость инициализации не так критична, то какая разница какой алгоритм добавления? Берите быстрый алгоритм на выборке, а не добавлении.
Ну, например, можно использовать декартовы деревья, если ключи отсортированы, то мы их все за линейное время можем запихнуть. Но, как выше замечено, смысла в этом немного — бинарный поиск всех спасет.
И да, если у вас элементы последовательности — целые числа, то можете посмотреть в сторону vEB-дерева. Вообще-то, есть еще более эффективные структуры, чем эта, но относительно деревьев отрезков и деревьев поиска она уже работает быстрее. Но лучше это всё проверить на практике, конечно.
