Рубрики

AVL Tree | Набор 2 (удаление)

Мы обсуждали вставку AVL в предыдущем посте . В этом посте мы будем следовать аналогичному подходу для удаления.

Шаги, чтобы следовать для удаления .
Чтобы убедиться, что данное дерево остается AVL после каждого удаления, мы должны расширить стандартную операцию удаления BST, чтобы выполнить некоторую перебалансировку. Ниже приведены две основные операции, которые можно выполнить, чтобы повторно сбалансировать BST без нарушения свойства BST (keys (left) <key (root) <keys (right)).
1) левое вращение
2) Правое вращение

T1, T2 and T3 are subtrees of the tree rooted with y (on left side)
or x (on right side)
                y                               x
               / \     Right Rotation          /  \
              x   T3   – - – - – - – >        T1   y
             / \       < - - - - - - -            / \
            T1  T2     Left Rotation            T2  T3
Keys in both of the above trees follow the following order
      keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.

Позвольте w быть узлом, который будет удален
1) Выполните стандартное удаление BST для w.
2) Начиная с w, поднимитесь и найдите первый неуравновешенный узел. Пусть z будет первым неуравновешенным узлом, y будет дочерним элементом с большей высотой z, а x будет дочерним элементом с большей высотой y. Обратите внимание, что определения x и y отличаются от вставки здесь.
3) Перебалансировать дерево, выполнив соответствующие повороты на поддереве с корнем z. Может быть 4 возможных случая, которые необходимо обработать, так как x, y и z могут быть организованы 4 способами. Ниже приведены возможные 4 договоренности:
а) у левый потомок z, а х левый потомок y (левый левый регистр)
б) у левый потомок z, а х правый потомок y (левый правый регистр)
c) y — правильный потомок z, а x — правильный потомок y (правый правильный случай)
г) у — правый потомок z, а х — левый потомок y (правый левый регистр)

Как и при вставке, ниже приведены операции, которые должны быть выполнены в вышеупомянутых 4 случаях. Обратите внимание, что, в отличие от вставки, исправление узла z не исправит полное дерево AVL. После исправления z нам, возможно, придется исправить и предков z (см. Эту видео-лекцию для доказательства)

а) левый левый корпус

T1, T2, T3 and T4 are subtrees.
         z                                      y 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

б) левый правый случай

     z                               z                           x
    / \                            /   \                        /  \ 
   y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2

в) правый правый случай

  z                                y
 /  \                            /   \ 
T1   y     Left Rotate(z)       z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4

г) правый левый корпус

   z                            z                            x
  / \                          / \                          /  \ 
T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      y
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
   x   T4                      T2   y                  T1  T2  T3  T4
  / \                              /  \
T2   T3                           T3   T4

В отличие от вставки, при удалении после выполнения поворота в точке z нам, возможно, придется выполнить вращение в отношении предков z. Таким образом, мы должны продолжать отслеживать путь, пока не достигнем корня.

Пример:

Узел со значением 32 удаляется. После удаления 32 мы поднимаемся вверх и находим первый небалансируемый узел, который равен 44. Мы помечаем его как z, его дочерний элемент большей высоты как y, который равен 62, а дочерний элемент большей высоты y как x, который может быть либо 78, либо 50, поскольку оба той же высоты. Мы рассмотрели 78. Теперь дело идет справа налево, поэтому мы выполняем вращение влево.

С реализация
Ниже приведена реализация C для удаления дерева AVL. Следующая реализация C использует рекурсивное удаление BST в качестве основы. В рекурсивном удалении BST, после удаления, мы получаем указатели на всех предков по очереди снизу вверх. Таким образом, нам не нужен родительский указатель для перемещения вверх. Сам рекурсивный код перемещается вверх и посещает всех предков удаленного узла.
1) Выполните обычное удаление BST.
2) Текущий узел должен быть одним из предков удаленного узла. Обновите высоту текущего узла.
3) Получить коэффициент баланса (высота левого поддерева — высота правого поддерева) текущего узла.
4) Если коэффициент баланса больше 1, то текущий узел не сбалансирован, и мы находимся либо в левом левом случае, либо в левом правом случае. Чтобы проверить, является ли это случаем «Левый левый» или «Левый правый», получите коэффициент баланса левого поддерева. Если коэффициент баланса левого поддерева больше или равен 0, тогда это левый левый случай, иначе левый правый случай.
5) Если коэффициент баланса меньше -1, то текущий узел является несбалансированным, и мы находимся либо в правой правой стороне, либо в правой левой стороне. Чтобы проверить, является ли это правым правым регистром или правым левым регистром, получите коэффициент баланса правого поддерева. Если коэффициент баланса правого поддерева меньше или равен 0, то это правый правый случай, иначе правый левый случай.

C ++

// C ++ программа для удаления узла из дерева AVL
#include<bits/stdc++.h>

using namespace std;

  
// Узел дерева AVL

class Node 

    public:

    int key; 

    Node *left; 

    Node *right; 

    int height; 

}; 

  
// Полезная функция для получения максимума
// из двух целых

int max(int a, int b); 

  
// Вспомогательная функция для получения высоты
// дерева

int height(Node *N) 

    if (N == NULL) 

        return 0; 

    return N->height; 

  
// Полезная функция для получения максимума
// из двух целых

int max(int a, int b) 

    return (a > b)? a : b; 

  
/ * Вспомогательная функция, которая выделяет

   новый узел с данным ключом и

   NULL левый и правый указатели. * /

Node* newNode(int key) 

    Node* node = new Node();

    node->key = key; 

    node->left = NULL; 

    node->right = NULL; 

    node->height = 1; // новый узел изначально

                      // добавлено в лист

    return(node); 

  
// Функция полезности справа
// вращаем поддерево с корнем у
// Смотрите диаграмму, приведенную выше.
Node *rightRotate(Node *y) 

    Node *x = y->left; 

    Node *T2 = x->right; 

  

    // Выполнить вращение

    x->right = y; 

    y->left = T2; 

  

    // Обновление высоты

    y->height = max(height(y->left), 

                    height(y->right)) + 1; 

    x->height = max(height(x->left), 

                    height(x->right)) + 1; 

  

    // Возвращаем новый корень

    return x; 

  
// Служебная функция слева
// вращаем поддерево с корнем x
// Смотрите диаграмму, приведенную выше.
Node *leftRotate(Node *x) 

    Node *y = x->right; 

    Node *T2 = y->left; 

  

    // Выполнить вращение

    y->left = x; 

    x->right = T2; 

  

    // Обновление высоты

    x->height = max(height(x->left), 

                    height(x->right)) + 1; 

    y->height = max(height(y->left), 

                    height(y->right)) + 1; 

  

    // Возвращаем новый корень

    return y; 

  
// Получить коэффициент баланса узла N

int getBalance(Node *N) 

    if (N == NULL) 

        return 0; 

    return height(N->left) - 

           height(N->right); 

  

Node* insert(Node* node, int key) 

    / * 1. Выполнить обычное вращение BST * /

    if (node == NULL) 

        return(newNode(key)); 

  

    if (key < node->key) 

        node->left = insert(node->left, key); 

    else if (key > node->key) 

        node->right = insert(node->right, key); 

    else // Равные ключи не допускаются

        return node; 

  

    / * 2. Обновить высоту этого узла-предка * /

    node->height = 1 + max(height(node->left), 

                           height(node->right)); 

  

    / * 3. Получите коэффициент баланса этого

        узел предка, чтобы проверить,

        этот узел стал неуравновешенным * /

    int balance = getBalance(node); 

  

    // Если этот узел становится несбалансированным,

    // тогда есть 4 случая

  

    // Левый левый регистр

    if (balance > 1 && key < node->left->key) 

        return rightRotate(node); 

  

    // правый правый случай

    if (balance < -1 && key > node->right->key) 

        return leftRotate(node); 

  

    // левый правый регистр

    if (balance > 1 && key > node->left->key) 

    

        node->left = leftRotate(node->left); 

        return rightRotate(node); 

    

  

    // Правый левый регистр

    if (balance < -1 && key < node->right->key) 

    

        node->right = rightRotate(node->right); 

        return leftRotate(node); 

    

  

    / * вернуть (неизмененный) указатель узла * /

    return node; 

  
/ * Учитывая непустое двоичное дерево поиска,
вернуть узел с минимальным значением ключа
найдено в этом дереве. Обратите внимание, что весь
дерево не нужно искать. * /
Node * minValueNode(Node* node) 

    Node* current = node; 

  

    / * зациклиться, чтобы найти самый левый лист * /

    while (current->left != NULL) 

        current = current->left; 

  

    return current; 

  
// Рекурсивная функция для удаления узла
// с заданным ключом из поддерева с
// данный корень. Возвращает корень
// измененное поддерево.

Node* deleteNode(Node* root, int key) 

      

    // ШАГ 1: ВЫПОЛНИТЕ СТАНДАРТ BST DELETE

    if (root == NULL) 

        return root; 

  

    // Если удаляемый ключ меньше

    // чем ключ рута, то лежит

    // в левом поддереве

    if ( key < root->key ) 

        root->left = deleteNode(root->left, key); 

  

    // Если удаляемый ключ больше

    // чем ключ рута, то лежит

    // в правом поддереве

    else if( key > root->key ) 

        root->right = deleteNode(root->right, key); 

  

    // если ключ совпадает с ключом root, то

    // Это узел, который нужно удалить

    else

    

        // узел только с одним дочерним элементом или без него

        if( (root->left == NULL) ||

            (root->right == NULL) ) 

        

            Node *temp = root->left ? 

                         root->left : 

                         root->right; 

  

            // Нет дочернего случая

            if (temp == NULL) 

            

                temp = root; 

                root = NULL; 

            

            else // Один дочерний случай

            *root = *temp; // Копируем содержимое

                           // непустой дочерний элемент

            free(temp); 

        

        else

        

            // узел с двумя детьми: Получить порядок

            // преемник (самый маленький в правом поддереве)

            Node* temp = minValueNode(root->right); 

  

            // Копируем преемника

            // данные в этот узел

            root->key = temp->key; 

  

            // Удалить наследник преемника

            root->right = deleteNode(root->right, 

                                     temp->key); 

        

    

  

    // Если у дерева был только один узел

    // затем возвращаем

    if (root == NULL) 

    return root; 

  

    // ШАГ 2: ОБНОВЛЕНИЕ ВЫСОТЫ ТЕКУЩЕГО УЗЛА

    root->height = 1 + max(height(root->left), 

                           height(root->right)); 

  

    // ШАГ 3: ПОЛУЧИТЕ ФАКТОР БАЛАНСА

    // ЭТО УЗЕЛ (чтобы проверить,

    // узел стал несбалансированным)

    int balance = getBalance(root); 

  

    // Если этот узел становится несбалансированным,

    // тогда есть 4 случая

  

    // Левый левый регистр

    if (balance > 1 && 

        getBalance(root->left) >= 0) 

        return rightRotate(root); 

  

    // левый правый регистр

    if (balance > 1 && 

        getBalance(root->left) < 0) 

    

        root->left = leftRotate(root->left); 

        return rightRotate(root); 

    

  

    // правый правый случай

    if (balance < -1 && 

        getBalance(root->right) <= 0) 

        return leftRotate(root); 

  

    // Правый левый регистр

    if (balance < -1 && 

        getBalance(root->right) > 0) 

    

        root->right = rightRotate(root->right); 

        return leftRotate(root); 

    

  

    return root; 

  
// Утилита для печати предзаказа
// обход дерева.
// Функция также печатает высоту
// каждого узла

void preOrder(Node *root) 

    if(root != NULL) 

    

        cout << root->key << " "

        preOrder(root->left); 

        preOrder(root->right); 

    

  
// Код драйвера

int main() 


Node *root = NULL; 

  

    / * Построение дерева дано в

    приведенная выше цифра *

    root = insert(root, 9); 

    root = insert(root, 5); 

    root = insert(root, 10); 

    root = insert(root, 0); 

    root = insert(root, 6); 

    root = insert(root, 11); 

    root = insert(root, -1); 

    root = insert(root, 1); 

    root = insert(root, 2); 

  

    / * Построенное дерево AVL будет

            9

        / /

        1 10

        ///

    0 5 11

    ///

    -1 2 6

    * /

  

    cout << "Preorder traversal of the "

            "constructed AVL tree is \n"

    preOrder(root); 

  

    root = deleteNode(root, 10); 

  

    / * Дерево AVL после удаления 10

            1

        / /

        0 9

        ///

    -1 5 11

        / /

        2 6

    * /

  

    cout << "\nPreorder traversal after"

         << " deletion of 10 \n"

    preOrder(root); 

  

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// C программа для удаления узла из дерева AVL
#include<stdio.h>
#include<stdlib.h>

  
// Узел дерева AVL

struct Node

{

    int key;

    struct Node *left;

    struct Node *right;

    int height;

};

  
// Вспомогательная функция для получения максимум двух целых

int max(int a, int b);

  
// Вспомогательная функция для получения высоты дерева

int height(struct Node *N)

{

    if (N == NULL)

        return 0;

    return N->height;

}

  
// Вспомогательная функция для получения максимум двух целых

int max(int a, int b)

{

    return (a > b)? a : b;

}

  
/ * Вспомогательная функция, которая выделяет новый узел с данным ключом и

    NULL левый и правый указатели. * /

struct Node* newNode(int key)

{

    struct Node* node = (struct Node*)

                        malloc(sizeof(struct Node));

    node->key   = key;

    node->left   = NULL;

    node->right  = NULL;

    node->height = 1;  // новый узел изначально добавляется в лист

    return(node);

}

  
// Полезная функция для правого поворота поддерева с корнем у
// Смотрите диаграмму, приведенную выше.

struct Node *rightRotate(struct Node *y)

{

    struct Node *x = y->left;

    struct Node *T2 = x->right;

  

    // Выполнить вращение

    x->right = y;

    y->left = T2;

  

    // Обновление высоты

    y->height = max(height(y->left), height(y->right))+1;

    x->height = max(height(x->left), height(x->right))+1;

  

    // Возвращаем новый корень

    return x;

}

  
// Вспомогательная функция левого поворота поддерева с корнем x
// Смотрите диаграмму, приведенную выше.

struct Node *leftRotate(struct Node *x)

{

    struct Node *y = x->right;

    struct Node *T2 = y->left;

  

    // Выполнить вращение

    y->left = x;

    x->right = T2;

  

    // Обновление высоты

    x->height = max(height(x->left), height(x->right))+1;

    y->height = max(height(y->left), height(y->right))+1;

  

    // Возвращаем новый корень

    return y;

}

  
// Получить коэффициент баланса узла N

int getBalance(struct Node *N)

{

    if (N == NULL)

        return 0;

    return height(N->left) - height(N->right);

}

  

struct Node* insert(struct Node* node, int key)

{

    / * 1. Выполнить обычное вращение BST * /

    if (node == NULL)

        return(newNode(key));

  

    if (key < node->key)

        node->left  = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);

    else // Равные ключи не допускаются

        return node;

  

    / * 2. Обновить высоту этого узла-предка * /

    node->height = 1 + max(height(node->left),

                           height(node->right));

  

    / * 3. Получите фактор баланса этого предка

          узел, чтобы проверить, стал ли этот узел

          несбалансированный * /

    int balance = getBalance(node);

  

    // Если этот узел становится несбалансированным, то есть 4 случая

  

    // Левый левый регистр

    if (balance > 1 && key < node->left->key)

        return rightRotate(node);

  

    // правый правый случай

    if (balance < -1 && key > node->right->key)

        return leftRotate(node);

  

    // левый правый регистр

    if (balance > 1 && key > node->left->key)

    {

        node->left =  leftRotate(node->left);

        return rightRotate(node);

    }

  

    // Правый левый регистр

    if (balance < -1 && key < node->right->key)

    {

        node->right = rightRotate(node->right);

        return leftRotate(node);

    }

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

  
/ * Если дано непустое двоичное дерево поиска, вернуть

   узел с минимальным значением ключа найден в этом дереве.

   Обратите внимание, что все дерево не должно быть

   поиск. * /

struct Node * minValueNode(struct Node* node)

{

    struct Node* current = node;

  

    / * зациклиться, чтобы найти самый левый лист * /

    while (current->left != NULL)

        current = current->left;

  

    return current;

}

  
// Рекурсивная функция для удаления узла с заданным ключом
// из поддерева с данным корнем. Возвращает корень
// измененное поддерево.

struct Node* deleteNode(struct Node* root, int key)

{

    // ШАГ 1: ВЫПОЛНИТЕ СТАНДАРТ BST DELETE

  

    if (root == NULL)

        return root;

  

    // Если удаляемый ключ меньше чем

    // ключ root, тогда он лежит в левом поддереве

    if ( key < root->key )

        root->left = deleteNode(root->left, key);

  

    // Если удаляемый ключ больше чем

    // ключ root, то он лежит в правом поддереве

    else if( key > root->key )

        root->right = deleteNode(root->right, key);

  

    // если ключ совпадает с ключом root, то это

    // удаляемый узел

    else

    {

        // узел только с одним дочерним элементом или без него

        if( (root->left == NULL) || (root->right == NULL) )

        {

            struct Node *temp = root->left ? root->left :

                                             root->right;

  

            // Нет дочернего случая

            if (temp == NULL)

            {

                temp = root;

                root = NULL;

            }

            else // Один дочерний случай

             *root = *temp; // Копируем содержимое

                            // непустой дочерний элемент

            free(temp);

        }

        else

        {

            // узел с двумя детьми: Получить порядок

            // преемник (самый маленький в правом поддереве)

            struct Node* temp = minValueNode(root->right);

  

            // Копируем данные преемника inorder в этот узел

            root->key = temp->key;

  

            // Удалить наследник преемника

            root->right = deleteNode(root->right, temp->key);

        }

    }

  

    // Если у дерева был только один узел, возвращаем

    if (root == NULL)

      return root;

  

    // ШАГ 2: ОБНОВЛЕНИЕ ВЫСОТЫ ТЕКУЩЕГО УЗЛА

    root->height = 1 + max(height(root->left),

                           height(root->right));

  

    // ШАГ 3: ПОЛУЧИТЕ ФАКТОР БАЛАНСА ЭТОГО УЗЛА (для

    // проверить, не стал ли этот узел несбалансированным)

    int balance = getBalance(root);

  

    // Если этот узел становится несбалансированным, то есть 4 случая

  

    // Левый левый регистр

    if (balance > 1 && getBalance(root->left) >= 0)

        return rightRotate(root);

  

    // левый правый регистр

    if (balance > 1 && getBalance(root->left) < 0)

    {

        root->left =  leftRotate(root->left);

        return rightRotate(root);

    }

  

    // правый правый случай

    if (balance < -1 && getBalance(root->right) <= 0)

        return leftRotate(root);

  

    // Правый левый регистр

    if (balance < -1 && getBalance(root->right) > 0)

    {

        root->right = rightRotate(root->right);

        return leftRotate(root);

    }

  

    return root;

}

  
// Полезная функция для печати предзаказа прохождения
// дерево.
// Функция также печатает высоту каждого узла

void preOrder(struct Node *root)

{

    if(root != NULL)

    {

        printf("%d ", root->key);

        preOrder(root->left);

        preOrder(root->right);

    }

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

  struct Node *root = NULL;

  

  / * Построение дерева приведено на рисунке выше * /

    root = insert(root, 9);

    root = insert(root, 5);

    root = insert(root, 10);

    root = insert(root, 0);

    root = insert(root, 6);

    root = insert(root, 11);

    root = insert(root, -1);

    root = insert(root, 1);

    root = insert(root, 2);

  

    / * Построенное дерево AVL будет

            9

           / /

          1 10

        ///

       0 5 11

      ///

     -1 2 6

    * /

  

    printf("Preorder traversal of the constructed AVL "

           "tree is \n");

    preOrder(root);

  

    root = deleteNode(root, 10);

  

    / * Дерево AVL после удаления 10

            1

           / /

          0 9

        ///

       -1 5 11

           / /

          2 6

    * /

  

    printf("\nPreorder traversal after deletion of 10 \n");

    preOrder(root);

  

    return 0;

}

Джава

// Java программа для удаления в AVL Tree

  

class Node 

    int key, height; 

    Node left, right; 

  

    Node(int d) 

    

        key = d; 

        height = 1

    

  

class AVLTree 

    Node root; 

  

    // Вспомогательная функция для получения высоты дерева

    int height(Node N) 

    

        if (N == null

            return 0

        return N.height; 

    

  

    // Вспомогательная функция для получения максимум двух целых

    int max(int a, int b) 

    

        return (a > b) ? a : b; 

    

  

    // Полезная функция для правого поворота поддерева с корнем у

    // Смотрите диаграмму, приведенную выше.

    Node rightRotate(Node y) 

    

        Node x = y.left; 

        Node T2 = x.right; 

  

        // Выполнить вращение

        x.right = y; 

        y.left = T2; 

  

        // Обновление высоты

        y.height = max(height(y.left), height(y.right)) + 1

        x.height = max(height(x.left), height(x.right)) + 1

  

        // Возвращаем новый корень

        return x; 

    

  

    // Вспомогательная функция левого поворота поддерева с корнем x

    // Смотрите диаграмму, приведенную выше.

    Node leftRotate(Node x) 

    

        Node y = x.right; 

        Node T2 = y.left; 

  

        // Выполнить вращение

        y.left = x; 

        x.right = T2; 

  

        // Обновление высоты

        x.height = max(height(x.left), height(x.right)) + 1

        y.height = max(height(y.left), height(y.right)) + 1

  

        // Возвращаем новый корень

        return y; 

    

  

    // Получить коэффициент баланса узла N

    int getBalance(Node N) 

    

        if (N == null

            return 0

        return height(N.left) - height(N.right); 

    

  

    Node insert(Node node, int key) 

    

        / * 1. Выполнить обычное вращение BST * /

        if (node == null

            return (new Node(key)); 

  

        if (key < node.key) 

            node.left = insert(node.left, key); 

        else if (key > node.key) 

            node.right = insert(node.right, key); 

        else // Равные ключи не допускаются

            return node; 

  

        / * 2. Обновить высоту этого узла-предка * /

        node.height = 1 + max(height(node.left), 

                            height(node.right)); 

  

        / * 3. Получите фактор баланса этого предка

        узел, чтобы проверить, стал ли этот узел

        Wunbalanced * /

        int balance = getBalance(node); 

  

        // Если этот узел становится несбалансированным, то

        // есть 4 случая Left Left Case

        if (balance > 1 && key < node.left.key) 

            return rightRotate(node); 

  

        // правый правый случай

        if (balance < -1 && key > node.right.key) 

            return leftRotate(node); 

  

        // левый правый регистр

        if (balance > 1 && key > node.left.key) 

        

            node.left = leftRotate(node.left); 

            return rightRotate(node); 

        

  

        // Правый левый регистр

        if (balance < -1 && key < node.right.key) 

        

            node.right = rightRotate(node.right); 

            return leftRotate(node); 

        

  

        / * вернуть (неизмененный) указатель узла * /

        return node; 

    

  

    / * Если дано непустое двоичное дерево поиска, вернуть

    узел с минимальным значением ключа найден в этом дереве.

    Обратите внимание, что все дерево не должно быть

    поиск. * /

    Node minValueNode(Node node) 

    

        Node current = node; 

  

        / * зациклиться, чтобы найти самый левый лист * /

        while (current.left != null

        current = current.left; 

  

        return current; 

    

  

    Node deleteNode(Node root, int key) 

    

        // ШАГ 1: ВЫПОЛНИТЕ СТАНДАРТ BST DELETE

        if (root == null

            return root; 

  

        // Если удаляемый ключ меньше чем

        // ключ корня, то он лежит в левом поддереве

        if (key < root.key) 

            root.left = deleteNode(root.left, key); 

  

        // Если удаляемый ключ больше чем

        // ключ root, то он лежит в правом поддереве

        else if (key > root.key) 

            root.right = deleteNode(root.right, key); 

  

        // если ключ совпадает с ключом root, то это узел

        // быть удаленным

        else

        

  

            // узел только с одним дочерним элементом или без него

            if ((root.left == null) || (root.right == null)) 

            

                Node temp = null

                if (temp == root.left) 

                    temp = root.right; 

                else

                    temp = root.left; 

  

                // Нет дочернего случая

                if (temp == null

                

                    temp = root; 

                    root = null

                

                else // Один дочерний случай

                    root = temp; // Копируем содержимое

                                // непустой дочерний элемент

            

            else

            

  

                // узел с двумя детьми: Получить порядок

                // преемник (самый маленький в правом поддереве)

                Node temp = minValueNode(root.right); 

  

                // Копируем данные преемника inorder в этот узел

                root.key = temp.key; 

  

                // Удалить наследник преемника

                root.right = deleteNode(root.right, temp.key); 

            

        

  

        // Если у дерева был только один узел, возвращаем

        if (root == null

            return root; 

  

        // ШАГ 2: ОБНОВЛЕНИЕ ВЫСОТЫ ТЕКУЩЕГО УЗЛА

        root.height = max(height(root.left), height(root.right)) + 1

  

        // ШАГ 3: ПОЛУЧИТЕ ФАКТОР БАЛАНСА ЭТОГО УЗЛА (чтобы проверить,

        // этот узел стал несбалансированным)

        int balance = getBalance(root); 

  

        // Если этот узел становится несбалансированным, то есть 4 случая

        // Левый левый регистр

        if (balance > 1 && getBalance(root.left) >= 0

            return rightRotate(root); 

  

        // левый правый регистр

        if (balance > 1 && getBalance(root.left) < 0

        

            root.left = leftRotate(root.left); 

            return rightRotate(root); 

        

  

        // правый правый случай

        if (balance < -1 && getBalance(root.right) <= 0

            return leftRotate(root); 

  

        // Правый левый регистр

        if (balance < -1 && getBalance(root.right) > 0

        

            root.right = rightRotate(root.right); 

            return leftRotate(root); 

        

  

        return root; 

    

  

    // Полезная функция для печати предзаказа прохождения

    // дерево. Функция также печатает высоту каждого

    // узел

    void preOrder(Node node) 

    

        if (node != null

        

            System.out.print(node.key + " "); 

            preOrder(node.left); 

            preOrder(node.right); 

        

    

  

    public static void main(String[] args) 

    

        AVLTree tree = new AVLTree(); 

  

        / * Построение дерева приведено на рисунке выше * /

        tree.root = tree.insert(tree.root, 9); 

        tree.root = tree.insert(tree.root, 5); 

        tree.root = tree.insert(tree.root, 10); 

        tree.root = tree.insert(tree.root, 0); 

        tree.root = tree.insert(tree.root, 6); 

        tree.root = tree.insert(tree.root, 11); 

        tree.root = tree.insert(tree.root, -1); 

        tree.root = tree.insert(tree.root, 1); 

        tree.root = tree.insert(tree.root, 2); 

  

        / * Построенное дерево AVL будет

        9

        / /

        1 10

        ///

        0 5 11

        ///

        -1 2 6

        * /

        System.out.println("Preorder traversal of "

                            "constructed tree is : "); 

        tree.preOrder(tree.root); 

  

        tree.root = tree.deleteNode(tree.root, 10); 

  

        / * Дерево AVL после удаления 10

        1

        / /

        0 9

        ///

        -1 5 11

        / /

        2 6

        * /

        System.out.println(""); 

        System.out.println("Preorder traversal after "

                        "deletion of 10 :"); 

        tree.preOrder(tree.root); 

    

  
// Этот код предоставлен Mayank Jaiswal

python3

# Python код для удаления узла в дереве AVL
# Общий класс узлов дерева

class TreeNode(object):

    def __init__(self, val):

        self.val = val

        self.left = None

        self.right = None

        self.height = 1

  
# AVL класс дерева, который поддерживает вставку,
# операции удаления

class AVL_Tree(object):

  

    def insert(self, root, key):

          

        # Шаг 1 - Выполнить нормальный BST

        if not root:

            return TreeNode(key)

        elif key < root.val:

            root.left = self.insert(root.left, key)

        else:

            root.right = self.insert(root.right, key)

  

        # Шаг 2 - Обновите высоту

        # узел предка

        root.height = 1 + max(self.getHeight(root.left),

                          self.getHeight(root.right))

  

        # Шаг 3 - Получить коэффициент баланса

        balance = self.getBalance(root)

  

        # Шаг 4 - Если узел не сбалансирован,

        # тогда попробуйте 4 случая

        # Случай 1 - Левый Левый

        if balance > 1 and key < root.left.val:

            return self.rightRotate(root)

  

        # Случай 2 - Право Право

        if balance < -1 and key > root.right.val:

            return self.leftRotate(root)

  

        # Случай 3 - Левый Правый

        if balance > 1 and key > root.left.val:

            root.left = self.leftRotate(root.left)

            return self.rightRotate(root)

  

        # Случай 4 - Справа налево

        if balance < -1 and key < root.right.val:

            root.right = self.rightRotate(root.right)

            return self.leftRotate(root)

  

        return root

  

    # Рекурсивная функция для удаления узла с

    # данный ключ из поддерева с данным корнем.

    # Возвращает корень модифицированного поддерева.

    def delete(self, root, key):

  

        # Шаг 1 - Выполнить стандартное удаление BST

        if not root:

            return root

  

        elif key < root.val:

            root.left = self.delete(root.left, key)

  

        elif key > root.val:

            root.right = self.delete(root.right, key)

  

        else:

            if root.left is None:

                temp = root.right

                root = None

                return temp

  

            elif root.right is None:

                temp = root.left

                root = None

                return temp

  

            temp = self.getMinValueNode(root.right)

            root.val = temp.val

            root.right = self.delete(root.right,

                                      temp.val)

  

        # Если дерево имеет только один узел,

        # просто верни его

        if root is None:

            return root

  

        # Шаг 2 - Обновите высоту

        # узел предка

        root.height = 1 + max(self.getHeight(root.left),

                            self.getHeight(root.right))

  

        # Шаг 3 - Получить коэффициент баланса

        balance = self.getBalance(root)

  

        # Шаг 4 - Если узел не сбалансирован,

        # тогда попробуйте 4 случая

        # Случай 1 - Левый Левый

        if balance > 1 and self.getBalance(root.left) >= 0:

            return self.rightRotate(root)

  

        # Случай 2 - Право Право

        if balance < -1 and self.getBalance(root.right) <= 0:

            return self.leftRotate(root)

  

        # Случай 3 - Левый Правый

        if balance > 1 and self.getBalance(root.left) < 0:

            root.left = self.leftRotate(root.left)

            return self.rightRotate(root)

  

        # Случай 4 - Справа налево

        if balance < -1 and self.getBalance(root.right) > 0:

            root.right = self.rightRotate(root.right)

            return self.leftRotate(root)

  

        return root

  

    def leftRotate(self, z):

  

        y = z.right

        T2 = y.left

  

        # Выполнить вращение

        y.left = z

        z.right = T2

  

        # Обновление высоты

        z.height = 1 + max(self.getHeight(z.left), 

                         self.getHeight(z.right))

        y.height = 1 + max(self.getHeight(y.left), 

                         self.getHeight(y.right))

  

        # Вернуть новый корень

        return y

  

    def rightRotate(self, z):

  

        y = z.left

        T3 = y.right

  

        # Выполнить вращение

        y.right = z

        z.left = T3

  

        # Обновление высоты

        z.height = 1 + max(self.getHeight(z.left),

                          self.getHeight(z.right))

        y.height = 1 + max(self.getHeight(y.left),

                          self.getHeight(y.right))

  

        # Вернуть новый корень

        return y

  

    def getHeight(self, root):

        if not root:

            return 0

  

        return root.height

  

    def getBalance(self, root):

        if not root:

            return 0

  

        return self.getHeight(root.left) - self.getHeight(root.right)

  

    def getMinValueNode(self, root):

        if root is None or root.left is None:

            return root

  

        return self.getMinValueNode(root.left)

  

    def preOrder(self, root):

  

        if not root:

            return

  

        print("{0} ".format(root.val), end="")

        self.preOrder(root.left)

        self.preOrder(root.right)

  

  

myTree = AVL_Tree()

root = None

nums = [9, 5, 10, 0, 6, 11, -1, 1, 2]

  

for num in nums:

    root = myTree.insert(root, num)

  
# Предзаказ Обход

print("Preorder Traversal after insertion -")

myTree.preOrder(root)

print()

  
# Удалять

key = 10

root = myTree.delete(root, key)

  
# Предзаказ Обход

print("Preorder Traversal after deletion -")

myTree.preOrder(root)

print()

  
# Этот код предоставлен Ajitesh Pathak

C #

// C # программа для удаления в AVL Tree

using System;

  

public class Node 

    public int key, height; 

    public Node left, right; 

  

    public Node(int d) 

    

        key = d; 

        height = 1; 

    

  

public class AVLTree 

    Node root; 

  

    // Вспомогательная функция для получения высоты дерева

    int height(Node N) 

    

        if (N == null

            return 0; 

        return N.height; 

    

  

    // Функция полезности для

    // получить максимум два целых числа

    int max(int a, int b) 

    

        return (a > b) ? a : b; 

    

  

    // Функция полезности справа

    // вращаем поддерево с корнем у

    // Смотрите диаграмму, приведенную выше.

    Node rightRotate(Node y) 

    

        Node x = y.left; 

        Node T2 = x.right; 

  

        // Выполнить вращение

        x.right = y; 

        y.left = T2; 

  

        // Обновление высоты

        y.height = max(height(y.left), height(y.right)) + 1; 

        x.height = max(height(x.left), height(x.right)) + 1; 

  

        // Возвращаем новый корень

        return x; 

    

  

    // Служебная функция слева

    // вращаем поддерево с корнем x

    // Смотрите диаграмму, приведенную выше.

    Node leftRotate(Node x) 

    

        Node y = x.right; 

        Node T2 = y.left; 

  

        // Выполнить вращение

        y.left = x; 

        x.right = T2; 

  

        // Обновление высоты

        x.height = max(height(x.left), height(x.right)) + 1; 

        y.height = max(height(y.left), height(y.right)) + 1; 

  

        // Возвращаем новый корень

        return y; 

    

  

    // Получить коэффициент баланса узла N

    int getBalance(Node N) 

    

        if (N == null

            return 0; 

        return height(N.left) - height(N.right); 

    

  

    Node insert(Node node, int key) 

    

        / * 1. Выполнить обычное вращение BST * /

        if (node == null

            return (new Node(key)); 

  

        if (key < node.key) 

            node.left = insert(node.left, key); 

        else if (key > node.key) 

            node.right = insert(node.right, key); 

        else // Равные ключи не допускаются

            return node; 

  

        / * 2. Обновить высоту этого узла-предка * /

        node.height = 1 + max(height(node.left), 

                            height(node.right)); 

  

        / * 3. Получите фактор баланса этого предка

        узел, чтобы проверить, стал ли этот узел

        Wunbalanced * /

        int balance = getBalance(node); 

  

        // Если этот узел становится несбалансированным, то

        // есть 4 случая Left Left Case

        if (balance > 1 && key < node.left.key) 

            return rightRotate(node); 

  

        // правый правый случай

        if (balance < -1 && key > node.right.key) 

            return leftRotate(node); 

  

        // левый правый регистр

        if (balance > 1 && key > node.left.key) 

        

            node.left = leftRotate(node.left); 

            return rightRotate(node); 

        

  

        // Правый левый регистр

        if (balance < -1 && key < node.right.key) 

        

            node.right = rightRotate(node.right); 

            return leftRotate(node); 

        

  

        / * вернуть (неизмененный) указатель узла * /

        return node; 

    

  

    / * Если дано непустое двоичное дерево поиска, вернуть

    узел с минимальным значением ключа найден в этом дереве.

    Обратите внимание, что все дерево не должно быть

    поиск. * /

    Node minValueNode(Node node) 

    

        Node current = node; 

  

        / * зациклиться, чтобы найти самый левый лист * /

        while (current.left != null

        current = current.left; 

  

        return current; 

    

  

    Node deleteNode(Node root, int key) 

    

        // ШАГ 1: ВЫПОЛНИТЕ СТАНДАРТ BST DELETE

        if (root == null

            return root; 

  

        // Если удаляемый ключ меньше чем

        // ключ корня, то он лежит в левом поддереве

        if (key < root.key) 

            root.left = deleteNode(root.left, key); 

  

        // Если удаляемый ключ больше чем

        // ключ root, то он лежит в правом поддереве

        else if (key > root.key) 

            root.right = deleteNode(root.right, key); 

  

        // если ключ совпадает с ключом root, то это узел

        // быть удаленным

        else

        

  

            // узел только с одним дочерним элементом или без него

            if ((root.left == null) || (root.right == null)) 

            

                Node temp = null

                if (temp == root.left) 

                    temp = root.right; 

                else

                    temp = root.left; 

  

                // Нет дочернего случая

                if (temp == null

                

                    temp = root; 

                    root = null

                

                else // Один дочерний случай

                    root = temp; // Копируем содержимое

                                // непустой дочерний элемент

            

            else

            

  

                // узел с двумя детьми: Получить порядок

                // преемник (самый маленький в правом поддереве)

                Node temp = minValueNode(root.right); 

  

                // Копируем данные преемника inorder в этот узел

                root.key = temp.key; 

  

                // Удалить наследник преемника

                root.right = deleteNode(root.right, temp.key); 

            

        

  

        // Если у дерева был только один узел, возвращаем

        if (root == null

            return root; 

  

        // ШАГ 2: ОБНОВЛЕНИЕ ВЫСОТЫ ТЕКУЩЕГО УЗЛА

        root.height = max(height(root.left), 

                    height(root.right)) + 1; 

  

        // ШАГ 3: ПОЛУЧИТЕ ФАКТОР БАЛАНСА

        // ЭТОГО УЗЛА (чтобы проверить,

        // этот узел стал несбалансированным)

        int balance = getBalance(root); 

  

        // Если этот узел становится несбалансированным,

        // тогда есть 4 случая

        // Левый левый регистр

        if (balance > 1 && getBalance(root.left) >= 0) 

            return rightRotate(root); 

  

        // левый правый регистр

        if (balance > 1 && getBalance(root.left) < 0) 

        

            root.left = leftRotate(root.left); 

            return rightRotate(root); 

        

  

        // правый правый случай

        if (balance < -1 && getBalance(root.right) <= 0) 

            return leftRotate(root); 

  

        // Правый левый регистр

        if (balance < -1 && getBalance(root.right) > 0) 

        

            root.right = rightRotate(root.right); 

            return leftRotate(root); 

        

  

        return root; 

    

  

    // Полезная функция для печати предзаказа прохождения

    // дерево. Функция также печатает высоту каждого

    // узел

    void preOrder(Node node) 

    

        if (node != null

        

            Console.Write(node.key + " "); 

            preOrder(node.left); 

            preOrder(node.right); 

        

    

  

    // Код драйвера

    public static void Main() 

    

        AVLTree tree = new AVLTree(); 

  

        / * Построение дерева приведено на рисунке выше * /

        tree.root = tree.insert(tree.root, 9); 

        tree.root = tree.insert(tree.root, 5); 

        tree.root = tree.insert(tree.root, 10); 

        tree.root = tree.insert(tree.root, 0); 

        tree.root = tree.insert(tree.root, 6); 

        tree.root = tree.insert(tree.root, 11); 

        tree.root = tree.insert(tree.root, -1); 

        tree.root = tree.insert(tree.root, 1); 

        tree.root = tree.insert(tree.root, 2); 

  

        / * Построенное дерево AVL будет

        9

        / /

        1 10

        ///

        0 5 11

        ///

        -1 2 6

        * /

        Console.WriteLine("Preorder traversal of "

                            "constructed tree is : "); 

        tree.preOrder(tree.root); 

  

        tree.root = tree.deleteNode(tree.root, 10); 

  

        / * Дерево AVL после удаления 10

        1

        / /

        0 9

        ///

        -1 5 11

        / /

        2 6

        * /

        Console.WriteLine(""); 

        Console.WriteLine("Preorder traversal after "

                        "deletion of 10 :"); 

        tree.preOrder(tree.root); 

    

}

  
/ * Этот код предоставлен PrinciRaj1992 * /

Выход:

Preorder traversal of the constructed AVL tree is 
9 1 0 -1 5 2 6 10 11 
Preorder traversal after deletion of 10 
1 0 -1 9 5 2 6 11 

Сложность времени: Операции вращения (вращение влево и вправо) занимают постоянное время, так как там меняется только несколько указателей. Обновление высоты и получение коэффициента баланса также требуют постоянного времени. Таким образом, временная сложность удаления AVL остается такой же, как удаление BST, которое равно O (h), где h — высота дерева. Поскольку дерево AVL сбалансировано, высота равна O (Logn). Таким образом, временная сложность удаления AVL равна O (Log n).

Ссылки:
https://www.cs.purdue.edu/homes/ayg/CS251/slides/chap7b.pdf
Видеолекция IITD по вставке и удалению дерева AVL

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

AVL Tree | Набор 2 (удаление)

0.00 (0%) 0 votes