[]
J>>А деревья меняются по ходу дела? Или создаются вначале и так и живут? J>>А то можно ведь параллельную структуру данных завести.
CS>Меняются.
J>>Можно ли каждому элементу присвоить номер (в процессе заполнения дерева)? Если да, то вместо hash_set можно использовать просто битовый vector и обращаться к нему по номеру элемента — чистить его очень быстро и легко. J>>Если у тебя flat tree (т.е. поверх массива) — то это вообще тривиально будет.
CS>Не понял что имеется ввиду. Поясни. Элементов много.
Рискну влезть и предположить, что jazzer имел ввиду, что если все элементы дерева хранятся в одном массиве, а в children и visible_chidlren используются лишь указатели на элементы в этом массиве, то каждому элементу можно сопоставить индекс в массиве. В этом случае visited будет битовым вектором, и признак посещения элемента — это лишь бит по индексу элемента.
Мне кажется, если есть возможность элементам при создании в дереве присваивать возрастающие id = last_used_id++, то при незначительных изменениях в дереве (ну и при условии что элементы не перемещаются между деревьями) все элементы в нем будут иметь индексы от 0 до last_used_id и битовый вектор подойдет в качестве visited.
