Построение идеально-сбалансированного дерева по массиву слов.

[eugrita]

1.Можно ли построить идеально сбалансированное дерево по следующему алгоритму:
1) упорядочиваем входной поток элементов (слов) и одновременно исключаем повторяющиеся (или увеличиваем их кратность)
2) После конца ввода ищем «медиану», слово0 т.е. 1 или 2 слова, стоящие в середине массива.
3) Относительно этого корня и строим дерево по принципу:
А)делим левую половину подмассива пополам и находим слово1 в середине
Б) делим правую половину подмассива пополам и находим слово2 в середине
Вставляем слово 1 в левую, а слово2 в правую ветвь слова 0
В) далее рекурсивно повторяем алгоритм для вершин следующего уровня

2. Для многократной загрузки в деревья скажем слов из файла, видимо понадобится процедура т.н. ребалансировки дерева (т.е выгрузки из дерева старого массива, объединение его с новым и построение нового сбалансированного дерева). Где можно об этом узнать?

3. Где вообще применяются методы построения хорошо сбалансированных деревьев?
Полагаю что для увеличения скорости поиска (двоичный поиск). В каких классах задач данный метод актуален?
Ведь доступ к оперативной памяти сейчас очень быстрый
В кн. Е.М.Демидовича “Основы алгоритмизации и программирования. Си» автор ставит задачу “усреднения  времени поиска данных в больших массивах информации». Для которго наряду с бинарным деревом предлагаются также способы построения массива указателей и хэш-функции.
Действительно ли подход с использованием сбалансированного дерева (не так просто реализуемый) является наилучшим в этом классе задач?

[Вад]

1. По-моему, вполне можно.

2. Самые основы - хотя бы в Википедии (и тут про балансировку двоичных в целом)

3. Поскольку перебалансировка занимает много времени, идеальные деревья применяют в случаях, когда дерево очень редко меняется. В противном случае используют красно-чёрные деревья, так как для них процедуры вставки-удаления выполняются быстрее, хотя это и приводит к потерям скорости поиска в дереве до 2х раз. Ассоциативные контейнеры строят на красно-чёрных деревьях.

[Mayor]

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

Красно-черные деревья применяются в контейнерах со временем вставки, поиска элемента по значению за o(logN).

Если тебе требуется время o(1), нужно воспользоваться хешированием, на базе него реализованы ассоциативные контейнеры в питоне\перле.

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