Построение идеально-сбалансированного дерева по массиву слов.
Построение идеально-сбалансированного дерева по массиву слов.
1.Можно ли построить идеально сбалансированное дерево по следующему алгоритму:
1) упорядочиваем входной поток элементов (слов) и одновременно исключаем повторяющиеся (или увеличиваем их кратность)
2) После конца ввода ищем «медиану», слово0 т.е. 1 или 2 слова, стоящие в середине массива.
3) Относительно этого корня и строим дерево по принципу:
А)делим левую половину подмассива пополам и находим слово1 в середине
Б) делим правую половину подмассива пополам и находим слово2 в середине
Вставляем слово 1 в левую, а слово2 в правую ветвь слова 0
В) далее рекурсивно повторяем алгоритм для вершин следующего уровня
2. Для многократной загрузки в деревья скажем слов из файла, видимо понадобится процедура т.н. ребалансировки дерева (т.е выгрузки из дерева старого массива, объединение его с новым и построение нового сбалансированного дерева). Где можно об этом узнать?
3. Где вообще применяются методы построения хорошо сбалансированных деревьев?
Полагаю что для увеличения скорости поиска (двоичный поиск). В каких классах задач данный метод актуален?
Ведь доступ к оперативной памяти сейчас очень быстрый
В кн. Е.М.Демидовича “Основы алгоритмизации и программирования. Си» автор ставит задачу “усреднения времени поиска данных в больших массивах информации». Для которго наряду с бинарным деревом предлагаются также способы построения массива указателей и хэш-функции.
Действительно ли подход с использованием сбалансированного дерева (не так просто реализуемый) является наилучшим в этом классе задач?
1.Можно ли построить идеально сбалансированное дерево по следующему алгоритму:
1) упорядочиваем входной поток элементов (слов) и одновременно исключаем повторяющиеся (или увеличиваем их кратность)
2) После конца ввода ищем «медиану», слово0 т.е. 1 или 2 слова, стоящие в середине массива.
3) Относительно этого корня и строим дерево по принципу:
А)делим левую половину подмассива пополам и находим слово1 в середине
Б) делим правую половину подмассива пополам и находим слово2 в середине
Вставляем слово 1 в левую, а слово2 в правую ветвь слова 0
В) далее рекурсивно повторяем алгоритм для вершин следующего уровня
2. Для многократной загрузки в деревья скажем слов из файла, видимо понадобится процедура т.н. ребалансировки дерева (т.е выгрузки из дерева старого массива, объединение его с новым и построение нового сбалансированного дерева). Где можно об этом узнать?
3. Где вообще применяются методы построения хорошо сбалансированных деревьев?
Полагаю что для увеличения скорости поиска (двоичный поиск). В каких классах задач данный метод актуален?
Ведь доступ к оперативной памяти сейчас очень быстрый
В кн. Е.М.Демидовича “Основы алгоритмизации и программирования. Си» автор ставит задачу “усреднения времени поиска данных в больших массивах информации». Для которго наряду с бинарным деревом предлагаются также способы построения массива указателей и хэш-функции.
Действительно ли подход с использованием сбалансированного дерева (не так просто реализуемый) является наилучшим в этом классе задач?
Идеальная балансировка дерева обычно никому не нужна из за катастрофической сложности процедуры балансировки при модификации дерева. Прогрессивному человечеству в настоящий момент известны два основных типа хорошо сбалансированных деревьев: АВЛ деревья и красно-черные деревья.
По вопросу хранения дерева в файле. Записывать нужно именно дерево: первая строка файла - корень, вторая - левый сын, третья - правый сын и т.д. особыми случаями будут листья: их можно помечать особым образом.
По вопросу хранения дерева в файле. Записывать нужно именно дерево: первая строка файла - корень, вторая - левый сын, третья - правый сын и т.д. особыми случаями будут листья: их можно помечать особым образом.