Оптимизация с деревьями

[evg_m]

ИМЕННО:
делаем обязательные и часто используемые быстрые операции типа добавления и удаления
при желании добавляем медленные и запускаемые по желанию операции типа сборка мусора/упаковка/сжатие.

НО! после упаковки повторное использование идентификаторов потребует МЕДЛЕННОЙ и частой если удалили много(!) вставки в произвольное место массива.
Либо реализации и использования ОТДЕЛЬНОЙ процедуры сортировки (опять же медленной).
Чтобы можно было обеспечить быстрый поиск.

Чего то мне это не нравится.

Если не боимся замедления работы при добавлении/удалении то сжатие (ТОЧНЕЕ переупорядочивание после сжатия/добавления) можно проводить и постоянно.

[waleri]

Опять вопрос - почему именно обязательно массив?

[Vapaamies]

Товарищи, вы зашли не в ту степь. Для дерева в БД лучше посмотреть какую-либо практическую реализацию иерархических запросов, вроде connect by/start with в Oracle. В этом случае рекурсию выполняет сервер, но данные хранятся в естественном виде. На других СУБД при наличии индекса легко сэмулировать рекурсию с клиента.

Если же БД необязательна, стоит обратить внимание в сторону двоичных деревьев или двоичных деревьев поиска.

В силу своей природы иерархические данные не могут иметь числового индекса, это ведь не массив! Данные в дереве всегда адресуются по ключам -- и в БД, и в двоичных деревьях.

[Utkin]

Опять вопрос - почему именно обязательно массив?

Это вовсе не обязательно. Я просто пытаюсь сначала имитировать работу в программе, отладить все, найти подводные камни и если взлетит, перенести на БДшечку. Что предлагаете Вы?

В силу своей природы иерархические данные не могут иметь числового индекса, это ведь не массив!

Поэтому я и ввел искусственные идентификаторы, чтобы не зависить от реализации.

[Vapaamies]

Сообщение от Utkin

Поэтому я и ввел искусственные идентификаторы, чтобы не зависить от реализации.

Они должны быть уникальны и отсортированы, то есть представлять собой настоящий ключ. В двоичном дереве сортировка выполняется реализацией дерева, в БД -- СУБД, где используется разновидность двоичных деревьев.

[Utkin]

Всем спасибо за участие в теме. Появился другой вопрос смежного характера (решил не плодить темы). Суть в операции перемещения. Итак требуется переместить одну ветвь дерева в другую. Естественно может возникнуть ситуация когда в дочернюю ветвь пытаются перенести предка и это вызовет бесконечное создание ветвей (вот раньше такое можно было наблюдать в первых версиях Norton Commander).
Вопрос:
Могу ли я теоретически, разбирая только путь и не проверяя физически все соответствующие узлы, проверить такую ситуацию. Чисто интуитивно чувствую что да, достаточно проверить что все узлы копируемой ветви полностью повторяют (и/или короче) приемника.
Например:
c:\1 --> c:\1\2
Проводник будет ругаться Чисто бездоказательно я тоже. Так можно ли проводить проверку путей не касаясь самих узлов? Очевидно что символическая проверка путей быстрей и проще в реализации...