Рубрики

AVL Tree | Набор 1 (вставка)

Дерево AVL — это самобалансирующееся дерево двоичного поиска (BST), в котором разница между высотами левого и правого поддеревьев не может превышать одного для всех узлов.

Дерево примеров, которое является деревом AVL

Вышеупомянутое дерево — AVL, потому что различия между высотами левого и правого поддеревьев для каждого узла меньше или равны 1.

Дерево примеров, которое НЕ является деревом AVL

Вышеупомянутое дерево не является AVL, потому что различия между высотой левого и правого поддеревьев для 8 и 18 больше 1.

Почему AVL Деревья?
Большинство операций BST (например, поиск, максимальное, минимальное, вставка, удаление и т. Д.) Занимают время O (h), где h — высота BST. Стоимость этих операций может стать O (n) для перекошенного двоичного дерева. Если мы удостоверимся, что высота дерева остается O (Logn) после каждой вставки и удаления, то мы можем гарантировать верхнюю границу O (Logn) для всех этих операций. Высота дерева AVL всегда равна O (Logn), где n — количество узлов в дереве (см. Эту видео-лекцию для доказательства).

вставка
Чтобы убедиться, что данное дерево остается 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 the left side) or x (on 
the 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.

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

Ниже приведены операции, которые должны быть выполнены в вышеупомянутых 4 случаях. Во всех случаях нам нужно только повторно сбалансировать поддерево с корнем 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

Примеры вставки:

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

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 // Равные ключи не разрешены в BST

        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; 

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

void preOrder(Node *root) 

    if(root != NULL) 

    

        cout << root->key << " "

        preOrder(root->left); 

        preOrder(root->right); 

    

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

int main() 

    Node *root = NULL; 

      

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

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

    root = insert(root, 10); 

    root = insert(root, 20); 

    root = insert(root, 30); 

    root = insert(root, 40); 

    root = insert(root, 50); 

    root = insert(root, 25); 

      

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

                30

            / /

            20 40

            ///

        10 25 50

    * /

    cout << "Preorder traversal of the "

            "constructed AVL tree is \n"

    preOrder(root); 

      

    return 0; 

  
// Этот код предоставлен
// ратбхупендра

С

// 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 // Равные ключи не разрешены в BST

        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;

}

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

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, 10);

  root = insert(root, 20);

  root = insert(root, 30);

  root = insert(root, 40);

  root = insert(root, 50);

  root = insert(root, 25);

  

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

            30

           / /

         20 40

        ///

       10 25 50

  * /

  

  printf("Preorder traversal of the constructed AVL"

         " tree is \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. Получите фактор баланса этого предка

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

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

        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;

    }

  

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

    // дерева.

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

    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, 10);

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

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

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

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

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

  

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

             30

            / /

          20 40

         ///

        10 25 50

        * /

        System.out.println("Preorder traversal" +

                        " of constructed tree is : ");

        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 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 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

  

root = myTree.insert(root, 10)

root = myTree.insert(root, 20)

root = myTree.insert(root, 30)

root = myTree.insert(root, 40)

root = myTree.insert(root, 50)

root = myTree.insert(root, 25)

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

            30

           / /

         20 40

        ///

       10 25 50 "" "

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

print("Preorder traversal of the",

      "constructed AVL tree is")

myTree.preOrder(root)

print()

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

C #

// C # программа для вставки в AVL Tree

using System;

  

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. Получите фактор баланса этого предка

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

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

        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; 

    

  

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

    // дерева.

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

    void preOrder(Node node) 

    

        if (node != null)

        

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

            preOrder(node.left); 

            preOrder(node.right); 

        

    

  

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

    public static void Main(String[] args) 

    

        AVLTree tree = new AVLTree(); 

  

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

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

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

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

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

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

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

  

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

            30

            / /

        20 40

        ///

        10 25 50

        * /

        Console.Write("Preorder traversal"

                        " of constructed tree is : "); 

        tree.preOrder(tree.root); 

    

  
// Этот код был добавлен
// by PrinciRaj1992


Выход:

  Preorder traversal of the constructed AVL tree is
  30 20 10 25 40 50

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

Сравнение с красным черным деревом
Дерево AVL и другие деревья с самобалансирующимся поиском, такие как Red Black, полезны для выполнения всех основных операций за O (log n). Деревья AVL более сбалансированы по сравнению с красно-черными деревьями, но они могут вызвать большее вращение при вставке и удалении. Так что, если ваше приложение включает в себя много частых вставок и удалений, тогда предпочтительны красно-чёрные деревья. И если вставки и удаления происходят реже, а поиск — более частая операция, то дерево AVL должно быть предпочтительнее, чем красное черное дерево .

Ниже приведен пост для удаления.
AVL Tree | Набор 2 (удаление)

Ниже приведены некоторые сообщения, в которых используются самобалансирующиеся деревья поиска.

Медиана в потоке целых чисел (работающих целых чисел)
Максимум всех подмассивов размера k
Подсчитайте меньшие элементы на правой стороне

Ссылки:
IITD Видео Лекция по AVL Tree Введение
Видеолекция IITD по вставке и удалению дерева AVL

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

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

AVL Tree | Набор 1 (вставка)

0.00 (0%) 0 votes