ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrey Dashkovsky                    2:5002/46.4    12 Dec 2002  12:14:24
 To : Juriy Tikhomirov
 Subject : деpево
 -------------------------------------------------------------------------------- 
 

 12 Дек 02 01:15, you wrote to all:
 
  JT> поясните, пожалyйста, что значит балансиpовка сабжа и как это
  JT> pеализyется.
 
 Это значит, что путь от корня ко всем листьям одинаковый или на 1 уровень
 только может различаться. Достигается это для двоичного дерева:
 
 Дерево - это структура данных сортированная, т.е. там всё, что слева от вершины
 - "<", а то что справа - ">" Hаходим вершину , такую, что слева и выше(правый
 лист) или справа и выше(левый лист) кол-во вершин одинаково, она станет корнем
 нового дерева.
 Далее если это правый лист, тогда корень прицепляем к самому левому листу, а
 если это левый лист, тогда корень прицепляем к самому правому листу, т.о.
 получили корень и 2 несбалансированных поддерева с лева и справа, далее
 балансируем эти поддеревья тем же образом. Алгоритм получился рекурсивный, как
 его делать не рекурсивным догадаешься сам. И когда ищешь средний элемент -
 полезно в вершинах хранить сколько на левом поддереве и сколько на правом,
 прощитав это заранее, тогда при обходе дерева надо будет постоянно знать сколько
 вверху и плюсовать это к тому сколько слева или справа, смотря какой лист и
 после реструктуризации дерева необходимо пробежаться по тем вершинам, где
 изменется это кол-во.
 
 Andrey
 
 ... Любишь кататься - полезай в кузов.
 --- GoldED+/386 1.1.4.7
  * Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    деpево   Juriy Tikhomirov   12 Dec 2002 02:15:12   деpево   Andrey Dashkovsky   12 Dec 2002 12:14:24   деpево   Juriy Tikhomirov   14 Dec 2002 19:35:02   Re: деpево   Andrey Belyakov   15 Dec 2002 03:33:33   деpево   Juriy Tikhomirov   15 Dec 2002 09:15:24   деpево   Andrey Dashkovsky   16 Dec 2002 00:14:45