Задачки на дерево
Вот понадобилось, может интересно будет.
Есть "плоское" описание дерева в виде
{
"Id": 0,
"Name": "Root",
"ParentId": 0
},
1. Как наиболее оптимально сгенерить "деревянную" структуру?
TreeItem {
long Id;
string Name;
List<TreeItem> Children;
}
2. Как наиболее оптимально найти всех детишек начиная с Id x для "плоского" варианта?
1. Как наиболее оптимально сгенерить "деревянную" структуру?
Ну это легко. Я бы при построении дерева сделал бы вспомогательный Dictionary и таким образом построил бы дерево за один проход "плоского" описания дерева.
2. Как наиболее оптимально найти всех детишек начиная с Id x для "плоского" варианта?
Без построения дерева будет куча итераций. А с построением дерева все просто - я бы имплементировал бы "вложенный" IEnumerable и IEnumerator для TreeItem.
1. Как наиболее оптимально сгенерить "деревянную" структуру?
-----
Отсортировать - парентИД,ИД, потом строить в один проход.
2. Как наиболее оптимально найти всех детишек начиная с Id x для "плоского" варианта?
------
Неоднозначность в определении ВСЕХ.
Можно читать - всех непосредственных, можно - вообще всех потомков.
В общем случае самый быстрый поиск будет если построить матрицу смежности. Но это ^2 по памяти. Можно - индекс - но тут много от данных зависит.
Можно список перестроить в сбалансированное дерево с упорядочением узлов - там будет быстро, но это не тот "плоский" вариант что дан.
Если по памяти критично - проверял бы в один проход является ли узел потомком. Для ускорения - добавил бы поле с отметкой "потомок" и отсекал проверку по нему.
Просто задачу переверни - не проверять потомков, а проверять предков - и все решится в один пrоход.
Вот дерево:
0-1-4-6
0-2-3-5
1-8-9
4-7
Как за один проход по списку (0:null), (1:0), (2:0), (3:2), (4:1), (5:2), (6:4), (7:4), (8:1), (9:8) узнать , является ли узел 5 потомком узла 4?
Ну и насколько я понял задачу, нужно получить список всех потомков.
Как за один проход по списку (0:null), (1:0), (2:0), (3:2), (4:1), (5:2), (6:4), (7:4), (8:1), (9:8) узнать , является ли узел 5 потомком узла 4?
-----
Берешь узел 5 и проверяешь есть в его предках узел 4. ПарентИД в узлах есть.
Ну либо делаешь акселерацию для поиска ВСЕХ - добавляешь поле с отметкой - этот узел входит в список парентов и дальше (до корня или узла 4) искать не надо.
Берешь узел 5 и проверяешь есть в его предках узел 4. ПарентИД в узлах есть.
За 1-й проход ты определил, что у узла 5 в предках есть узел 2. Ну и, что предок узла 2 узел 0. Является ли узел 5 потомком узла 4 ты не выяснил.
Понятно, что тут надо строить некую структуру. Простым проходом по всем элементам получится непозволительно долго. Поэтому лучше построить дерево и потом итерировать каждую отдельную вершину.
За 1-й проход ты определил, что у узла 5 в предках есть узел 2. Ну и, что предок узла 2 узел 0. Является ли узел 5 потомком узла 4 ты не выяснил.
------
Не понял.
Я взял узел 5.
Проверил цепочку предков (паренИД) до руута на наличие узла 4.
Если нашел - есть потомок - отметил, если нет - не потомок - не надо больше ничего.
Перешел к следующему непровернному узлу.
Что еще надо проверять?
Все делается в один проход по узлам и куче возвратов (но их существенно меньше чем прямых проверок) по парентам.
Про возможную акселерацию процесса - дополнительное поле и три статуса - пока не говорим.
Понятно, что тут надо строить некую структуру.
-----
Зачем?!! У тебя уже все что надо есть в наличии...
Поэтому лучше построить дерево и потом итерировать каждую отдельную вершину.
-----
Может почитать Кнута? Том 3. Сортировка и поиск. 
Переверни задачу. Не ищи всех потомков от данного - это долго и сложно, а проверяй наличие данного в предках - это элементарно и быстро.
Проверил цепочку предков (паренИД) до руута на наличие узла 4.
Цепочку предков надо сначала построить. Если в моем примере ID элемента совпадает с индексом в массиве, то это не значит, что так случается всегда ;)
Если же цепочку предков (т.е. на самом деле это дерево) не строить, то для проверки предков придется итерировать по элементам списка.
Ну или можем вообще считать, что ID элемента - это строка.
При этом если мы уже построили дерево, то для функции "дай всех потомков" достаточно реализовать примитивный итератор. Задачи "проверить, является ли элемент потомком" не стоит ;)
Цепочку предков надо сначала построить.
-----
Не надо ничего строить - все уже есть в узлах. Как будет сделана навигация - не важно, но по условию дан "плоский" формат - ссылки будут индексами, а не референсами. Но чем именно они будут - без разницы.
Ну или можем вообще считать, что ID элемента - это строка.
-----
Да хоть - квадратное - лишь бы можно было получить узел парента и из него вынуть его парента и так до рута.
Если же цепочку предков (т.е. на самом деле это дерево) не строить
-----
В каждом узле уже есть указание на предка. т.е. есть навигация по предкам. Что еще надо строить - не понимаю.
Отсортировать - парентИД,ИД, потом строить в один проход.
Сортировка +1 проход - это только если с базы прямо брать, получится за один
Неоднозначность в определении ВСЕХ.
теоретически да, а практически - есть какие то проблемы в нахождении всех непосредственных потомков?
мне кажется что Visitor будет попроще и удобнее в данном случае.
IEnumerable работает в связке с foreach, т.е.
TreeItem currentItem = <как-то выбираешь вершину>
foreach (TreeItem item in currentItem)
{
System.Diagnostic.Trace.WriteLine (item.Name);
}
напечатает тебе всех детишек у item.
В общем случае самый быстрый поиск будет если построить матрицу смежности. Но это ^2 по памяти.
Только не матрицу смежности, а неравномерный массив с id. И операция поиска всех достижимых "детей" будет требовать не O(n) времени (0 и 1 из строки матрицы надо превратить в список id) а O(1).