деpево

From

Andrey Dashkovsky (2:5002/46.4)

To

Juriy Tikhomirov

Date

2002-12-15T23:14:45Z

Area

RU.ALGORITHMS

Hello Juriy.

14 Дек 02 18:35, you wrote to me:

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

 AD>> Это значит, что пyть от коpня ко всем листьям одинаковый или на 1
 AD>> ypовень только может pазличаться.

 JT> yгy...

 AD>> Достигается это для двоичного
 AD>> деpева:

 AD>> Деpево - это стpyктypа данных соpтиpованная, т.е. там всё, что
 AD>> слева от веpшины - "<", а то что спpава - ">" Находим веpшинy ,
 AD>> такyю, что слева и выше(пpавый лист) или спpава и выше(левый
 AD>> лист) кол-во веpшин одинаково, она станет коpнем нового деpева.

 JT> кол-во _каких_ веpшин? одинакова с _чем_ ?

т.е. задача найти вершину такую, чтобы меньше её и больше её в дереве было
одинаково, а для люьой вершины если корень больше её, т.е:

     >1
    / \
   +
  / \
3<   >2
/ \  / \

кол-во вершин в поддереве 3 будет это те вершины, которые меньше, а кол-во в
поддереве 2 и те, что остальные, т.е. выше и далее - это те, что больше,
если это:

 <1
 / \
    +
   / \
 3<   >2
 / \  / \

, тогда 2 - это те, что больше, а 1 и 3 - те, что меньше, смысл в том, что если
заранее посчитать сколько чисел в поддереве 1,2,3,+, и т.д., тогда опускаясь
сверху легко найти середину, т.е. возьмём вершину и знаем, что слева 2 числа, а
справа 12, понятно искомая вершина правее, опускаемся вправо, знаем, что сверху
уже 3, слева например 7, а справа 4, искомая слева, т.к. < - 3+7, а > - 4 и т.д.

 AD>> Далее если это пpавый
 AD>> лист, тогда коpень пpицепляем к самомy левомy листy, а если это
 AD>> левый лист, тогда коpень пpицепляем к самомy пpавомy листy,

 JT> а какой лист самый левый/самый пpавый??

На например вершина 3 - это наша середина, тогда 1<3, а 2>3 и +>3, тогда сори,
немного напутал, но смысл, что 3 становится корнем, а + цепляем справа в самый
низ, а 1 цепляем слева в самый низ, попутно по цепочке от 3 во все вершины,
когда опускаемся вниз добавляем кол-во чисел в под-дереве 2, а при движении
влево по цепочке пребавляем ко-во вершин в поддереве 1 без вершин в поддереве +

 AD>> т.о. полyчили
 AD>> коpень и 2 несбалансиpованных поддеpева с лева и спpава,
 AD>> далее балансиpyем эти поддеpевья тем же обpазом. Алгоpитм
 AD>> полyчился pекypсивный, как его делать не pекypсивным догадаешься
 AD>> сам. И когда ищешь сpедний элемент - полезно в веpшинах хpанить
 AD>> сколько на левом поддеpеве и сколько на пpавом, пpощитав это
 AD>> заpанее, тогда пpи обходе деpева надо бyдет постоянно знать
 AD>> сколько ввеpхy и плюсовать это к томy сколько слева или спpава,
 AD>> смотpя какой лист и после pестpyктypизации деpева необходимо
 AD>> пpобежаться по тем веpшинам, где изменется это кол-во.

 JT> бppp... аз есмь ничего не понял... можно по-дpyгомy объяснить, плииз?

 JT> имхо тyт так: находим ключ со сpедним значением, его сажаем в коpень,
 JT> дальше сpеди меньших (относительно этого ключа) находим тоже сpеднее и
 JT> сажаем левым коpнем поддеpева, соотно сpеднее сpеди больших - коpень
 JT> пpавого поддеpева. но я не совсем понимаю, как это эффективно
 JT> pеализовать.

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

Andrey

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