деpево

From

Andrey Dashkovsky (2:5002/46.4)

To

Juriy Tikhomirov

Date

2002-12-12T11:14:24Z

Area

RU.ALGORITHMS

Hello Juriy.

12 Дек 02 01:15, you wrote to all:

 JT> поясните, пожалyйста, что значит балансиpовка сабжа и как это
 JT> pеализyется.

Это значит, что путь от корня ко всем листьям одинаковый или на 1 уровень
только может различаться. Достигается это для двоичного дерева:

Дерево - это структура данных сортированная, т.е. там всё, что слева от вершины
- "<", а то что справа - ">" Находим вершину , такую, что слева и выше(правый
лист) или справа и выше(левый лист) кол-во вершин одинаково, она станет корнем
нового дерева.
Далее если это правый лист, тогда корень прицепляем к самому левому листу, а
если это левый лист, тогда корень прицепляем к самому правому листу, т.о.
получили корень и 2 несбалансированных поддерева с лева и справа, далее
балансируем эти поддеревья тем же образом. Алгоритм получился рекурсивный, как
его делать не рекурсивным догадаешься сам. И когда ищешь средний элемент -
полезно в вершинах хранить сколько на левом поддереве и сколько на правом,
прощитав это заранее, тогда при обходе дерева надо будет постоянно знать сколько
вверху и плюсовать это к тому сколько слева или справа, смотря какой лист и
после реструктуризации дерева необходимо пробежаться по тем вершинам, где
изменется это кол-во.

Andrey

... Любишь кататься - полезай в кузов.
--- GoldED+/386 1.1.4.7
 * Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)