# AVL-дерево *

В главе "Двоичное дерево поиска" мы упоминали, что после многократных операций вставки и удаления двоичное дерево поиска может выродиться в список. В этом случае временная сложность всех операций ухудшится с $O(\log n)$ до $O(n)$.

Как показано на рисунке ниже, после двух операций удаления узлов это двоичное дерево поиска выродится в список.

![Вырождение AVL-дерева после удаления узла](../assets/avltree_degradation_from_removing_node.png)

Например, в идеальном двоичном дереве, показанном на рисунке ниже, после вставки двух узлов дерево сильно наклонится влево, и временная сложность операции поиска также ухудшится.

![Вырождение AVL-дерева после вставки узла](../assets/avltree_degradation_from_inserting_node.png)

В 1962 году Г. М. Адельсон-Вельский и Е. М. Ландис в статье "An algorithm for the organization of information" предложили <u>AVL-дерево</u>. В статье подробно описана серия операций, обеспечивающих, что после непрерывного добавления и удаления узлов AVL-дерево не вырождается, благодаря чему временная сложность различных операций сохраняется на уровне $O(\log n)$. Другими словами, в сценариях, требующих частых операций вставки, удаления, поиска и изменения, AVL-дерево всегда может поддерживать высокую эффективность операций с данными и имеет большую практическую ценность.

## Основные термины AVL-дерева

AVL-дерево является одновременно двоичным деревом поиска и сбалансированным двоичным деревом, удовлетворяя свойствам обоих типов двоичных деревьев, поэтому является <u>сбалансированным двоичным деревом поиска (balanced binary search tree)</u>.

### Высота узла

Поскольку операции с AVL-деревом требуют получения высоты узла, необходимо добавить переменную `height` в класс узла:

=== "Python"

    ```python title=""
    class TreeNode:
        """Класс узла AVL-дерева"""
        def __init__(self, val: int):
            self.val: int = val                 # Значение узла
            self.height: int = 0                # Высота узла
            self.left: TreeNode | None = None   # Ссылка на левый дочерний узел
            self.right: TreeNode | None = None  # Ссылка на правый дочерний узел
    ```

=== "C++"

    ```cpp title=""
    /* Класс узла AVL-дерева */
    struct TreeNode {
        int val{};          // Значение узла
        int height = 0;     // Высота узла
        TreeNode *left{};   // Левый дочерний узел
        TreeNode *right{};  // Правый дочерний узел
        TreeNode() = default;
        explicit TreeNode(int x) : val(x){}
    };
    ```

=== "Java"

    ```java title=""
    /* Класс узла AVL-дерева */
    class TreeNode {
        public int val;        // Значение узла
        public int height;     // Высота узла
        public TreeNode left;  // Левый дочерний узел
        public TreeNode right; // Правый дочерний узел
        public TreeNode(int x) { val = x; }
    }
    ```

=== "C#"

    ```csharp title=""
    /* Класс узла AVL-дерева */
    class TreeNode(int? x) {
        public int? val = x;    // Значение узла
        public int height;      // Высота узла
        public TreeNode? left;  // Ссылка на левый дочерний узел
        public TreeNode? right; // Ссылка на правый дочерний узел
    }
    ```

=== "Go"

    ```go title=""
    /* Структура узла AVL-дерева */
    type TreeNode struct {
        Val    int       // Значение узла
        Height int       // Высота узла
        Left   *TreeNode // Ссылка на левый дочерний узел
        Right  *TreeNode // Ссылка на правый дочерний узел
    }
    ```

=== "Swift"

    ```swift title=""
    /* Класс узла AVL-дерева */
    class TreeNode {
        var val: Int // Значение узла
        var height: Int // Высота узла
        var left: TreeNode? // Левый дочерний узел
        var right: TreeNode? // Правый дочерний узел

        init(x: Int) {
            val = x
            height = 0
        }
    }
    ```

=== "JS"

    ```javascript title=""
    /* Класс узла AVL-дерева */
    class TreeNode {
        val; // Значение узла
        height; // Высота узла
        left; // Указатель на левый дочерний узел
        right; // Указатель на правый дочерний узел
        constructor(val, left, right, height) {
            this.val = val === undefined ? 0 : val;
            this.height = height === undefined ? 0 : height;
            this.left = left === undefined ? null : left;
            this.right = right === undefined ? null : right;
        }
    }
    ```

=== "TS"

    ```typescript title=""
    /* Класс узла AVL-дерева */
    class TreeNode {
        val: number;            // Значение узла
        height: number;         // Высота узла
        left: TreeNode | null;  // Указатель на левый дочерний узел
        right: TreeNode | null; // Указатель на правый дочерний узел
        constructor(val?: number, height?: number, left?: TreeNode | null, right?: TreeNode | null) {
            this.val = val === undefined ? 0 : val;
            this.height = height === undefined ? 0 : height;
            this.left = left === undefined ? null : left;
            this.right = right === undefined ? null : right;
        }
    }
    ```

=== "Dart"

    ```dart title=""
    /* Класс узла AVL-дерева */
    class TreeNode {
      int val;         // Значение узла
      int height;      // Высота узла
      TreeNode? left;  // Левый дочерний узел
      TreeNode? right; // Правый дочерний узел
      TreeNode(this.val, [this.height = 0, this.left, this.right]);
    }
    ```

=== "Rust"

    ```rust title=""
    use std::rc::Rc;
    use std::cell::RefCell;

    /* Структура узла AVL-дерева */
    struct TreeNode {
        val: i32,                               // Значение узла
        height: i32,                            // Высота узла
        left: Option<Rc<RefCell<TreeNode>>>,    // Левый дочерний узел
        right: Option<Rc<RefCell<TreeNode>>>,   // Правый дочерний узел
    }

    impl TreeNode {
        /* Конструктор */
        fn new(val: i32) -> Rc<RefCell<Self>> {
            Rc::new(RefCell::new(Self {
                val,
                height: 0,
                left: None,
                right: None
            }))
        }
    }
    ```

=== "C"

    ```c title=""
    /* Структура узла AVL-дерева */
    typedef struct TreeNode {
        int val;
        int height;
        struct TreeNode *left;
        struct TreeNode *right;
    } TreeNode;

    /* Конструктор */
    TreeNode *newTreeNode(int val) {
        TreeNode *node;

        node = (TreeNode *)malloc(sizeof(TreeNode));
        node->val = val;
        node->height = 0;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
    ```

=== "Kotlin"

    ```kotlin title=""
    /* Класс узла AVL-дерева */
    class TreeNode(val _val: Int) {  // Значение узла
        val height: Int = 0          // Высота узла
        val left: TreeNode? = null   // Левый дочерний узел
        val right: TreeNode? = null  // Правый дочерний узел
    }
    ```

=== "Ruby"

    ```ruby title=""
    ### Класс узла AVL-дерева ###
    class TreeNode
      attr_accessor :val    # Значение узла
      attr_accessor :height # Высота узла
      attr_accessor :left   # Ссылка на левый дочерний узел
      attr_accessor :right  # Ссылка на правый дочерний узел

      def initialize(val)
        @val = val
        @height = 0
      end
    end
    ```

"Высота узла" — это расстояние от данного узла до самого удаленного листового узла, т. е. количество пройденных "ребер". Особо следует отметить, что высота листового узла равна $0$, а высота пустого узла равна $-1$. Мы создадим две вспомогательные функции для получения и обновления высоты узла:

```src
[file]{avl_tree}-[class]{avl_tree}-[func]{update_height}
```

### Коэффициент балансировки узла

<u>Коэффициент балансировки (balance factor)</u> узла определяется как высота левого поддерева минус высота правого поддерева, при этом коэффициент балансировки пустого узла равен $0$. Мы также инкапсулируем функцию получения коэффициента балансировки узла для удобства последующего использования:

```src
[file]{avl_tree}-[class]{avl_tree}-[func]{balance_factor}
```

!!! tip "Подсказка"

    Пусть коэффициент балансировки равен $f$, тогда коэффициент балансировки любого узла AVL-дерева удовлетворяет условию $-1 \le f \le 1$.

## Повороты AVL-дерева

Особенность AVL-дерева заключается в операции "поворота", которая позволяет восстановить баланс несбалансированного узла без нарушения порядка обхода двоичного дерева в симметричном порядке. Другими словами, **операция поворота сохраняет свойство "двоичного дерева поиска" и делает дерево снова "сбалансированным двоичным деревом"**.

Узел с абсолютным значением коэффициента балансировки $> 1$ называется "несбалансированным узлом". В зависимости от ситуации несбалансированности узла операции поворота делятся на четыре типа: правый поворот, левый поворот, сначала правый поворот затем левый поворот, сначала левый поворот затем правый поворот. Ниже подробно описаны эти операции поворота.

### Правый поворот

Как показано на рисунке ниже, под узлом указан коэффициент балансировки. Снизу вверх первый несбалансированный узел в двоичном дереве — это "узел 3". Рассмотрим поддерево с этим несбалансированным узлом в качестве корневого узла, обозначим этот узел как `node`, его левый дочерний узел как `child`, и выполним "правый поворот". После завершения правого поворота поддерево восстанавливает баланс и по-прежнему сохраняет свойство двоичного дерева поиска.

=== "<1>"
    ![Шаги операции правого поворота](../assets/avltree_right_rotate_step1.png)

=== "<2>"
    ![avltree_right_rotate_step2](../assets/avltree_right_rotate_step2.png)

=== "<3>"
    ![avltree_right_rotate_step3](../assets/avltree_right_rotate_step3.png)

=== "<4>"
    ![avltree_right_rotate_step4](../assets/avltree_right_rotate_step4.png)

Как показано на рисунке ниже, когда узел `child` имеет правый дочерний узел (обозначим его как `grand_child`), необходимо добавить один шаг в правый поворот: сделать `grand_child` левым дочерним узлом `node`.

![Операция правого поворота с grand_child](../assets/avltree_right_rotate_with_grandchild.png)

"Поворот вправо" — это образное выражение, на самом деле это реализуется путем изменения указателей узлов, код показан ниже:

```src
[file]{avl_tree}-[class]{avl_tree}-[func]{right_rotate}
```

### Левый поворот

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

![Операция левого поворота](../assets/avltree_left_rotate.png)

Аналогично, как показано на рисунке ниже, когда узел `child` имеет левый дочерний узел (обозначим его как `grand_child`), необходимо добавить один шаг в левый поворот: сделать `grand_child` правым дочерним узлом `node`.

![Операция левого поворота с grand_child](../assets/avltree_left_rotate_with_grandchild.png)

Можно заметить, что **операции правого и левого поворотов логически зеркально симметричны, и две ситуации несбалансированности, которые они решают, также симметричны**. Основываясь на симметрии, нам нужно только заменить все `left` на `right` и все `right` на `left` в коде реализации правого поворота, чтобы получить код реализации левого поворота:

```src
[file]{avl_tree}-[class]{avl_tree}-[func]{left_rotate}
```

### Сначала левый поворот, затем правый поворот

Для несбалансированного узла 3 на рисунке ниже использование только левого или правого поворота не может восстановить баланс поддерева. В этом случае необходимо сначала выполнить "левый поворот" для `child`, а затем "правый поворот" для `node`.

![Сначала левый поворот, затем правый поворот](../assets/avltree_left_right_rotate.png)

### Сначала правый поворот, затем левый поворот

Как показано на рисунке ниже, для зеркальной ситуации вышеупомянутого несбалансированного двоичного дерева необходимо сначала выполнить "правый поворот" для `child`, а затем "левый поворот" для `node`.

![Сначала правый поворот, затем левый поворот](../assets/avltree_right_left_rotate.png)

### Выбор поворота

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

![Четыре ситуации поворота AVL-дерева](../assets/avltree_rotation_cases.png)

Как показано в таблице ниже, мы определяем, к какой ситуации на рисунке выше относится несбалансированный узел, путем оценки знака коэффициента балансировки несбалансированного узла и коэффициента балансировки дочернего узла с большей высотой.

<p align="center"> Таблица <id> &nbsp; Условия выбора четырех типов поворотов </p>

| Коэффициент балансировки несбалансированного узла | Коэффициент балансировки дочернего узла | Применяемый метод поворота |
| ------------------ | ---------------- | ---------------- |
| $> 1$ (левое смещение)   | $\geq 0$         | Правый поворот             |
| $> 1$ (левое смещение)   | $<0$             | Сначала левый поворот, затем правый поворот     |
| $< -1$ (правое смещение)  | $\leq 0$         | Левый поворот             |
| $< -1$ (правое смещение)  | $>0$             | Сначала правый поворот, затем левый поворот     |

Для удобства использования мы инкапсулируем операцию поворота в функцию. **С помощью этой функции мы можем выполнять повороты для различных ситуаций несбалансированности, восстанавливая баланс несбалансированных узлов**. Код показан ниже:

```src
[file]{avl_tree}-[class]{avl_tree}-[func]{rotate}
```

## Основные операции с AVL-деревом

### Вставка узла

Операция вставки узла в AVL-дерево в основном аналогична операции в двоичном дереве поиска. Единственное отличие заключается в том, что после вставки узла в AVL-дерево на пути от этого узла к корневому узлу может появиться серия несбалансированных узлов. Поэтому **необходимо начиная с этого узла снизу вверх выполнять операции поворота, чтобы восстановить баланс всех несбалансированных узлов**. Код показан ниже:

```src
[file]{avl_tree}-[class]{avl_tree}-[func]{insert_helper}
```

### Удаление узла

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

```src
[file]{avl_tree}-[class]{avl_tree}-[func]{remove_helper}
```

### Поиск узла

Операция поиска узла в AVL-дереве идентична операции в двоичном дереве поиска, здесь не будем повторяться.

## Типичные применения AVL-дерева

- Организация и хранение больших объемов данных, подходит для сценариев с высокой частотой поиска и низкой частотой вставки и удаления.
- Используется для построения системы индексов в базах данных.
- Красно-черное дерево также является распространенным сбалансированным двоичным деревом поиска. По сравнению с AVL-деревом условия балансировки красно-черного дерева более мягкие, для операций вставки и удаления узлов требуется меньше операций поворота, средняя эффективность операций добавления и удаления узлов выше.