Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Построение идеально-сбалансированного дерева по массиву слов.  (Прочитано 14738 раз)
0 Пользователей и 1 Гость смотрят эту тему.
eugrita
Помогающий

ru
Offline Offline

« : 03-12-2009 09:54 » 

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

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

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

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 03-12-2009 14:05 » 

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

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

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

ru
Offline Offline

« Ответ #2 : 05-01-2010 08:18 » new

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

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

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

Имхо, лучше поначалу не забивать себе голову кчд реализацией, пока не поймешь задач,у в которой именно это потребуется.
« Последнее редактирование: 05-01-2010 10:17 от Sel » Записан

1n c0de we trust
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines