Здравствуйте, нет ли у кого-нибудь исходника класса на С++, описывающего дерево с восемью узлами? Мне много наворотов не надо, лишь бы оно было динамическим и были реализованы методы добавить/удалить элемент, сортировка и балансировка. Желательны, конечно, комментарии, но если их нет — не беда. Самому все реализовывать не рационально, уверен, такой класс уже написан, отлажен и не раз.
11.01.04 00:41: Перенесено модератором из 'C/C++' — ПК
Здравствуйте, notepad, Вы писали:
N>Здравствуйте, нет ли у кого-нибудь исходника класса на С++, описывающего дерево с восемью узлами? Мне много наворотов не надо, лишь бы оно было динамическим и были реализованы методы добавить/удалить элемент, сортировка и балансировка. Желательны, конечно, комментарии, но если их нет — не беда. Самому все реализовывать не рационально, уверен, такой класс уже написан, отлажен и не раз.
Все-таки бинарные деревья — более распространенное явление. К ним и алгоритмы придуманы, и структуры, и используются они...
Опять же, с бинарным деревом меньше вариантов упорядочивания: это либо L < P < R (двоичное дерево поиска), либо P < L && P < R (пирамида).
Восьмеричное же дерево — это что? На вскидку могу предложить только B-tree (Б-дерево).
Кстати, Б-деревья сбалансированы. Копай в их сторону.
Octree применяются при написании 3D дижков в качестве ооочень эффективной структуры для отсечения того что заведомо не видимо, объектов которые заведомо не сталкиваются...
... << RSDN@Home 1.1 beta 2 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, notepad, Вы писали:
N>Здравствуйте, нет ли у кого-нибудь исходника класса на С++, описывающего дерево с восемью узлами? Мне много наворотов не надо, лишь бы оно было динамическим и были реализованы методы добавить/удалить элемент, сортировка и балансировка. Желательны, конечно, комментарии, но если их нет — не беда. Самому все реализовывать не рационально, уверен, такой класс уже написан, отлажен и не раз.
А ты уверен что тебе Octree надо? Я себе слабо представляю динамическое Octree и еще хуже как, а главное зачем его сортировать и балансировать.
... << RSDN@Home 1.1 beta 2 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
WH>А ты уверен что тебе Octree надо? Я себе слабо представляю динамическое Octree и еще хуже как, а главное зачем его сортировать и балансировать.
Да-да, именно octree. Ты правильно описал, где эта структура данных применяется очень эффективно. Я тоже слабо представляю как балансировать/сортировать такое дерево. Зачем? Скорость поиска и обработки элементов сильно возрастает.
Здравствуйте, notepad, Вы писали:
N>Да-да, именно octree. Ты правильно описал, где эта структура данных применяется очень эффективно. Я тоже слабо представляю как балансировать/сортировать такое дерево. Зачем? Скорость поиска и обработки элементов сильно возрастает.
Хм. Похоже кто-то из нас не понимает что такое Octree и как его готовить.
Я себе его представляю так:
Берем пространство допустим куб со стороной километер и делим его на 8 кубов со стороной 500 метров и так далие пока не достигнем куба приемлимого размера. Теперь берем все объекты из пространства и в зависимости от их координат и размеров (если объект попадает в несколько кубов сразу) заносим ссылки на объекты в соответствующие кубы (наименьшего размера). Теперь для того чтобы проверить столкновения надо только пройтись по спискам в кубах.
А теперь внимание вопросы: Где тут динамическое дерево? Что тут можно отсортировать? И что тут балансировать?
И вопрос на засыпку: Как вобще можно отсортировать дерево? Балансировка дерева это я понимаю, а что такое сортировка дерева?
... << RSDN@Home 1.1 beta 2 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Перекуём баги на фичи!
