Какой самый эффективный алгоритм добавления элемента в дерево?

Question

[hoxnox]

Имеется входящая возрастающая последовательность (каждый следующий элемент строго больше предыдущего). Необходимо добавлять элементы последовательности в дерево таким образом, чтобы оно оставалось сбаланисрованным. Какой наиболее эффективный алгоритм?

Answer 1

[vgrichina]

По идее в таком случае просто нет смысла использовать дерево, эффективнее будет динамически растущий массив с бинарным поиском по нему.

Еще если сначала сохранить последовательность в массив, то можно потом из нее построить сбалансированное бинарное дерево за O(N), просто обойдя массив рекурсивно в правильном порядке.

Comments

[hoxnox]

>эффективнее будет динамически растущий массив с бинарным поиском по нему
Спорно. Поиск по сбаллансированному дереву эффективней бинарного поиска по отсортированному массиву. А в моем случае дерево создается один раз, для последующего многократного поиска. Даже ради небольшого выигрыша в эффективности поиска готов жертвовать медленной инициализацией.

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

[CKOPOBAPKuH]

> Поиск по сбаллансированному дереву эффективней бинарного поиска по отсортированному массиву

почему это? и там и там — O(log(n)). асимптотика одинаковая.
но отсортированный массив аналогичен идеально сбалансированному дереву, а авл или красночерные такими не являются и выше идеального в среднем в 1.3-1.4 раза.

второе преимущество массива — локальность данных. чем глубже вы в дереве, тем меньше ваш working set (а в случае с деревом память соседние элементы могут отстоять далеко в адресном пространстве; тут можно сделать node pool и выделять память для элементов оттуда)

[Алексей Сундуков]

>Какой самый эффективный алгоритм добавления элемента в дерево
и
>Даже ради небольшого выигрыша в эффективности поиска готов жертвовать медленной инициализацией

Мне тут видится противоречие. Если важна скорость поиска, а скорость инициализации не так критична, то какая разница какой алгоритм добавления? Берите быстрый алгоритм на выборке, а не добавлении.

Answer 2

[Артур Хашаев]

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

Comments

[Артур Хашаев]

И да, если у вас элементы последовательности — целые числа, то можете посмотреть в сторону vEB-дерева. Вообще-то, есть еще более эффективные структуры, чем эта, но относительно деревьев отрезков и деревьев поиска она уже работает быстрее. Но лучше это всё проверить на практике, конечно.

Answer 3

[sgzmd]

В любом случае ты получишь O(N log N) так что AVL.

Comments

[hoxnox]

Как показать, что в «любом случае» так получится? Было такое чувство, но математически не знаю как обосновать…