Балансировка (при вставке) АВЛ-дерева

[kuraga]

Объясните, пожалуйста, доходчиво. Ну или сошлитесь. А то в Википедии непонятно, а одногруппники не дают переписать... Спасибо!

[venco]

Что именно в Википедии непонятно?

[kuraga]

Когда какое вращение применяется.

[venco]

Здесь это написано.

[_AliEn_]

Не хотелось создавать новую тему, поэтому пишу здесь.
У меня проблема с пониманием удаления узла из АВЛ-дерева, алгоритм которого описан в Вики. Я не могу понять одну деталь: что означает в "найдем самую близкую по значению вершину в поддереве наибольшей высоты (правом или левом) и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления" слово переместим? Замена подразумевает обмен указателей на дочерние элементы, или просто ключей??

[worm2]

Достаточно поменять ключи, т.к. при такой замене, очевидно, дерево остаётся деревом поиска, а большего здесь и не требуется.
Хотя если ключи длинные и менять их долго, быстрее будет совершить эквивалентную замену указателей.

[_AliEn_]

Мой алгоритм работает неправильно, если удалять несбалансированный корневой элемент, потому что в этом случае не происходит балансировка, так как у него нет родителей. Делал вроде по классическому алгоритму, но не уверен что манипулирую правильно указателями при замещении... Хочется сделать элегантно, без многочисленных условий.

// удаление узла из дерева
TTree removeNode(TTree T, int key, bool* reduced) {
   TTree Q;
   TKey bkey;
   if (T == NULL)
      return NULL;
   if (key == T->key) {
      if (T->left == NULL) {
         Q = T->right;
         _release(T);
         *reduced = TRUE;
         return Q;
      }
      else if (T->right == NULL) {
         Q = T->left;
         _release(T);
         *reduced = TRUE;
         return Q;
      }
                // здесь идет замена. в зависимости баланса удаляемого узла, выбирается симметричный ей узел в левом или правом поддереве
      if (T->balance == L) {
         Q = getRightNode(T->left);
         bkey = Q->key;
         Q->key = T->key;
         T->key = bkey;
         T->left = removeNode(Q, key, reduced);
         T->balance = Q->balance;
         return T;
      }
      else {
         Q = getLeftNode(T->right);
         bkey = Q->key;
         Q->key = T->key;
         T->key = bkey;
         T->right = removeNode(Q, key, reduced);
         T->balance = Q->balance;
         return T;
      }
   }
   if (key < T->key) {
      T->left = removeNode(T->left, key, reduced);
      if (*reduced == TRUE) {
         switch (T->balance) {
            case B:
               T->balance = R;
               *reduced = FALSE;
               break;
            case L:
               T->balance = B;
               break;
            case R:
               if (T->right->balance == L)
                  T = leftBigRot(T);
               else
                  T = leftSmallRot(T);
               T->balance = B;
         };
      }
   }
   if (key > T->key) {
      T->right = removeNode(T->right, key, reduced);
      if (*reduced == TRUE) {
         switch (T->balance) {
            case B:
               T->balance = L;
               *reduced = FALSE;
               break;
            case R:
               T->balance = B;
               break;
            case L:
               if (T->left->balance == R)
                  T = rightBigRot(T);
               else
                  T = rightSmallRot(T);
               T->balance = B;
         };
      }
   }
   return T;
}

День на это потратил, обидно не разобраться!

[worm2]

Не понял насчёт переменной L. Что это?
Если удаляется корневой узел (да и вообще любой не лист), то на этапе обмена узлов перебалансировка не нужна (хотя при последующем рекурсивном вызове может уже понадобиться удаление листа и перебалансировка).

[_AliEn_]

Я конечно извиняюсь, что вылил код без контекста. L, B и R это константы перечисляемого типа TBalance, который устанавливает, в какую сторону узел имеет "перевес" (влево, баланс и вправо соответственно). Логично, балансировку нужно выполнять после вызова функции removeNode, где бы она не вызывалась.
Я собираюсь немного переделать алгоритм, в случае успеха или неудачи все равно отпишусь.

[_AliEn_]

Вот моя версия удаления с балансировкой. Фишка в использовании стека для запоминания пути от удаляемого узла к его inorder predecessor, замена ключей удаляемого узла и inorder predecessor, рекурсивное удаление inorder predecessor и наконец обратный ход с балансировкой. Функции removed_from_left и removed_from_right используются соответственно при удалении узла из левого и правого поддерева. Они просто назначают новый баланс узлу и решают поворачивать дерево или нет.

Используется синтаксис C

TTree removeNode(TTree T, int akey, bool* reduced) {
        if (T == NULL)
                return NULL;
        if (akey == T->key) {
                TTree Q, track[MAX_TREE_HEIGHT];
                int top;
                TKey bkey;
                if (T->left == NULL) { // just throw T and put its right subtree instead of it
                        Q = T->right;
                        _release(T);
                        *reduced = TRUE; // mark subtree height reducing 
                        return Q;
                }
                top = -1;
                track[++top] = T; // T is on the bottom of the track
                //       T - target                  --
                //    x                                |
                //       x                             | track
                //          x                          |
                //             Q - substitute        --
                //                0
                Q = T->left;
                while (Q != NULL) { // getting inorder predecessor and tracking path to it
                        track[++top] = Q;
                        Q = Q->right;
                };
                Q = track[top]; // swap keys of the target node and the substitute node
                bkey = T->key;
                T->key = Q->key;
                Q->key = bkey;
                if (Q != T->left) // remove the substitute node (Q = track[top])
                        track[--top]->right = removeNode(Q, akey, reduced);
                else
                        track[--top]->left = removeNode(Q, akey, reduced); // here track[top-1] is T
                while (top >= 0 && *reduced == TRUE) { // balance track while depth of a subtree is reduced
                        Q = track[top];
                        if (Q != T) { // came from right
                                if (Q != T->left) 
                                        track[top-1]->right = removed_from_right(Q, reduced);
                                else
                                        T->left = removed_from_right(T->left, reduced);
                        }
                        else // came from left
                                T = removed_from_left(T, reduced);
                        top--; // up to T
                }
                return T;
        }
        if (akey < T->key) { // search
                T->left = removeNode(T->left, akey, reduced);
                if (*reduced == TRUE) // if T->left has been unbalanced, balance it
                        T = removed_from_left(T, reduced);
        }
        if (akey > T->key) {
                T->right = removeNode(T->right, akey, reduced);
                if (*reduced == TRUE)
                        T = removed_from_right(T, reduced);
        }
        return T;
}

К минусу отношу необходимость создавания массива для хранения трека (стека) при каждом переходе от удаляемого к заменяемому узлу и многочисленные условия, связанные с тем, что трек неоднородный по направлению (не каждый i элемент трека является правым потомком i-1, это справедливо только для i>1).
Кстати, процедура добавления узла в АВЛ дерево на Вики не доработана. Там при малом правом и левом поворотах, бывшему корневому узлу (да и новому) присваивается нулевой баланс, что не всегда справедливо (если L = C это не справедливо). Может это прокатывает при добавлении, но при удалении я столкнулся с разбалансировкой дерева из-за этого недочета.