|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Astafiev 2:5000/228.16 05 Apr 2002 13:04:52
To : All
Subject : Trees Comparison
--------------------------------------------------------------------------------
Было бы интересно обсудить алгоритмы сравнения деревьев.
представьте себе, что имеется две древовидные иерархии.
они различаются только немножко, причем где-то в глубине.
глубина иерархии может достигать 200-300 и впринципе, неограничена.
количество узлов во всей иерархии может достигать 200-300 тыс элементов.
интересен оптимальный алгоритм поиска различий.
для стандартизации, давайте предположим, что два наших дерева схематически
справа и слева. будем сравнивать правое дерево с левым, т.е. из правого
вычитать левое или правое дерево будет образцовым.
мы должны получить ответ какие узлы есть в правом дереве, но отсутвуют в левом.
(то что не нашлось в левом дереве) и наоборот, что есть в левом, но отсутсвует
в правом.
Hужно получить оба ответа. Еще можно представить задачу вот так:
дерево со временем меняется, что-то исчезает, что-то в нем добавляется.
Hужно получить ответ - что добавилось, а что исчезло.
Я подумал над решением и пока остановился на следущем.
Достаточно выяснять только какие узлы HЕ находятся в левом дереве, взяв правое
дерево за образец. Таким образом, мы узнаем что у нас добавилось в правом
дереве по сравнению с левым. Поменяв деревья местами, мы узнаем что из бывшего
правого дерева исчезло.
Просто, но алгоритм запускается уже два раза, что неоптимально.
Само сравнение у меня происходит так - я двигаюсь (пока что пальцем =;) )
по правому дереву, начиная с корня. В левом дереве мы тоже начинаем с
корня. У меня есть понятие текущего узла в левом и правом дереве, поиск
подузлов я начинаю всегда с текущего в данный момент узла, для того чтобы не
выполнять каждый раз поиск в левом дереве.
Поиск для меня чрезвычайно медленно работает, т.к.
структуру дерева я храню вырожденно и компактно,
выглядит она в виде большого массива, в котором каждый элемент обладает двумя
полями и выглядит так
[количество дочерних нод или 0, если это конечный лист]
[данные ноды]
[..] дочерние ноды, если есть.
[..]
т.е. дерво вида
[A]
/ \
[B] [C]
/ \ / \
[D] [E] [F] [G]
будет записано в виде
[2]
[A]
[2]
[B]
[0]
[D]
[0]
[E]
[2]
[C]
[0]
[F]
[0]
[G]
дерево-образец я обхожу рекурсивно, зная каждый раз, сколько мне нужно считать
дочерних нод.
Можно сравнивать деревья так, что взяв очередной узел в правом дереве, кидаться
искать его в левом дереве. Так как я храню деревья вырожденно, то для поиска
элемента на n-глубине иерархии, нужно перебрать все дерево до него.
Может быть хранить деревья невырожденно, т.е. хранить у каждого узла-родителя
ссылку на узел-потомок?
Еще наблюдение - Двигаясь по правому образцовому дереву, мы имеем информацию о
адресе узла, т.е. теущий уровень, и возможно, положение (позиция) на узле.
Т.е. если дополнительно записав информацию о порядке обхода дочерних узлов,
можем ли мы получить ускорение выборки, записвая адрес узла F из рисунка выше
как 121 - глубина иерархии 3уровня, первый(левый) узел A, второй (правый)
узел C, третий, (снова левый) узел F.
И все-таки не хотелось бы выполнять поиск. хотелось бы просто двигаться с узла
на узел, причем за один проход ответить что лишнее, а что недостает. И сделать
это быстро. Какие будут мысли?
---
* Origin: Alex Raider/ Flash inc. 1992-2002 (2:5000/228.16)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
