Балансировка дерева и приведение его к АВЛ сбалансированному дереву

257
27 февраля 2017, 12:34

В файле записаны числа, нужно их считать, построить дерево поиска. После этого сбалансировать дерево, выполнив RR поворот. Проблема возникла с тем, как определить именно несбалансированный узел (есть гарантия, что такой узел только один). Написал функцию, которая определяет высоту заданного ей узла. А как найти именно несбалансированный узел? Ниже функция, которая возвращает высоту узла.

 int HeightNode(PNode Tree)
 {
     int l,r,height = 0;
     if(Tree != 0)
    {
         l = HeightNode(Tree -> Left);
         r = HeightNode(Tree -> Right);
         height = ((l > r) ? l : r) + 1;
    }
    return height;
 }
Answer 1

Решение получилось таким. Вроде работает. 

 void FindDebalancedNode(PNode & tree)
 {
    if (!tree)
        return;
    FindDebalancedNode(tree->Left);
    FindDebalancedNode(tree->Right);
    int leftSubtree = HeightOfSubtree(tree -> Left);
    int rightSubtree = HeightOfSubtree(tree -> Right);
    if (leftSubtree + 1 < rightSubtree)
    {
        DoRRTurn(tree); 
    }
}
 int HeightOfSubtree(PNode tree)
 {
     int l,r,height = 0;
     if(tree != 0)
     {
         l = HeightOfSubtree(tree -> Left);
         r = HeightOfSubtree(tree -> Right);
         height = ((l > r) ? l : r) + 1;
     }
     return height;
  }
 void DoRRTurn(PNode & p)
 {
    PNode q = p-> Right;
    p->Right = q -> Left;
    q->Left = p;
    p = q;
 }
READ ALSO
end() vs cend()
c++

end() vs cend()

Всегда ли это предложение возвращает true для стандартных контейнеров?

 266
Выборка данных с группировкой по дате
MySQL

Выборка данных с группировкой по дате

Две таблицы, связь один ко многимКак выбрать присутствующих сотрудников, за день

 851
SQL выборочный UPDATE
MySQL

SQL выборочный UPDATE

Есть таблица, T1, в ней нужно установить значение поля V2 в 'A3', но только в том случае, если это поле было равно 'A2'Сделать это нужно для всех записей,...

 280
Выборка из двух таблиц через JOIN
MySQL

Выборка из двух таблиц через JOIN

Сижу 2 часа, не могу разобраться как получить данные из двух таблиц

 268