поиск узла в дереве

← →
Kozhanov (2002-05-24 14:18) [0]

есть дерево

aaa
|-aaaa
|-aaaaa
bbb
|-bbbb
ccc

количество узлов может быть любым

Проблема : нужно придумать нумерацию узлов для быстрого
поиска нужного узла, но не уникальный номер узла, а такой номер,
который бы сразу давал представление где узел нужно искать,т.е.
чтобы не "лопатить" в цикле всё дерево целиком для поиска нужного узла.

Если ли на этот счёт какие-нибудь умные алгоритмы ?
В общем, поделитесь своими соображениями ?

← →
MBo (2002-05-24 14:30) [1]

если дерево не будет часто обновляться, то можно что-нибудь подобное:
двузначные (если хватит) номера в списке child каждого уровня
первый уровень
00
0000
0001
000100
000101
01
02
0200
020000
020000
0201

← →
Kozhanov (2002-05-24 14:47) [2]

> MBo
Спасибо.
Но..это будет работать не для всех вариантов.
А мне нужно чтобы работало "в любых условиях"

В принципе можно придумать для каждого узла
ID типа вот такого :

1|1|20|...|10|2

т.е. парсить строку (например и вытаскивать нужные ID узлов).

Но может быть есть поразумнее что-нибудь ???

← →
Shaman_Naydak (2002-05-24 15:19) [3]

Можно взять классический отрезковый способ:
Каждый узел характеризуется отрезком - 2 числами Low & High
Дочерние узлы вкладываются в отрезок папы и т.д..
Легче объяснить на примере твоего дерева

Root = 1,14
|-aaa = 2,7
| |-aaaa = 3,6
| |-aaaaa = 4,5
|-bbb = 8,11
| |-bbbb = 9,10
|-ccc = 12,13

Обычное применение этой технологии, правда, в БД как альтернатива
ParentID. Я к этим 2 полям добаляю еще обычно Level - уровень..

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

В общем, и целом, вот такая вот бодяга

← →
Kozhanov (2002-05-24 15:44) [4]

> Shaman_Naydak
Спасибо.
Хотя не совсем понятно.
1. Как вычисляется (1,14) для Root и (2,7) для aaa ?
2. Как, зная (4,5), получить aaaaa ?

В общем расскажи немного по-подробней, пожалуйста.

← →
Shaman_Naydak (2002-05-24 19:22) [5]

Сперва отвечу на 2 вопрос..
Надо найти элемент 4,5
a)Ищем на корневом уровне элемент, у которого left<=4 and right>=5
Находим Root.
b)в Root ищем элемент, у которого left<=4 and right>=5
Находим aaa
c)в ааа ищем элемент, у которого left<=4 and right>=5
Находим aaaa

Но вообще-то это на порядок лучше применять для построения дерева, не используя классическую ссылку на родителя, а используя left, right, +очень рекомендую level
То есть структура должна быть вида обычный список (я ж говорю, это обычно применяется в БД)- типа
array of record
left, right, level: Integer;
NodeValue: Variant;
end;

По поводу 1 вопроса..
Расскажу для простого варианта, когда все лежит плотно упаковонное (то есть отрезки без дырок)
Предположим, что надо вставить в корень, то есть папа = ""
Если список пуст, то (1,2) иначе (max(right)+1, max(right)+2)

Теперь, что надо вставить в (4,5)..
Во-первых, сперва убеждаемся, что такой есть..
Дальше
для всех left >5 сделать left:=left+2;
для всех right >=5 сделать right:=right+2;
Элемент = (5,6) (Папа при этом превратится в (4,7) )

← →
Дима347874 (2002-05-25 02:00) [6]

http://sdm.viptop.ru/articles/sqltrees.html

← →
Kozhanov (2002-05-28 19:31) [7]

> Дима347874
Спасибо !
> Shaman_Naydak
Спасибо !
Не мог бы ты вкратце рассказать про свой подход
с использованием "триады" (left, right, level) ?
Меня интересуют : описание самого алгоритма и используемых
в этом случае структур данных.

← →
Kozhanov (2002-05-31 19:30) [8]

> Shaman_Naydak
Аууууууууууууу...

поиск узла в дереве Найти похожие ветки