структура данных для treeview

Question

Я хотел бы реализовать «TreeView» как визуальное отображение дерева в список, причем отступ в списке обеспечивается глубиной отображаемого узла. Моя конкретная проблема - это древо 2 уровня с глубиной 100 000 узлов на первом уровне, каждый узел содержит 20 узлов (т. Е. 100 000 папок, каждый из которых содержит 20 файлов). В настоящее время я поддерживать отображение из дерева в std::map, что для полностью расширенного дерева (2 000 000 потенциально видимые элементы в «TreeView») выглядит следующим образом:

key value 
0 pointer to parent node 0 
20 pointer to parent node 1 
40 pointer to parent node 2 
... 

Это означает, что элементы списка [0, 19 ] покрыты родительским узлом 0, [20, 39] родительским узлом 1, ... Если я разрушится узел 0, отображение должно быть обновлено:

key value 
0 pointer to parent node 0 
1 pointer to parent node 1 
21 pointer to parent node 2 
... 

Здесь элемент списка 0 покрывается родителю узел 0, элементы списка [1, 20] с помощью родительского узла 1, ... что означает, что ключи из 99 000 значений в std::map необходимо обновить при свертывании узла 0. Это означает 99 000 удалений и вставки на карту, поскольку в противном случае ключи не могут быть обновлены. Какая структура данных и/или контейнер позволят мне обновить список отображения -> список с меньшими усилиями?

Answer 1

Это похоже на то, с чем вы можете использовать расширенное дерево. Это сделает обновление этих ключей логарифмическим временем, а поиск по ключу будет также логарифмическим.

К сожалению, я не могу написать полный ответ здесь и сейчас, как мне нужно голову, но мы надеемся, что эта статья поможет: http://je4d.blogspot.co.uk/2013/01/boostintrusive-annotated-trees-part-1.html