Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 7.5 AVL-дерево *

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

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

Рисунок 7-24 Деградация AVL-дерева после удаления узлов

Другой пример: если в идеальное двоичное дерево, показанное на рисунке 7-25, вставить два узла, то дерево сильно наклонится влево, а временная сложность поиска тоже ухудшится.

Рисунок 7-25 Деградация AVL-дерева после вставки узлов

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

## 7.5.1 Распространенные термины AVL-дерева

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

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

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

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby

    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  # Ссылка на правого дочернего узла

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

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

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

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

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

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

    /* Класс узла 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;
        }
    }

    /* Класс узла 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;
        }
    }

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

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

    /* Структура узла 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;
    }

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

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

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
avl_tree.py

    def height(self, node: TreeNode | None) -> int:
        """Получить высоту узла"""
        # Высота пустого узла равна -1, высота листового узла равна 0
        if node is not None:
            return node.height
        return -1

    def update_height(self, node: TreeNode | None):
        """Обновить высоту узла"""
        # Высота узла равна высоте более высокого поддерева + 1
        node.height = max([self.height(node.left), self.height(node.right)]) + 1

avl_tree.cpp

    /* Получить высоту узла */
    int height(TreeNode *node) {
        // Высота пустого узла равна -1, высота листового узла равна 0
        return node == nullptr ? -1 : node->height;
    }

    /* Обновить высоту узла */
    void updateHeight(TreeNode *node) {
        // Высота узла равна высоте более высокого поддерева + 1
        node->height = max(height(node->left), height(node->right)) + 1;
    }

avl_tree.java

    /* Получить высоту узла */
    int height(TreeNode node) {
        // Высота пустого узла равна -1, высота листового узла равна 0
        return node == null ? -1 : node.height;
    }

    /* Обновить высоту узла */
    void updateHeight(TreeNode node) {
        // Высота узла равна высоте более высокого поддерева + 1
        node.height = Math.max(height(node.left), height(node.right)) + 1;
    }

avl_tree.cs

    /* Получить высоту узла */
    int Height(TreeNode? node) {
        // Высота пустого узла равна -1, высота листового узла равна 0
        return node == null ? -1 : node.height;
    }

    /* Обновить высоту узла */
    void UpdateHeight(TreeNode node) {
        // Высота узла равна высоте более высокого поддерева + 1
        node.height = Math.Max(Height(node.left), Height(node.right)) + 1;
    }

avl_tree.go

    /* Получить высоту узла */
    func (t *aVLTree) height(node *TreeNode) int {
        // Высота пустого узла равна -1, высота листового узла равна 0
        if node != nil {
            return node.Height
        }
        return -1
    }

    /* Обновить высоту узла */
    func (t *aVLTree) updateHeight(node *TreeNode) {
        lh := t.height(node.Left)
        rh := t.height(node.Right)
        // Высота узла равна высоте более высокого поддерева + 1
        if lh > rh {
            node.Height = lh + 1
        } else {
            node.Height = rh + 1
        }
    }

avl_tree.swift

    /* Получить высоту узла */
    func height(node: TreeNode?) -> Int {
        // Высота пустого узла равна -1, высота листового узла равна 0
        node?.height ?? -1
    }

    /* Обновить высоту узла */
    func updateHeight(node: TreeNode?) {
        // Высота узла равна высоте более высокого поддерева + 1
        node?.height = max(height(node: node?.left), height(node: node?.right)) + 1
    }

avl_tree.js

    /* Получить высоту узла */
    height(node) {
        // Высота пустого узла равна -1, высота листового узла равна 0
        return node === null ? -1 : node.height;
    }

    /* Обновить высоту узла */
    #updateHeight(node) {
        // Высота узла равна высоте более высокого поддерева + 1
        node.height =
            Math.max(this.height(node.left), this.height(node.right)) + 1;
    }

avl_tree.ts

    /* Получить высоту узла */
    height(node: TreeNode): number {
        // Высота пустого узла равна -1, высота листового узла равна 0
        return node === null ? -1 : node.height;
    }

    /* Обновить высоту узла */
    updateHeight(node: TreeNode): void {
        // Высота узла равна высоте более высокого поддерева + 1
        node.height =
            Math.max(this.height(node.left), this.height(node.right)) + 1;
    }

avl_tree.dart

    /* Получить высоту узла */
    int height(TreeNode? node) {
      // Высота пустого узла равна -1, высота листового узла равна 0
      return node == null ? -1 : node.height;
    }

    /* Обновить высоту узла */
    void updateHeight(TreeNode? node) {
      // Высота узла равна высоте более высокого поддерева + 1
      node!.height = max(height(node.left), height(node.right)) + 1;
    }

avl_tree.rs

    /* Получить высоту узла */
    fn height(node: OptionTreeNodeRc) -> i32 {
        // Высота пустого узла равна -1, высота листового узла равна 0
        match node {
            Some(node) => node.borrow().height,
            None => -1,
        }
    }

    /* Обновить высоту узла */
    fn update_height(node: OptionTreeNodeRc) {
        if let Some(node) = node {
            let left = node.borrow().left.clone();
            let right = node.borrow().right.clone();
            // Высота узла равна высоте более высокого поддерева + 1
            node.borrow_mut().height = std::cmp::max(Self::height(left), Self::height(right)) + 1;
        }
    }

avl_tree.c

    /* Получить высоту узла */
    int height(TreeNode *node) {
        // Высота пустого узла равна -1, высота листового узла равна 0
        if (node != NULL) {
            return node->height;
        }
        return -1;
    }

    /* Обновить высоту узла */
    void updateHeight(TreeNode *node) {
        int lh = height(node->left);
        int rh = height(node->right);
        // Высота узла равна высоте более высокого поддерева + 1
        if (lh > rh) {
            node->height = lh + 1;
        } else {
            node->height = rh + 1;
        }
    }

avl_tree.kt

    /* Получить высоту узла */
    fun height(node: TreeNode?): Int {
        // Высота пустого узла равна -1, высота листового узла равна 0
        return node?.height ?: -1
    }

    /* Обновить высоту узла */
    fun updateHeight(node: TreeNode?) {
        // Высота узла равна высоте более высокого поддерева + 1
        node?.height = max(height(node?.left), height(node?.right)) + 1
    }

avl_tree.rb

    ### Получить высоту узла ###
    def height(node)
      # Высота пустого узла равна -1, высота листового узла равна 0
      return node.height unless node.nil?

      -1
    end

    ### Обновить высоту узла ###
    def update_height(node)
      # Высота узла равна высоте более высокого поддерева + 1
      node.height = [height(node.left), height(node.right)].max + 1
    end

### 2. Баланс-фактор узла

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

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
avl_tree.py

    def balance_factor(self, node: TreeNode | None) -> int:
        """Получить коэффициент баланса"""
        # Коэффициент баланса пустого узла равен 0
        if node is None:
            return 0
        # Коэффициент баланса узла = высота левого поддерева - высота правого поддерева
        return self.height(node.left) - self.height(node.right)

avl_tree.cpp

    /* Получить коэффициент баланса */
    int balanceFactor(TreeNode *node) {
        // Коэффициент баланса пустого узла равен 0
        if (node == nullptr)
            return 0;
        // Коэффициент баланса узла = высота левого поддерева - высота правого поддерева
        return height(node->left) - height(node->right);
    }

avl_tree.java

    /* Получить коэффициент баланса */
    int balanceFactor(TreeNode node) {
        // Коэффициент баланса пустого узла равен 0
        if (node == null)
            return 0;
        // Коэффициент баланса узла = высота левого поддерева - высота правого поддерева
        return height(node.left) - height(node.right);
    }

avl_tree.cs

    /* Получить коэффициент баланса */
    int BalanceFactor(TreeNode? node) {
        // Коэффициент баланса пустого узла равен 0
        if (node == null) return 0;
        // Коэффициент баланса узла = высота левого поддерева - высота правого поддерева
        return Height(node.left) - Height(node.right);
    }

avl_tree.go

    /* Получить коэффициент баланса */
    func (t *aVLTree) balanceFactor(node *TreeNode) int {
        // Коэффициент баланса пустого узла равен 0
        if node == nil {
            return 0
        }
        // Коэффициент баланса узла = высота левого поддерева - высота правого поддерева
        return t.height(node.Left) - t.height(node.Right)
    }

avl_tree.swift

    /* Получить коэффициент баланса */
    func balanceFactor(node: TreeNode?) -> Int {
        // Коэффициент баланса пустого узла равен 0
        guard let node = node else { return 0 }
        // Коэффициент баланса узла = высота левого поддерева - высота правого поддерева
        return height(node: node.left) - height(node: node.right)
    }

avl_tree.js

    /* Получить коэффициент баланса */
    balanceFactor(node) {
        // Коэффициент баланса пустого узла равен 0
        if (node === null) return 0;
        // Коэффициент баланса узла = высота левого поддерева - высота правого поддерева
        return this.height(node.left) - this.height(node.right);
    }

avl_tree.ts

    /* Получить коэффициент баланса */
    balanceFactor(node: TreeNode): number {
        // Коэффициент баланса пустого узла равен 0
        if (node === null) return 0;
        // Коэффициент баланса узла = высота левого поддерева - высота правого поддерева
        return this.height(node.left) - this.height(node.right);
    }

avl_tree.dart

    /* Получить коэффициент баланса */
    int balanceFactor(TreeNode? node) {
      // Коэффициент баланса пустого узла равен 0
      if (node == null) return 0;
      // Коэффициент баланса узла = высота левого поддерева - высота правого поддерева
      return height(node.left) - height(node.right);
    }

avl_tree.rs

    /* Получить коэффициент баланса */
    fn balance_factor(node: OptionTreeNodeRc) -> i32 {
        match node {
            // Коэффициент баланса пустого узла равен 0
            None => 0,
            // Коэффициент баланса узла = высота левого поддерева - высота правого поддерева
            Some(node) => {
                Self::height(node.borrow().left.clone()) - Self::height(node.borrow().right.clone())
            }
        }
    }

avl_tree.c

    /* Получить коэффициент баланса */
    int balanceFactor(TreeNode *node) {
        // Коэффициент баланса пустого узла равен 0
        if (node == NULL) {
            return 0;
        }
        // Коэффициент баланса узла = высота левого поддерева - высота правого поддерева
        return height(node->left) - height(node->right);
    }

avl_tree.kt

    /* Получить коэффициент баланса */
    fun balanceFactor(node: TreeNode?): Int {
        // Коэффициент баланса пустого узла равен 0
        if (node == null) return 0
        // Коэффициент баланса узла = высота левого поддерева - высота правого поддерева
        return height(node.left) - height(node.right)
    }

avl_tree.rb

    ### Получить коэффициент баланса ###
    def balance_factor(node)
      # Коэффициент баланса пустого узла равен 0
      return 0 if node.nil?

      # Коэффициент баланса узла = высота левого поддерева - высота правого поддерева
      height(node.left) - height(node.right)
    end

Tip

Пусть баланс-фактор равен \(f\). Тогда для любого узла AVL-дерева выполняется \(-1 \le f \le 1\) .

## 7.5.2 Вращения AVL-дерева

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

Узлы, для которых абсолютное значение баланс-фактора больше \(1\) , мы называем «разбалансированными узлами». В зависимости от вида разбаланса вращения делятся на четыре типа: правое вращение, левое вращение, сначала левое затем правое, и сначала правое затем левое. Ниже разберем их подробно.

### 1. Правое вращение

Как показано на рисунке 7-26, под узлом указан его баланс-фактор. Если двигаться снизу вверх, то первым разбалансированным узлом в двоичном дереве будет «узел 3». Рассмотрим поддерево с этим узлом в качестве корня, обозначим данный узел как `node` , его левого дочернего узла как `child` и выполним «правое вращение». После завершения правого вращения поддерево снова станет сбалансированным и при этом сохранит свойство двоичного дерева поиска.

<1><2><3><4>

Рисунок 7-26 Шаги правого вращения

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

Рисунок 7-27 Правое вращение при наличии grand_child

«Поворот вправо» - это лишь образное описание. В реальности он реализуется через изменение указателей узлов. Код приведен ниже:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
avl_tree.py

    def right_rotate(self, node: TreeNode | None) -> TreeNode | None:
        """Операция правого вращения"""
        child = node.left
        grand_child = child.right
        # Выполнить правое вращение узла node вокруг child
        child.right = node
        node.left = grand_child
        # Обновить высоту узла
        self.update_height(node)
        self.update_height(child)
        # Вернуть корневой узел поддерева после вращения
        return child

avl_tree.cpp

    /* Операция правого вращения */
    TreeNode *rightRotate(TreeNode *node) {
        TreeNode *child = node->left;
        TreeNode *grandChild = child->right;
        // Выполнить правое вращение узла node вокруг child
        child->right = node;
        node->left = grandChild;
        // Обновить высоту узла
        updateHeight(node);
        updateHeight(child);
        // Вернуть корневой узел поддерева после вращения
        return child;
    }

avl_tree.java

    /* Операция правого вращения */
    TreeNode rightRotate(TreeNode node) {
        TreeNode child = node.left;
        TreeNode grandChild = child.right;
        // Выполнить правое вращение узла node вокруг child
        child.right = node;
        node.left = grandChild;
        // Обновить высоту узла
        updateHeight(node);
        updateHeight(child);
        // Вернуть корневой узел поддерева после вращения
        return child;
    }

avl_tree.cs

    /* Операция правого вращения */
    TreeNode? RightRotate(TreeNode? node) {
        TreeNode? child = node?.left;
        TreeNode? grandChild = child?.right;
        // Выполнить правое вращение узла node вокруг child
        child.right = node;
        node.left = grandChild;
        // Обновить высоту узла
        UpdateHeight(node);
        UpdateHeight(child);
        // Вернуть корневой узел поддерева после вращения
        return child;
    }

avl_tree.go

    /* Операция правого вращения */
    func (t *aVLTree) rightRotate(node *TreeNode) *TreeNode {
        child := node.Left
        grandChild := child.Right
        // Выполнить правое вращение узла node вокруг child
        child.Right = node
        node.Left = grandChild
        // Обновить высоту узла
        t.updateHeight(node)
        t.updateHeight(child)
        // Вернуть корневой узел поддерева после вращения
        return child
    }

avl_tree.swift

    /* Операция правого вращения */
    func rightRotate(node: TreeNode?) -> TreeNode? {
        let child = node?.left
        let grandChild = child?.right
        // Выполнить правое вращение узла node вокруг child
        child?.right = node
        node?.left = grandChild
        // Обновить высоту узла
        updateHeight(node: node)
        updateHeight(node: child)
        // Вернуть корневой узел поддерева после вращения
        return child
    }

avl_tree.js

    /* Операция правого вращения */
    #rightRotate(node) {
        const child = node.left;
        const grandChild = child.right;
        // Выполнить правое вращение узла node вокруг child
        child.right = node;
        node.left = grandChild;
        // Обновить высоту узла
        this.#updateHeight(node);
        this.#updateHeight(child);
        // Вернуть корневой узел поддерева после вращения
        return child;
    }

avl_tree.ts

    /* Операция правого вращения */
    rightRotate(node: TreeNode): TreeNode {
        const child = node.left;
        const grandChild = child.right;
        // Выполнить правое вращение узла node вокруг child
        child.right = node;
        node.left = grandChild;
        // Обновить высоту узла
        this.updateHeight(node);
        this.updateHeight(child);
        // Вернуть корневой узел поддерева после вращения
        return child;
    }

avl_tree.dart

    /* Операция правого вращения */
    TreeNode? rightRotate(TreeNode? node) {
      TreeNode? child = node!.left;
      TreeNode? grandChild = child!.right;
      // Выполнить правое вращение узла node вокруг child
      child.right = node;
      node.left = grandChild;
      // Обновить высоту узла
      updateHeight(node);
      updateHeight(child);
      // Вернуть корневой узел поддерева после вращения
      return child;
    }

avl_tree.rs

    /* Операция правого вращения */
    fn right_rotate(node: OptionTreeNodeRc) -> OptionTreeNodeRc {
        match node {
            Some(node) => {
                let child = node.borrow().left.clone().unwrap();
                let grand_child = child.borrow().right.clone();
                // Выполнить правое вращение узла node вокруг child
                child.borrow_mut().right = Some(node.clone());
                node.borrow_mut().left = grand_child;
                // Обновить высоту узла
                Self::update_height(Some(node));
                Self::update_height(Some(child.clone()));
                // Вернуть корневой узел поддерева после вращения
                Some(child)
            }
            None => None,
        }
    }

avl_tree.c

    /* Операция правого вращения */
    TreeNode *rightRotate(TreeNode *node) {
        TreeNode *child, *grandChild;
        child = node->left;
        grandChild = child->right;
        // Выполнить правое вращение узла node вокруг child
        child->right = node;
        node->left = grandChild;
        // Обновить высоту узла
        updateHeight(node);
        updateHeight(child);
        // Вернуть корневой узел поддерева после вращения
        return child;
    }

avl_tree.kt

    /* Операция правого вращения */
    fun rightRotate(node: TreeNode?): TreeNode {
        val child = node!!.left
        val grandChild = child!!.right
        // Выполнить правое вращение узла node вокруг child
        child.right = node
        node.left = grandChild
        // Обновить высоту узла
        updateHeight(node)
        updateHeight(child)
        // Вернуть корневой узел поддерева после вращения
        return child
    }

avl_tree.rb

    ### Операция правого вращения ###
    def right_rotate(node)
      child = node.left
      grand_child = child.right
      # Выполнить правое вращение узла node вокруг child
      child.right = node
      node.left = grand_child
      # Обновить высоту узла
      update_height(node)
      update_height(child)
      # Вернуть корневой узел поддерева после вращения
      child
    end

### 2. Левое вращение

Соответственно, если рассмотреть «зеркальную» версию приведенного выше разбалансированного двоичного дерева, то понадобится выполнить «левое вращение», показанное на рисунке 7-28.

Рисунок 7-28 Левое вращение

Аналогичная ситуация показана на рисунке 7-29. Если у узла `child` есть левый дочерний узел, который обозначим как `grand_child` , то в левое вращение также требуется добавить шаг: сделать `grand_child` правым дочерним узлом `node` .

Рисунок 7-29 Левое вращение при наличии grand_child

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

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
avl_tree.py

    def left_rotate(self, node: TreeNode | None) -> TreeNode | None:
        """Операция левого вращения"""
        child = node.right
        grand_child = child.left
        # Выполнить левое вращение узла node вокруг child
        child.left = node
        node.right = grand_child
        # Обновить высоту узла
        self.update_height(node)
        self.update_height(child)
        # Вернуть корневой узел поддерева после вращения
        return child

avl_tree.cpp

    /* Операция левого вращения */
    TreeNode *leftRotate(TreeNode *node) {
        TreeNode *child = node->right;
        TreeNode *grandChild = child->left;
        // Выполнить левое вращение узла node вокруг child
        child->left = node;
        node->right = grandChild;
        // Обновить высоту узла
        updateHeight(node);
        updateHeight(child);
        // Вернуть корневой узел поддерева после вращения
        return child;
    }

avl_tree.java

    /* Операция левого вращения */
    TreeNode leftRotate(TreeNode node) {
        TreeNode child = node.right;
        TreeNode grandChild = child.left;
        // Выполнить левое вращение узла node вокруг child
        child.left = node;
        node.right = grandChild;
        // Обновить высоту узла
        updateHeight(node);
        updateHeight(child);
        // Вернуть корневой узел поддерева после вращения
        return child;
    }

avl_tree.cs

    /* Операция левого вращения */
    TreeNode? LeftRotate(TreeNode? node) {
        TreeNode? child = node?.right;
        TreeNode? grandChild = child?.left;
        // Выполнить левое вращение узла node вокруг child
        child.left = node;
        node.right = grandChild;
        // Обновить высоту узла
        UpdateHeight(node);
        UpdateHeight(child);
        // Вернуть корневой узел поддерева после вращения
        return child;
    }

avl_tree.go

    /* Операция левого вращения */
    func (t *aVLTree) leftRotate(node *TreeNode) *TreeNode {
        child := node.Right
        grandChild := child.Left
        // Выполнить левое вращение узла node вокруг child
        child.Left = node
        node.Right = grandChild
        // Обновить высоту узла
        t.updateHeight(node)
        t.updateHeight(child)
        // Вернуть корневой узел поддерева после вращения
        return child
    }

avl_tree.swift

    /* Операция левого вращения */
    func leftRotate(node: TreeNode?) -> TreeNode? {
        let child = node?.right
        let grandChild = child?.left
        // Выполнить левое вращение узла node вокруг child
        child?.left = node
        node?.right = grandChild
        // Обновить высоту узла
        updateHeight(node: node)
        updateHeight(node: child)
        // Вернуть корневой узел поддерева после вращения
        return child
    }

avl_tree.js

    /* Операция левого вращения */
    #leftRotate(node) {
        const child = node.right;
        const grandChild = child.left;
        // Выполнить левое вращение узла node вокруг child
        child.left = node;
        node.right = grandChild;
        // Обновить высоту узла
        this.#updateHeight(node);
        this.#updateHeight(child);
        // Вернуть корневой узел поддерева после вращения
        return child;
    }

avl_tree.ts

    /* Операция левого вращения */
    leftRotate(node: TreeNode): TreeNode {
        const child = node.right;
        const grandChild = child.left;
        // Выполнить левое вращение узла node вокруг child
        child.left = node;
        node.right = grandChild;
        // Обновить высоту узла
        this.updateHeight(node);
        this.updateHeight(child);
        // Вернуть корневой узел поддерева после вращения
        return child;
    }

avl_tree.dart

    /* Операция левого вращения */
    TreeNode? leftRotate(TreeNode? node) {
      TreeNode? child = node!.right;
      TreeNode? grandChild = child!.left;
      // Выполнить левое вращение узла node вокруг child
      child.left = node;
      node.right = grandChild;
      // Обновить высоту узла
      updateHeight(node);
      updateHeight(child);
      // Вернуть корневой узел поддерева после вращения
      return child;
    }

avl_tree.rs

    /* Операция левого вращения */
    fn left_rotate(node: OptionTreeNodeRc) -> OptionTreeNodeRc {
        match node {
            Some(node) => {
                let child = node.borrow().right.clone().unwrap();
                let grand_child = child.borrow().left.clone();
                // Выполнить левое вращение узла node вокруг child
                child.borrow_mut().left = Some(node.clone());
                node.borrow_mut().right = grand_child;
                // Обновить высоту узла
                Self::update_height(Some(node));
                Self::update_height(Some(child.clone()));
                // Вернуть корневой узел поддерева после вращения
                Some(child)
            }
            None => None,
        }
    }

avl_tree.c

    /* Операция левого вращения */
    TreeNode *leftRotate(TreeNode *node) {
        TreeNode *child, *grandChild;
        child = node->right;
        grandChild = child->left;
        // Выполнить левое вращение узла node вокруг child
        child->left = node;
        node->right = grandChild;
        // Обновить высоту узла
        updateHeight(node);
        updateHeight(child);
        // Вернуть корневой узел поддерева после вращения
        return child;
    }

avl_tree.kt

    /* Операция левого вращения */
    fun leftRotate(node: TreeNode?): TreeNode {
        val child = node!!.right
        val grandChild = child!!.left
        // Выполнить левое вращение узла node вокруг child
        child.left = node
        node.right = grandChild
        // Обновить высоту узла
        updateHeight(node)
        updateHeight(child)
        // Вернуть корневой узел поддерева после вращения
        return child
    }

avl_tree.rb

    ### Операция левого вращения ###
    def left_rotate(node)
      child = node.right
      grand_child = child.left
      # Выполнить левое вращение узла node вокруг child
      child.left = node
      node.right = grand_child
      # Обновить высоту узла
      update_height(node)
      update_height(child)
      # Вернуть корневой узел поддерева после вращения
      child
    end

### 3. Сначала левое, затем правое вращение

Для разбалансированного узла 3 на рисунке 7-30 ни одно лишь левое вращение, ни одно лишь правое вращение не способны вернуть поддерево в баланс. В этом случае нужно сначала выполнить «левое вращение» для `child` , а затем выполнить «правое вращение» для `node` .

Рисунок 7-30 Сначала левое, затем правое вращение

### 4. Сначала правое, затем левое вращение

Как показано на рисунке 7-31, для зеркальной ситуации предыдущего разбалансированного двоичного дерева нужно сначала выполнить «правое вращение» для `child` , а затем «левое вращение» для `node` .

Рисунок 7-31 Сначала правое, затем левое вращение

### 5. Выбор вращения

Четыре вида разбаланса, показанные на рисунке 7-32, по одному соответствуют рассмотренным выше случаям. Для них соответственно требуются правое вращение, сначала левое затем правое, сначала правое затем левое и левое вращение.

Рисунок 7-32 Четыре случая вращений AVL-дерева

Как показано в таблице 7-3, мы определяем, какому из случаев на рисунке 7-32 соответствует разбалансированный узел, по знаку баланс-фактора самого разбалансированного узла и по знаку баланс-фактора дочернего узла на более высокой стороне.

Таблица 7-3 Условия выбора для четырех случаев вращений

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

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

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
avl_tree.py

    def rotate(self, node: TreeNode | None) -> TreeNode | None:
        """Выполнить вращение, чтобы снова сбалансировать поддерево"""
        # Получить коэффициент баланса узла node
        balance_factor = self.balance_factor(node)
        # Левосторонне перекошенное дерево
        if balance_factor > 1:
            if self.balance_factor(node.left) >= 0:
                # Правое вращение
                return self.right_rotate(node)
            else:
                # Сначала левое вращение, затем правое
                node.left = self.left_rotate(node.left)
                return self.right_rotate(node)
        # Правосторонне перекошенное дерево
        elif balance_factor < -1:
            if self.balance_factor(node.right) <= 0:
                # Левое вращение
                return self.left_rotate(node)
            else:
                # Сначала правое вращение, затем левое
                node.right = self.right_rotate(node.right)
                return self.left_rotate(node)
        # Дерево сбалансировано, вращение не требуется, вернуть сразу
        return node

avl_tree.cpp

    /* Выполнить вращение, чтобы снова сбалансировать поддерево */
    TreeNode *rotate(TreeNode *node) {
        // Получить коэффициент баланса узла node
        int _balanceFactor = balanceFactor(node);
        // Левосторонне перекошенное дерево
        if (_balanceFactor > 1) {
            if (balanceFactor(node->left) >= 0) {
                // Правое вращение
                return rightRotate(node);
            } else {
                // Сначала левое вращение, затем правое
                node->left = leftRotate(node->left);
                return rightRotate(node);
            }
        }
        // Правосторонне перекошенное дерево
        if (_balanceFactor < -1) {
            if (balanceFactor(node->right) <= 0) {
                // Левое вращение
                return leftRotate(node);
            } else {
                // Сначала правое вращение, затем левое
                node->right = rightRotate(node->right);
                return leftRotate(node);
            }
        }
        // Дерево сбалансировано, вращение не требуется, вернуть сразу
        return node;
    }

avl_tree.java

    /* Выполнить вращение, чтобы снова сбалансировать поддерево */
    TreeNode rotate(TreeNode node) {
        // Получить коэффициент баланса узла node
        int balanceFactor = balanceFactor(node);
        // Левосторонне перекошенное дерево
        if (balanceFactor > 1) {
            if (balanceFactor(node.left) >= 0) {
                // Правое вращение
                return rightRotate(node);
            } else {
                // Сначала левое вращение, затем правое
                node.left = leftRotate(node.left);
                return rightRotate(node);
            }
        }
        // Правосторонне перекошенное дерево
        if (balanceFactor < -1) {
            if (balanceFactor(node.right) <= 0) {
                // Левое вращение
                return leftRotate(node);
            } else {
                // Сначала правое вращение, затем левое
                node.right = rightRotate(node.right);
                return leftRotate(node);
            }
        }
        // Дерево сбалансировано, вращение не требуется, вернуть сразу
        return node;
    }

avl_tree.cs

    /* Выполнить вращение, чтобы снова сбалансировать поддерево */
    TreeNode? Rotate(TreeNode? node) {
        // Получить коэффициент баланса узла node
        int balanceFactorInt = BalanceFactor(node);
        // Левосторонне перекошенное дерево
        if (balanceFactorInt > 1) {
            if (BalanceFactor(node?.left) >= 0) {
                // Правое вращение
                return RightRotate(node);
            } else {
                // Сначала левое вращение, затем правое
                node!.left = LeftRotate(node!.left);
                return RightRotate(node);
            }
        }
        // Правосторонне перекошенное дерево
        if (balanceFactorInt < -1) {
            if (BalanceFactor(node?.right) <= 0) {
                // Левое вращение
                return LeftRotate(node);
            } else {
                // Сначала правое вращение, затем левое
                node!.right = RightRotate(node!.right);
                return LeftRotate(node);
            }
        }
        // Дерево сбалансировано, вращение не требуется, вернуть сразу
        return node;
    }

avl_tree.go

    /* Выполнить вращение, чтобы снова сбалансировать поддерево */
    func (t *aVLTree) rotate(node *TreeNode) *TreeNode {
        // Получить коэффициент баланса узла node
        // В Go рекомендуется использовать короткие имена переменных, здесь bf обозначает t.balanceFactor
        bf := t.balanceFactor(node)
        // Левосторонне перекошенное дерево
        if bf > 1 {
            if t.balanceFactor(node.Left) >= 0 {
                // Правое вращение
                return t.rightRotate(node)
            } else {
                // Сначала левое вращение, затем правое
                node.Left = t.leftRotate(node.Left)
                return t.rightRotate(node)
            }
        }
        // Правосторонне перекошенное дерево
        if bf < -1 {
            if t.balanceFactor(node.Right) <= 0 {
                // Левое вращение
                return t.leftRotate(node)
            } else {
                // Сначала правое вращение, затем левое
                node.Right = t.rightRotate(node.Right)
                return t.leftRotate(node)
            }
        }
        // Дерево сбалансировано, вращение не требуется, вернуть сразу
        return node
    }

avl_tree.swift

    /* Выполнить вращение, чтобы снова сбалансировать поддерево */
    func rotate(node: TreeNode?) -> TreeNode? {
        // Получить коэффициент баланса узла node
        let balanceFactor = balanceFactor(node: node)
        // Левосторонне перекошенное дерево
        if balanceFactor > 1 {
            if self.balanceFactor(node: node?.left) >= 0 {
                // Правое вращение
                return rightRotate(node: node)
            } else {
                // Сначала левое вращение, затем правое
                node?.left = leftRotate(node: node?.left)
                return rightRotate(node: node)
            }
        }
        // Правосторонне перекошенное дерево
        if balanceFactor < -1 {
            if self.balanceFactor(node: node?.right) <= 0 {
                // Левое вращение
                return leftRotate(node: node)
            } else {
                // Сначала правое вращение, затем левое
                node?.right = rightRotate(node: node?.right)
                return leftRotate(node: node)
            }
        }
        // Дерево сбалансировано, вращение не требуется, вернуть сразу
        return node
    }

avl_tree.js

    /* Выполнить вращение, чтобы снова сбалансировать поддерево */
    #rotate(node) {
        // Получить коэффициент баланса узла node
        const balanceFactor = this.balanceFactor(node);
        // Левосторонне перекошенное дерево
        if (balanceFactor > 1) {
            if (this.balanceFactor(node.left) >= 0) {
                // Правое вращение
                return this.#rightRotate(node);
            } else {
                // Сначала левое вращение, затем правое
                node.left = this.#leftRotate(node.left);
                return this.#rightRotate(node);
            }
        }
        // Правосторонне перекошенное дерево
        if (balanceFactor < -1) {
            if (this.balanceFactor(node.right) <= 0) {
                // Левое вращение
                return this.#leftRotate(node);
            } else {
                // Сначала правое вращение, затем левое
                node.right = this.#rightRotate(node.right);
                return this.#leftRotate(node);
            }
        }
        // Дерево сбалансировано, вращение не требуется, вернуть сразу
        return node;
    }

avl_tree.ts

    /* Выполнить вращение, чтобы снова сбалансировать поддерево */
    rotate(node: TreeNode): TreeNode {
        // Получить коэффициент баланса узла node
        const balanceFactor = this.balanceFactor(node);
        // Левосторонне перекошенное дерево
        if (balanceFactor > 1) {
            if (this.balanceFactor(node.left) >= 0) {
                // Правое вращение
                return this.rightRotate(node);
            } else {
                // Сначала левое вращение, затем правое
                node.left = this.leftRotate(node.left);
                return this.rightRotate(node);
            }
        }
        // Правосторонне перекошенное дерево
        if (balanceFactor < -1) {
            if (this.balanceFactor(node.right) <= 0) {
                // Левое вращение
                return this.leftRotate(node);
            } else {
                // Сначала правое вращение, затем левое
                node.right = this.rightRotate(node.right);
                return this.leftRotate(node);
            }
        }
        // Дерево сбалансировано, вращение не требуется, вернуть сразу
        return node;
    }

avl_tree.dart

    /* Выполнить вращение, чтобы снова сбалансировать поддерево */
    TreeNode? rotate(TreeNode? node) {
      // Получить коэффициент баланса узла node
      int factor = balanceFactor(node);
      // Левосторонне перекошенное дерево
      if (factor > 1) {
        if (balanceFactor(node!.left) >= 0) {
          // Правое вращение
          return rightRotate(node);
        } else {
          // Сначала левое вращение, затем правое
          node.left = leftRotate(node.left);
          return rightRotate(node);
        }
      }
      // Правосторонне перекошенное дерево
      if (factor < -1) {
        if (balanceFactor(node!.right) <= 0) {
          // Левое вращение
          return leftRotate(node);
        } else {
          // Сначала правое вращение, затем левое
          node.right = rightRotate(node.right);
          return leftRotate(node);
        }
      }
      // Дерево сбалансировано, вращение не требуется, вернуть сразу
      return node;
    }

avl_tree.rs

    /* Выполнить вращение, чтобы снова сбалансировать поддерево */
    fn rotate(node: OptionTreeNodeRc) -> OptionTreeNodeRc {
        // Получить коэффициент баланса узла node
        let balance_factor = Self::balance_factor(node.clone());
        // Левосторонне перекошенное дерево
        if balance_factor > 1 {
            let node = node.unwrap();
            if Self::balance_factor(node.borrow().left.clone()) >= 0 {
                // Правое вращение
                Self::right_rotate(Some(node))
            } else {
                // Сначала левое вращение, затем правое
                let left = node.borrow().left.clone();
                node.borrow_mut().left = Self::left_rotate(left);
                Self::right_rotate(Some(node))
            }
        }
        // Правосторонне перекошенное дерево
        else if balance_factor < -1 {
            let node = node.unwrap();
            if Self::balance_factor(node.borrow().right.clone()) <= 0 {
                // Левое вращение
                Self::left_rotate(Some(node))
            } else {
                // Сначала правое вращение, затем левое
                let right = node.borrow().right.clone();
                node.borrow_mut().right = Self::right_rotate(right);
                Self::left_rotate(Some(node))
            }
        } else {
            // Дерево сбалансировано, вращение не требуется, вернуть сразу
            node
        }
    }

avl_tree.c

    /* Выполнить вращение, чтобы снова сбалансировать поддерево */
    TreeNode *rotate(TreeNode *node) {
        // Получить коэффициент баланса узла node
        int bf = balanceFactor(node);
        // Левосторонне перекошенное дерево
        if (bf > 1) {
            if (balanceFactor(node->left) >= 0) {
                // Правое вращение
                return rightRotate(node);
            } else {
                // Сначала левое вращение, затем правое
                node->left = leftRotate(node->left);
                return rightRotate(node);
            }
        }
        // Правосторонне перекошенное дерево
        if (bf < -1) {
            if (balanceFactor(node->right) <= 0) {
                // Левое вращение
                return leftRotate(node);
            } else {
                // Сначала правое вращение, затем левое
                node->right = rightRotate(node->right);
                return leftRotate(node);
            }
        }
        // Дерево сбалансировано, вращение не требуется, вернуть сразу
        return node;
    }

avl_tree.kt

    /* Выполнить вращение, чтобы снова сбалансировать поддерево */
    fun rotate(node: TreeNode): TreeNode {
        // Получить коэффициент баланса узла node
        val balanceFactor = balanceFactor(node)
        // Левосторонне перекошенное дерево
        if (balanceFactor > 1) {
            if (balanceFactor(node.left) >= 0) {
                // Правое вращение
                return rightRotate(node)
            } else {
                // Сначала левое вращение, затем правое
                node.left = leftRotate(node.left)
                return rightRotate(node)
            }
        }
        // Правосторонне перекошенное дерево
        if (balanceFactor < -1) {
            if (balanceFactor(node.right) <= 0) {
                // Левое вращение
                return leftRotate(node)
            } else {
                // Сначала правое вращение, затем левое
                node.right = rightRotate(node.right)
                return leftRotate(node)
            }
        }
        // Дерево сбалансировано, вращение не требуется, вернуть сразу
        return node
    }

avl_tree.rb

    ### Выполнить вращение, чтобы снова сбалансировать поддерево ###
    def rotate(node)
      # Получить коэффициент баланса узла node
      balance_factor = balance_factor(node)
      # Обойти левое поддерево
      if balance_factor > 1
        if balance_factor(node.left) >= 0
          # Правое вращение
          return right_rotate(node)
        else
          # Сначала левое вращение, затем правое
          node.left = left_rotate(node.left)
          return right_rotate(node)
        end
      # Правостороннее дерево обхода
      elsif balance_factor < -1
        if balance_factor(node.right) <= 0
          # Левое вращение
          return left_rotate(node)
        else
          # Сначала правое вращение, затем левое
          node.right = right_rotate(node.right)
          return left_rotate(node)
        end
      end
      # Дерево сбалансировано, вращение не требуется, вернуть сразу
      node
    end

## 7.5.3 Распространенные операции AVL-дерева

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

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

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
avl_tree.py

    def insert(self, val):
        """Вставка узла"""
        self._root = self.insert_helper(self._root, val)

    def insert_helper(self, node: TreeNode | None, val: int) -> TreeNode:
        """Рекурсивная вставка узла (вспомогательный метод)"""
        if node is None:
            return TreeNode(val)
        # 1. Найти позицию вставки и вставить узел
        if val < node.val:
            node.left = self.insert_helper(node.left, val)
        elif val > node.val:
            node.right = self.insert_helper(node.right, val)
        else:
            # Повторяющийся узел не вставлять, сразу вернуть
            return node
        # Обновить высоту узла
        self.update_height(node)
        # 2. Выполнить вращение, чтобы снова сбалансировать поддерево
        return self.rotate(node)

avl_tree.cpp

    /* Вставка узла */
    void insert(int val) {
        root = insertHelper(root, val);
    }

    /* Рекурсивная вставка узла (вспомогательный метод) */
    TreeNode *insertHelper(TreeNode *node, int val) {
        if (node == nullptr)
            return new TreeNode(val);
        /* 1. Найти позицию вставки и вставить узел */
        if (val < node->val)
            node->left = insertHelper(node->left, val);
        else if (val > node->val)
            node->right = insertHelper(node->right, val);
        else
            return node;    // Повторяющийся узел не вставлять, сразу вернуть
        updateHeight(node); // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = rotate(node);
        // Вернуть корневой узел поддерева
        return node;
    }

avl_tree.java

    /* Вставка узла */
    void insert(int val) {
        root = insertHelper(root, val);
    }

    /* Рекурсивная вставка узла (вспомогательный метод) */
    TreeNode insertHelper(TreeNode node, int val) {
        if (node == null)
            return new TreeNode(val);
        /* 1. Найти позицию вставки и вставить узел */
        if (val < node.val)
            node.left = insertHelper(node.left, val);
        else if (val > node.val)
            node.right = insertHelper(node.right, val);
        else
            return node; // Повторяющийся узел не вставлять, сразу вернуть
        updateHeight(node); // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = rotate(node);
        // Вернуть корневой узел поддерева
        return node;
    }

avl_tree.cs

    /* Вставка узла */
    void Insert(int val) {
        root = InsertHelper(root, val);
    }

    /* Рекурсивная вставка узла (вспомогательный метод) */
    TreeNode? InsertHelper(TreeNode? node, int val) {
        if (node == null) return new TreeNode(val);
        /* 1. Найти позицию вставки и вставить узел */
        if (val < node.val)
            node.left = InsertHelper(node.left, val);
        else if (val > node.val)
            node.right = InsertHelper(node.right, val);
        else
            return node;     // Повторяющийся узел не вставлять, сразу вернуть
        UpdateHeight(node);  // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = Rotate(node);
        // Вернуть корневой узел поддерева
        return node;
    }

avl_tree.go

    /* Вставка узла */
    func (t *aVLTree) insert(val int) {
        t.root = t.insertHelper(t.root, val)
    }

    /* Рекурсивная вставка узла (вспомогательная функция) */
    func (t *aVLTree) insertHelper(node *TreeNode, val int) *TreeNode {
        if node == nil {
            return NewTreeNode(val)
        }
        /* 1. Найти позицию вставки и вставить узел */
        if val < node.Val.(int) {
            node.Left = t.insertHelper(node.Left, val)
        } else if val > node.Val.(int) {
            node.Right = t.insertHelper(node.Right, val)
        } else {
            // Повторяющийся узел не вставлять, сразу вернуть
            return node
        }
        // Обновить высоту узла
        t.updateHeight(node)
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = t.rotate(node)
        // Вернуть корневой узел поддерева
        return node
    }

avl_tree.swift

    /* Вставка узла */
    func insert(val: Int) {
        root = insertHelper(node: root, val: val)
    }

    /* Рекурсивная вставка узла (вспомогательный метод) */
    func insertHelper(node: TreeNode?, val: Int) -> TreeNode? {
        var node = node
        if node == nil {
            return TreeNode(x: val)
        }
        /* 1. Найти позицию вставки и вставить узел */
        if val < node!.val {
            node?.left = insertHelper(node: node?.left, val: val)
        } else if val > node!.val {
            node?.right = insertHelper(node: node?.right, val: val)
        } else {
            return node // Повторяющийся узел не вставлять, сразу вернуть
        }
        updateHeight(node: node) // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = rotate(node: node)
        // Вернуть корневой узел поддерева
        return node
    }

avl_tree.js

    /* Вставка узла */
    insert(val) {
        this.root = this.#insertHelper(this.root, val);
    }

    /* Рекурсивная вставка узла (вспомогательный метод) */
    #insertHelper(node, val) {
        if (node === null) return new TreeNode(val);
        /* 1. Найти позицию вставки и вставить узел */
        if (val < node.val) node.left = this.#insertHelper(node.left, val);
        else if (val > node.val)
            node.right = this.#insertHelper(node.right, val);
        else return node; // Повторяющийся узел не вставлять, сразу вернуть
        this.#updateHeight(node); // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = this.#rotate(node);
        // Вернуть корневой узел поддерева
        return node;
    }

avl_tree.ts

    /* Вставка узла */
    insert(val: number): void {
        this.root = this.insertHelper(this.root, val);
    }

    /* Рекурсивная вставка узла (вспомогательный метод) */
    insertHelper(node: TreeNode, val: number): TreeNode {
        if (node === null) return new TreeNode(val);
        /* 1. Найти позицию вставки и вставить узел */
        if (val < node.val) {
            node.left = this.insertHelper(node.left, val);
        } else if (val > node.val) {
            node.right = this.insertHelper(node.right, val);
        } else {
            return node; // Повторяющийся узел не вставлять, сразу вернуть
        }
        this.updateHeight(node); // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = this.rotate(node);
        // Вернуть корневой узел поддерева
        return node;
    }

avl_tree.dart

    /* Вставка узла */
    void insert(int val) {
      root = insertHelper(root, val);
    }

    /* Рекурсивная вставка узла (вспомогательный метод) */
    TreeNode? insertHelper(TreeNode? node, int val) {
      if (node == null) return TreeNode(val);
      /* 1. Найти позицию вставки и вставить узел */
      if (val < node.val)
        node.left = insertHelper(node.left, val);
      else if (val > node.val)
        node.right = insertHelper(node.right, val);
      else
        return node; // Повторяющийся узел не вставлять, сразу вернуть
      updateHeight(node); // Обновить высоту узла
      /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
      node = rotate(node);
      // Вернуть корневой узел поддерева
      return node;
    }

avl_tree.rs

    /* Вставка узла */
    fn insert(&mut self, val: i32) {
        self.root = Self::insert_helper(self.root.clone(), val);
    }

    /* Рекурсивная вставка узла (вспомогательный метод) */
    fn insert_helper(node: OptionTreeNodeRc, val: i32) -> OptionTreeNodeRc {
        match node {
            Some(mut node) => {
                /* 1. Найти позицию вставки и вставить узел */
                match {
                    let node_val = node.borrow().val;
                    node_val
                }
                .cmp(&val)
                {
                    Ordering::Greater => {
                        let left = node.borrow().left.clone();
                        node.borrow_mut().left = Self::insert_helper(left, val);
                    }
                    Ordering::Less => {
                        let right = node.borrow().right.clone();
                        node.borrow_mut().right = Self::insert_helper(right, val);
                    }
                    Ordering::Equal => {
                        return Some(node); // Повторяющийся узел не вставлять, сразу вернуть
                    }
                }
                Self::update_height(Some(node.clone())); // Обновить высоту узла

                /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
                node = Self::rotate(Some(node)).unwrap();
                // Вернуть корневой узел поддерева
                Some(node)
            }
            None => Some(TreeNode::new(val)),
        }
    }

avl_tree.c

    /* Вставка узла */
    void insert(AVLTree *tree, int val) {
        tree->root = insertHelper(tree->root, val);
    }

    /* Рекурсивная вставка узла (вспомогательная функция) */
    TreeNode *insertHelper(TreeNode *node, int val) {
        if (node == NULL) {
            return newTreeNode(val);
        }
        /* 1. Найти позицию вставки и вставить узел */
        if (val < node->val) {
            node->left = insertHelper(node->left, val);
        } else if (val > node->val) {
            node->right = insertHelper(node->right, val);
        } else {
            // Повторяющийся узел не вставлять, сразу вернуть
            return node;
        }
        // Обновить высоту узла
        updateHeight(node);
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = rotate(node);
        // Вернуть корневой узел поддерева
        return node;
    }

avl_tree.kt

    /* Вставка узла */
    fun insert(_val: Int) {
        root = insertHelper(root, _val)
    }

    /* Рекурсивная вставка узла (вспомогательный метод) */
    fun insertHelper(n: TreeNode?, _val: Int): TreeNode {
        if (n == null)
            return TreeNode(_val)
        var node = n
        /* 1. Найти позицию вставки и вставить узел */
        if (_val < node._val)
            node.left = insertHelper(node.left, _val)
        else if (_val > node._val)
            node.right = insertHelper(node.right, _val)
        else
            return node // Повторяющийся узел не вставлять, сразу вернуть
        updateHeight(node) // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = rotate(node)
        // Вернуть корневой узел поддерева
        return node
    }

avl_tree.rb

    ### Вставка узла ###
    def insert(val)
      @root = insert_helper(@root, val)
    end

    ### Вставка узла ###
    def insert(val)
      @root = insert_helper(@root, val)
    end

    # ## Рекурсивная вставка узла (вспомогательный метод) ###
    def insert_helper(node, val)
      return TreeNode.new(val) if node.nil?
      # 1. Найти позицию вставки и вставить узел
      if val < node.val
        node.left = insert_helper(node.left, val)
      elsif val > node.val
        node.right = insert_helper(node.right, val)
      else
        # Повторяющийся узел не вставлять, сразу вернуть
        return node
      end
      # Обновить высоту узла
      update_height(node)
      # 2. Выполнить вращение, чтобы снова сбалансировать поддерево
      rotate(node)
    end

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

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

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
avl_tree.py

    def remove(self, val: int):
        """Удаление узла"""
        self._root = self.remove_helper(self._root, val)

    def remove_helper(self, node: TreeNode | None, val: int) -> TreeNode | None:
        """Рекурсивное удаление узла (вспомогательный метод)"""
        if node is None:
            return None
        # 1. Найти узел и удалить его
        if val < node.val:
            node.left = self.remove_helper(node.left, val)
        elif val > node.val:
            node.right = self.remove_helper(node.right, val)
        else:
            if node.left is None or node.right is None:
                child = node.left or node.right
                # Число дочерних узлов = 0, удалить node и сразу вернуть
                if child is None:
                    return None
                # Число дочерних узлов = 1, удалить node напрямую
                else:
                    node = child
            else:
                # Число дочерних узлов = 2, удалить следующий по симметричному обходу узел и заменить им текущий узел
                temp = node.right
                while temp.left is not None:
                    temp = temp.left
                node.right = self.remove_helper(node.right, temp.val)
                node.val = temp.val
        # Обновить высоту узла
        self.update_height(node)
        # 2. Выполнить вращение, чтобы снова сбалансировать поддерево
        return self.rotate(node)

avl_tree.cpp

    /* Удаление узла */
    void remove(int val) {
        root = removeHelper(root, val);
    }

    /* Рекурсивное удаление узла (вспомогательный метод) */
    TreeNode *removeHelper(TreeNode *node, int val) {
        if (node == nullptr)
            return nullptr;
        /* 1. Найти узел и удалить его */
        if (val < node->val)
            node->left = removeHelper(node->left, val);
        else if (val > node->val)
            node->right = removeHelper(node->right, val);
        else {
            if (node->left == nullptr || node->right == nullptr) {
                TreeNode *child = node->left != nullptr ? node->left : node->right;
                // Число дочерних узлов = 0, удалить node и сразу вернуть
                if (child == nullptr) {
                    delete node;
                    return nullptr;
                }
                // Число дочерних узлов = 1, удалить node напрямую
                else {
                    delete node;
                    node = child;
                }
            } else {
                // Число дочерних узлов = 2, удалить следующий по симметричному обходу узел и заменить им текущий узел
                TreeNode *temp = node->right;
                while (temp->left != nullptr) {
                    temp = temp->left;
                }
                int tempVal = temp->val;
                node->right = removeHelper(node->right, temp->val);
                node->val = tempVal;
            }
        }
        updateHeight(node); // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = rotate(node);
        // Вернуть корневой узел поддерева
        return node;
    }

avl_tree.java

    /* Удаление узла */
    void remove(int val) {
        root = removeHelper(root, val);
    }

    /* Рекурсивное удаление узла (вспомогательный метод) */
    TreeNode removeHelper(TreeNode node, int val) {
        if (node == null)
            return null;
        /* 1. Найти узел и удалить его */
        if (val < node.val)
            node.left = removeHelper(node.left, val);
        else if (val > node.val)
            node.right = removeHelper(node.right, val);
        else {
            if (node.left == null || node.right == null) {
                TreeNode child = node.left != null ? node.left : node.right;
                // Число дочерних узлов = 0, удалить node и сразу вернуть
                if (child == null)
                    return null;
                // Число дочерних узлов = 1, удалить node напрямую
                else
                    node = child;
            } else {
                // Число дочерних узлов = 2, удалить следующий по симметричному обходу узел и заменить им текущий узел
                TreeNode temp = node.right;
                while (temp.left != null) {
                    temp = temp.left;
                }
                node.right = removeHelper(node.right, temp.val);
                node.val = temp.val;
            }
        }
        updateHeight(node); // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = rotate(node);
        // Вернуть корневой узел поддерева
        return node;
    }

avl_tree.cs

    /* Удаление узла */
    void Remove(int val) {
        root = RemoveHelper(root, val);
    }

    /* Рекурсивное удаление узла (вспомогательный метод) */
    TreeNode? RemoveHelper(TreeNode? node, int val) {
        if (node == null) return null;
        /* 1. Найти узел и удалить его */
        if (val < node.val)
            node.left = RemoveHelper(node.left, val);
        else if (val > node.val)
            node.right = RemoveHelper(node.right, val);
        else {
            if (node.left == null || node.right == null) {
                TreeNode? child = node.left ?? node.right;
                // Число дочерних узлов = 0, удалить node и сразу вернуть
                if (child == null)
                    return null;
                // Число дочерних узлов = 1, удалить node напрямую
                else
                    node = child;
            } else {
                // Число дочерних узлов = 2, удалить следующий по симметричному обходу узел и заменить им текущий узел
                TreeNode? temp = node.right;
                while (temp.left != null) {
                    temp = temp.left;
                }
                node.right = RemoveHelper(node.right, temp.val!.Value);
                node.val = temp.val;
            }
        }
        UpdateHeight(node);  // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = Rotate(node);
        // Вернуть корневой узел поддерева
        return node;
    }

avl_tree.go

    /* Удаление узла */
    func (t *aVLTree) remove(val int) {
        t.root = t.removeHelper(t.root, val)
    }

    /* Рекурсивное удаление узла (вспомогательная функция) */
    func (t *aVLTree) removeHelper(node *TreeNode, val int) *TreeNode {
        if node == nil {
            return nil
        }
        /* 1. Найти узел и удалить его */
        if val < node.Val.(int) {
            node.Left = t.removeHelper(node.Left, val)
        } else if val > node.Val.(int) {
            node.Right = t.removeHelper(node.Right, val)
        } else {
            if node.Left == nil || node.Right == nil {
                child := node.Left
                if node.Right != nil {
                    child = node.Right
                }
                if child == nil {
                    // Число дочерних узлов = 0, удалить node и сразу вернуть
                    return nil
                } else {
                    // Число дочерних узлов = 1, удалить node напрямую
                    node = child
                }
            } else {
                // Число дочерних узлов = 2, удалить следующий по симметричному обходу узел и заменить им текущий узел
                temp := node.Right
                for temp.Left != nil {
                    temp = temp.Left
                }
                node.Right = t.removeHelper(node.Right, temp.Val.(int))
                node.Val = temp.Val
            }
        }
        // Обновить высоту узла
        t.updateHeight(node)
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = t.rotate(node)
        // Вернуть корневой узел поддерева
        return node
    }

avl_tree.swift

    /* Удаление узла */
    func remove(val: Int) {
        root = removeHelper(node: root, val: val)
    }

    /* Рекурсивное удаление узла (вспомогательный метод) */
    func removeHelper(node: TreeNode?, val: Int) -> TreeNode? {
        var node = node
        if node == nil {
            return nil
        }
        /* 1. Найти узел и удалить его */
        if val < node!.val {
            node?.left = removeHelper(node: node?.left, val: val)
        } else if val > node!.val {
            node?.right = removeHelper(node: node?.right, val: val)
        } else {
            if node?.left == nil || node?.right == nil {
                let child = node?.left ?? node?.right
                // Число дочерних узлов = 0, удалить node и сразу вернуть
                if child == nil {
                    return nil
                }
                // Число дочерних узлов = 1, удалить node напрямую
                else {
                    node = child
                }
            } else {
                // Число дочерних узлов = 2, удалить следующий по симметричному обходу узел и заменить им текущий узел
                var temp = node?.right
                while temp?.left != nil {
                    temp = temp?.left
                }
                node?.right = removeHelper(node: node?.right, val: temp!.val)
                node?.val = temp!.val
            }
        }
        updateHeight(node: node) // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = rotate(node: node)
        // Вернуть корневой узел поддерева
        return node
    }

avl_tree.js

    /* Удаление узла */
    remove(val) {
        this.root = this.#removeHelper(this.root, val);
    }

    /* Рекурсивное удаление узла (вспомогательный метод) */
    #removeHelper(node, val) {
        if (node === null) return null;
        /* 1. Найти узел и удалить его */
        if (val < node.val) node.left = this.#removeHelper(node.left, val);
        else if (val > node.val)
            node.right = this.#removeHelper(node.right, val);
        else {
            if (node.left === null || node.right === null) {
                const child = node.left !== null ? node.left : node.right;
                // Число дочерних узлов = 0, удалить node и сразу вернуть
                if (child === null) return null;
                // Число дочерних узлов = 1, удалить node напрямую
                else node = child;
            } else {
                // Число дочерних узлов = 2, удалить следующий по симметричному обходу узел и заменить им текущий узел
                let temp = node.right;
                while (temp.left !== null) {
                    temp = temp.left;
                }
                node.right = this.#removeHelper(node.right, temp.val);
                node.val = temp.val;
            }
        }
        this.#updateHeight(node); // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = this.#rotate(node);
        // Вернуть корневой узел поддерева
        return node;
    }

avl_tree.ts

    /* Удаление узла */
    remove(val: number): void {
        this.root = this.removeHelper(this.root, val);
    }

    /* Рекурсивное удаление узла (вспомогательный метод) */
    removeHelper(node: TreeNode, val: number): TreeNode {
        if (node === null) return null;
        /* 1. Найти узел и удалить его */
        if (val < node.val) {
            node.left = this.removeHelper(node.left, val);
        } else if (val > node.val) {
            node.right = this.removeHelper(node.right, val);
        } else {
            if (node.left === null || node.right === null) {
                const child = node.left !== null ? node.left : node.right;
                // Число дочерних узлов = 0, удалить node и сразу вернуть
                if (child === null) {
                    return null;
                } else {
                    // Число дочерних узлов = 1, удалить node напрямую
                    node = child;
                }
            } else {
                // Число дочерних узлов = 2, удалить следующий по симметричному обходу узел и заменить им текущий узел
                let temp = node.right;
                while (temp.left !== null) {
                    temp = temp.left;
                }
                node.right = this.removeHelper(node.right, temp.val);
                node.val = temp.val;
            }
        }
        this.updateHeight(node); // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = this.rotate(node);
        // Вернуть корневой узел поддерева
        return node;
    }

avl_tree.dart

    /* Удаление узла */
    void remove(int val) {
      root = removeHelper(root, val);
    }

    /* Рекурсивное удаление узла (вспомогательный метод) */
    TreeNode? removeHelper(TreeNode? node, int val) {
      if (node == null) return null;
      /* 1. Найти узел и удалить его */
      if (val < node.val)
        node.left = removeHelper(node.left, val);
      else if (val > node.val)
        node.right = removeHelper(node.right, val);
      else {
        if (node.left == null || node.right == null) {
          TreeNode? child = node.left ?? node.right;
          // Число дочерних узлов = 0, удалить node и сразу вернуть
          if (child == null)
            return null;
          // Число дочерних узлов = 1, удалить node напрямую
          else
            node = child;
        } else {
          // Число дочерних узлов = 2, удалить следующий по симметричному обходу узел и заменить им текущий узел
          TreeNode? temp = node.right;
          while (temp!.left != null) {
            temp = temp.left;
          }
          node.right = removeHelper(node.right, temp.val);
          node.val = temp.val;
        }
      }
      updateHeight(node); // Обновить высоту узла
      /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
      node = rotate(node);
      // Вернуть корневой узел поддерева
      return node;
    }

avl_tree.rs

    /* Удаление узла */
    fn remove(&self, val: i32) {
        Self::remove_helper(self.root.clone(), val);
    }

    /* Рекурсивное удаление узла (вспомогательный метод) */
    fn remove_helper(node: OptionTreeNodeRc, val: i32) -> OptionTreeNodeRc {
        match node {
            Some(mut node) => {
                /* 1. Найти узел и удалить его */
                if val < node.borrow().val {
                    let left = node.borrow().left.clone();
                    node.borrow_mut().left = Self::remove_helper(left, val);
                } else if val > node.borrow().val {
                    let right = node.borrow().right.clone();
                    node.borrow_mut().right = Self::remove_helper(right, val);
                } else if node.borrow().left.is_none() || node.borrow().right.is_none() {
                    let child = if node.borrow().left.is_some() {
                        node.borrow().left.clone()
                    } else {
                        node.borrow().right.clone()
                    };
                    match child {
                        // Число дочерних узлов = 0, удалить node и сразу вернуть
                        None => {
                            return None;
                        }
                        // Число дочерних узлов = 1, удалить node напрямую
                        Some(child) => node = child,
                    }
                } else {
                    // Число дочерних узлов = 2, удалить следующий по симметричному обходу узел и заменить им текущий узел
                    let mut temp = node.borrow().right.clone().unwrap();
                    loop {
                        let temp_left = temp.borrow().left.clone();
                        if temp_left.is_none() {
                            break;
                        }
                        temp = temp_left.unwrap();
                    }
                    let right = node.borrow().right.clone();
                    node.borrow_mut().right = Self::remove_helper(right, temp.borrow().val);
                    node.borrow_mut().val = temp.borrow().val;
                }
                Self::update_height(Some(node.clone())); // Обновить высоту узла

                /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
                node = Self::rotate(Some(node)).unwrap();
                // Вернуть корневой узел поддерева
                Some(node)
            }
            None => None,
        }
    }

avl_tree.c

    /* Удаление узла */
    // Из-за подключения stdio.h здесь нельзя использовать ключевое слово remove
    void removeItem(AVLTree *tree, int val) {
        TreeNode *root = removeHelper(tree->root, val);
    }

    /* Рекурсивное удаление узла (вспомогательная функция) */
    TreeNode *removeHelper(TreeNode *node, int val) {
        TreeNode *child, *grandChild;
        if (node == NULL) {
            return NULL;
        }
        /* 1. Найти узел и удалить его */
        if (val < node->val) {
            node->left = removeHelper(node->left, val);
        } else if (val > node->val) {
            node->right = removeHelper(node->right, val);
        } else {
            if (node->left == NULL || node->right == NULL) {
                child = node->left;
                if (node->right != NULL) {
                    child = node->right;
                }
                // Число дочерних узлов = 0, удалить node и сразу вернуть
                if (child == NULL) {
                    return NULL;
                } else {
                    // Число дочерних узлов = 1, удалить node напрямую
                    node = child;
                }
            } else {
                // Число дочерних узлов = 2, удалить следующий по симметричному обходу узел и заменить им текущий узел
                TreeNode *temp = node->right;
                while (temp->left != NULL) {
                    temp = temp->left;
                }
                int tempVal = temp->val;
                node->right = removeHelper(node->right, temp->val);
                node->val = tempVal;
            }
        }
        // Обновить высоту узла
        updateHeight(node);
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = rotate(node);
        // Вернуть корневой узел поддерева
        return node;
    }

avl_tree.kt

    /* Удаление узла */
    fun remove(_val: Int) {
        root = removeHelper(root, _val)
    }

    /* Рекурсивное удаление узла (вспомогательный метод) */
    fun removeHelper(n: TreeNode?, _val: Int): TreeNode? {
        var node = n ?: return null
        /* 1. Найти узел и удалить его */
        if (_val < node._val)
            node.left = removeHelper(node.left, _val)
        else if (_val > node._val)
            node.right = removeHelper(node.right, _val)
        else {
            if (node.left == null || node.right == null) {
                val child = if (node.left != null)
                    node.left
                else
                    node.right
                // Число дочерних узлов = 0, удалить node и сразу вернуть
                if (child == null)
                    return null
                // Число дочерних узлов = 1, удалить node напрямую
                else
                    node = child
            } else {
                // Число дочерних узлов = 2, удалить следующий по симметричному обходу узел и заменить им текущий узел
                var temp = node.right
                while (temp!!.left != null) {
                    temp = temp.left
                }
                node.right = removeHelper(node.right, temp._val)
                node._val = temp._val
            }
        }
        updateHeight(node) // Обновить высоту узла
        /* 2. Выполнить вращение, чтобы снова сбалансировать поддерево */
        node = rotate(node)
        // Вернуть корневой узел поддерева
        return node
    }

avl_tree.rb

    ### Удаление узла ###
    def remove(val)
      @root = remove_helper(@root, val)
    end

    ### Удаление узла ###
    def remove(val)
      @root = remove_helper(@root, val)
    end

    # ## Рекурсивное удаление узла (вспомогательный метод) ###
    def remove_helper(node, val)
      return if node.nil?
      # 1. Найти узел и удалить его
      if val < node.val
        node.left = remove_helper(node.left, val)
      elsif val > node.val
        node.right = remove_helper(node.right, val)
      else
        if node.left.nil? || node.right.nil?
          child = node.left || node.right
          # Число дочерних узлов = 0, удалить node и сразу вернуть
          return if child.nil?
          # Число дочерних узлов = 1, удалить node напрямую
          node = child
        else
          # Число дочерних узлов = 2, удалить следующий по симметричному обходу узел и заменить им текущий узел
          temp = node.right
          while !temp.left.nil?
            temp = temp.left
          end
          node.right = remove_helper(node.right, temp.val)
          node.val = temp.val
        end
      end
      # Обновить высоту узла
      update_height(node)
      # 2. Выполнить вращение, чтобы снова сбалансировать поддерево
      rotate(node)
    end

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

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

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

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

##### Оставляйте свои идеи, вопросы и предложения в комментариях