Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 15.03.2011, 22:35
Новичок

Отправить личное сообщение для nim_cch Посмотреть профиль Найти все сообщения от nim_cch
 
Регистрация: 15.03.2011
Сообщений: 3

Вопрос по обходу АВЛ
Я знаю есть довольно простой алгоритм последовательного обхода в порядке возрастания ключей. Но мне нужно получать элементы по случайному индексу из этого представления.
  #2  
Старый 15.03.2011, 22:59
гocть

 
Сообщений: n/a

тогда тебе нужно хранить и поддерживать в каждой вершине размер поддерева. с ним можно просто за log n найти k-й ключ.
  #3  
Старый 16.03.2011, 00:35
Новичок

Отправить личное сообщение для nim_cch Посмотреть профиль Найти все сообщения от nim_cch
 
Регистрация: 15.03.2011
Сообщений: 3

Черевато большими затратами памяти

Последний раз редактировалось nim_cch, 16.03.2011 в 12:22.
  #4  
Старый 16.03.2011, 00:39
гocть

 
Сообщений: n/a

откажись от хранения каждой вершины по отдельности на хипе, храни все в однем массиве или пуле, и выиграешь достаточно места на оверхеде от хипа
  #5  
Старый 16.03.2011, 01:21
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>Тогда эта структура много весит
а на баланс какого типа поле отведено?
  #6  
Старый 16.03.2011, 12:31
Новичок

Отправить личное сообщение для nim_cch Посмотреть профиль Найти все сообщения от nim_cch
 
Регистрация: 15.03.2011
Сообщений: 3

Сообщение от MBo
а на баланс какого типа поле отведено?
sbyte

Сообщение от гocть
откажись от хранения каждой вершины по отдельности на хипе, храни все в однем массиве или пуле, и выиграешь достаточно места на оверхеде от хипа
Тогда как балансировать дерево? Мне приходит в голову только метод перестановок. Это черевато потерей производительности. Если конечно существует другой способ, которого я не знаю, это было бы супер.
  #7  
Старый 16.03.2011, 13:06
гocть

 
Сообщений: n/a

покажи код, какой у тебя есть, иначе сложно давать конкретные советы
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
вопрос гость Реализация, исходники, языки 1 10.05.2009 03:21
вопрос по программе Миха Реализация, исходники, языки 5 09.05.2008 10:33
Вопрос по деревьям seregarem Поиск и обсуждение книг/сайтов 1 09.04.2008 10:41
вопрос по БПФ SEreGA Обработка изображений, звук, графика 1 03.12.2007 11:00
Вопрос по ДСТ NepsteR Математические алгоритмы (другое) 1 21.07.2007 18:19