Оптимальные деревья

← →
Wistler (2003-12-21 12:59) [0]

Подскажите где можно взять исходники построения оптимального дерева?

← →
Digitman (2003-12-21 13:05) [1]

что есть "оптимальное дерево" ?

← →
Wistler (2003-12-21 13:56) [2]

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

← →
Igorek (2003-12-21 14:24) [3]

> Wistler © (21.12.03 13:56) [2]
> Нам заранее известны вероятности запроса всех элементов,
> и нужно элементы к которым обращаются часто разместить поближе
> к корню, чтоб к ним не ходить далеко, а элементы, к которым
> почти никогда не обращаются, можно разместить и где-то подальше.

сам сказал решение :-)))

← →
MBo (2003-12-21 14:34) [4]

>Wistler
Динамически такое делает Splay Tree

← →
Digitman (2003-12-21 15:17) [5]

> чтоб к ним не ходить далеко

что значит "ходить далеко" ?

> разместить поближе к корню

что за глупости ? если ветка С растет из ветки B от корня A, то как можно "пересадить" ветку C прямо в корень A ? кто ветку "пустил", там ей и "расти")

← →
Digitman (2003-12-21 15:30) [6]

> Wistler

если же ты ведешь речь о том, как перечислить все ветки, растущие из заданной (включая подветки каждой из найденных веток) без использования рекурсии и прочих зачастую не слишком производительных алгоритмов, то следует просто предусмотреть списочную структуру, каждый эл-т которой имеет примерно такой вид :

Id //ид-р ветки
ParentId //ид-р род.ветки
RootId //ид-р корня
Level //абс. уровень вложенности, считая от корня

при "рождении"/"пересадке" ветки в список добавляется эл-т, имеющий такую структуру, при "выкорчевывании" - этот эл-т удаляется

тогда запрос на получение всех веток/подветок, дочерних к заданной, выливается в банальный запрос к этому списку вида :

выбрать все Id, где RootId и ParentId такие-то

← →
Digitman (2003-12-21 15:33) [7]

и вот здесь уже можно вести речь о некоей оптимизации : следует просто проиндексировать поля этого списка и делать выборки с учетом только нужных индексов

Оптимальные деревья Найти похожие ветки