mirror of https://github.com/krahets/hello-algo.git synced 2026-02-10 22:25:30 +08:00

Files

krahets 8071daddaa First version.

2026-01-20 15:08:42 +08:00

22 KiB

Raw Permalink Blame History

AVL-дерево *

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

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

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

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

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

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

Высота узла

Поскольку операции с 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. Мы создадим две вспомогательные функции для получения и обновления высоты узла:

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

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

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

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

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

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

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

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

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

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

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

=== "<1>"

=== "<2>"

=== "<3>"

=== "<4>"

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица Условия выбора четырех типов поворотов

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

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

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

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

Вставка узла

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

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

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

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

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

Поиск узла

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

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

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

22 KiB Raw Permalink Blame History Unescape Escape