Струтура данных "дерево" нужна бывает довольно часто.
Внимание, вопрос: кто какую реализацию использует? такое ощущение, что все уже нашли свой идеал... (Впечатление такое оттого, что в "Исходниках" на деревья реагируют крайне слабенько)
Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>Струтура данных "дерево" нужна бывает довольно часто. ЗХ>Внимание, вопрос: кто какую реализацию использует? такое ощущение, что все уже нашли свой идеал... (Впечатление такое оттого, что в "Исходниках" на деревья реагируют крайне слабенько)
А потому что в STL уже контейнер типа map есть.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>>Струтура данных "дерево" нужна бывает довольно часто. ЗХ>>Внимание, вопрос: кто какую реализацию использует? такое ощущение, что все уже нашли свой идеал... (Впечатление такое оттого, что в "Исходниках" на деревья реагируют крайне слабенько) LVV>А потому что в STL уже контейнер типа map есть.
ну и шо?
например, в STL есть вектор с операциями пуш и поп,
а есть стек (контейнер более высокого логического ур-ня)
если нужно именно дерево, на мэп все равно приходится некую обертку делать, хоть бы и тонкую.
ЗЫ: уточняю: я имел в виду не двоичное дерево, а любых размеров.
Здравствуйте, Зверёк Харьковский, Вы писали:
LVV>>А потому что в STL уже контейнер типа map есть. ЗХ>ну и шо? ЗХ>например, в STL есть вектор с операциями пуш и поп, ЗХ>а есть стек (контейнер более высокого логического ур-ня) ЗХ>если нужно именно дерево, на мэп все равно приходится некую обертку делать, хоть бы и тонкую.
ЗХ>ЗЫ: уточняю: я имел в виду не двоичное дерево, а любых размеров.
В смысле арность?
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, LaptevVV, Вы писали:
LVV>>В смысле арность? WH>Ему надо чтобы у одного узла было сколько угодно потомков.
угу
виноват. хреново формулирую.
Здравствуйте, Зверёк Харьковский, Вы писали:
LVV>>>В смысле арность? WH>>Ему надо чтобы у одного узла было сколько угодно потомков. ЗХ>угу ЗХ>виноват. хреново формулирую.
Это в памяти или на диске?
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>Здравствуйте, Зверёк Харьковский, Вы писали:
LVV>>>>В смысле арность? WH>>>Ему надо чтобы у одного узла было сколько угодно потомков. ЗХ>>угу ЗХ>>виноват. хреново формулирую. LVV>Это в памяти или на диске?
вопроса не понял
Здравствуйте, Зверёк Харьковский, Вы писали:
LVV>>>>>В смысле арность? WH>>>>Ему надо чтобы у одного узла было сколько угодно потомков. ЗХ>>>угу ЗХ>>>виноват. хреново формулирую. LVV>>Это в памяти или на диске? ЗХ>вопроса не понял
Если на диске, то там рулят B-деревья в различных модификациях.
А если в памяти, то ни в одной классической книжке не встречал программистского подхода к этому вопросу — все сплошь математика.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>Если на диске, то там рулят B-деревья в различных модификациях.
B-деревья и в памяти очень хорошо рулят.
1. Не фрагментируют память.
2. При больших объемах поиск быстрее чем в массиве за счет использования кэша ппроцессора куда попадают данные верхних уровней.
3. Простота и скорость навигации (в Б+ дреревьях)
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, LaptevVV, Вы писали:
LVV>Если на диске, то там рулят B-деревья в различных модификациях. LVV>А если в памяти, то ни в одной классической книжке не встречал программистского подхода к этому вопросу — все сплошь математика.
Не задача гораздо банальнее. Очень часто просто нужна структура для хранения какойто иерархии XML, файловая система...
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, LaptevVV, Вы писали:
LVV>А если в памяти, то ни в одной классической книжке не встречал программистского подхода к этому вопросу — все сплошь математика.
в ней. никаких свер-возможностей не надо.
просто, есть классы, хранящиеся деревом (каталоги-подкаталоги, и все такое)
нужно
1. возможность обойти дерево (итератор)
2. возможность обойти только данную ветку (итератор')
3. возможность добавить-удалить потомков к ветке.
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, LaptevVV, Вы писали:
LVV>>Если на диске, то там рулят B-деревья в различных модификациях. LVV>>А если в памяти, то ни в одной классической книжке не встречал программистского подхода к этому вопросу — все сплошь математика. WH>Не задача гораздо банальнее. Очень часто просто нужна структура для хранения какойто иерархии XML, файловая система...
во! и я ж об энтом!!!
внутреннее представление не сильно важно (на данном этапе), важно -- класс с интерфейсом дерева!
ЗХ>1. возможность обойти дерево (итератор) ЗХ>2. возможность обойти только данную ветку (итератор') ЗХ>3. возможность добавить-удалить потомков к ветке. ЗХ>
ЗХ>неужели никому такое не надо?
Прошу прощения за назойливость в http://www.1c.hippo.ru/cgi-bin/predownl.cgi?id=2019
сделал простое иерархическое хранилище.
А все что ты пишешь это не деревья, а связные списки.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Serginio1, Вы писали:
S> Прошу прощения за назойливость в http://www.1c.hippo.ru/cgi-bin/predownl.cgi?id=2019 S>сделал простое иерархическое хранилище. S> А все что ты пишешь это не деревья, а связные списки.
Это ж как же? а то. что там иерархия -- это все побоку?
Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>Здравствуйте, Serginio1, Вы писали:
S>> Прошу прощения за назойливость в http://www.1c.hippo.ru/cgi-bin/predownl.cgi?id=2019 S>>сделал простое иерархическое хранилище. S>> А все что ты пишешь это не деревья, а связные списки.
ЗХ>Это ж как же? а то. что там иерархия -- это все побоку?
Тогда джагед массивы тоже деревья. Всетаки деревья подчиняются некоторому закону роста и балансировке.
А из связных спиках делай какую угодно иерархию, а классические деревья всего лишь подвид связных списков.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>Здравствуйте, Serginio1, Вы писали:
S>> Тогда джагед массивы тоже деревья... ЗХ>а это хто за зверь, извиняюсь за невежество?
Это массив массивов.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>>Здравствуйте, Serginio1, Вы писали:
S>>> Тогда джагед массивы тоже деревья... ЗХ>>а это хто за зверь, извиняюсь за невежество? S>Это массив массивов.
К коим также можно отнести и Б деревья.
и солнце б утром не вставало, когда бы не было меня
Существует структура данных, которая определяется таким образом:
у каждого элемента 0..N потомков. Один корень.
Если я еще не все перезабыл, то это, стало быть, ациклический направленный граф с одной корневой вершиной.
Хорошо.
Нужна она для представления иерархически организоанной информации (файлы на диске, XML, да что угодно!)
Внимание, вопрос:
КТО КАКИЕ КЛАССЫ ИСПОЛЬЗУЕТ, когда сталкиваеться с такой структурой. Теоретически, такое бывает надо довольно часто.
