| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > оценка густоты дерева |
| Автор: DoberZ 30.11.2007, 03:11 |
| есть несколько деревьев. хранятся в реляционной таблице, если это важно. предложите формальный алгоритм, чтобы оценить одим показателем (числом) "густоту" каждого дерева... то есть, скажем, если у него всего одна длинная ветка, на которой последовательно расположены все узлы - то "густота"=0, а если все узлы, кроме корневого, не имеют потомков - то густота=100, например |
| Автор: esperant0 30.11.2007, 09:34 |
| если у него всего одна длинная ветка, на которой последовательно расположены все узлы - то "густота"=0, а если все узлы, кроме корневого, не имеют потомков - то густота=100, инча густота = 50. |
| Автор: DoberZ 30.11.2007, 12:21 |
| собственно, придумал... стоило только сформулировать - и решение назрело. густота=Б/N , где Б-число бездетных узлом, N-число узлов |
| Автор: maxim1000 30.11.2007, 12:23 |
| хм... ну можно, например, рассмотреть соотношение глубины (можно средней) дерева и количества узов при одной длинной ветке они будут практически одинаковы при равномерно раскиданных по дереву узлах - глубина будет чем-то вроде логарифма от количества узлов |
| Автор: _Y_ 30.11.2007, 13:51 |
| Я, по простоте душевной, просто посчитал бы среднее число потомков у предка, учитывая при этом только узлы имеющие хоть одного потомка. |