Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

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

Разность между высотами левого и правого поддерева для любого узла называется коэффициентом баланса узла.

Свойство

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

Балансировка AVL-дерева

LL-поворот

RR-поворот

LR-поворот

RL-поворот

Python

Итератор

class Iterator:
    """
    итератор по дереву
    """
    def __init__(self, _node):
        """

        :param _node: корень дерева
        :variable stack: стек для хранения уже пройденых вершин
        """
        self.stack = []
        self.node = _node

    def __iter__(self):
        return self

    def __next__(self):
        """
        итератор по всем вершинам дерева, от большей к меньшей
        :return: данные который хранит вершина
        """
        while self.node or len(self.stack) > 0:
            if self.node:
                self.stack.append(self.node)
                self.node = self.node.left
            else:
                self.node = self.stack.pop()
                result = self.node.data
                self.node = self.node.right
                return result
        raise StopIteration

Вершина

from Iterator import Iterator

class Node:
    """
    класс элемента дерева
    """

    def __init__(self, _key, _data):
        """
        конструктор класса
        :param _key: ключ по которому идёт сравнение
        :param _data: данные пользователя
        :variable height высота элемента
        :variable left левое поддерева
        :variable right правое поддерево
        """
        self.key = _key
        self.data = _data
        self.height: int = 1
        self.left = None
        self.right = None

    def __iter__(self):
        return Iterator(self)

    def get_height(self, node):
        """

        :param node: элемент дерева
        :return: высоту элемента дерева
        """
        if node:
            return node.height
        else:
            return 0

    def get_balance_factor(self, node):
        """

        :param node: элемент дерева
        :return: коэффицент баланса дерева
        """
        if node:
            return node.get_height(node.left) - node.get_height(node.right)
        else:
            return 0

    def fix_height(self, node):
        """
        исправляет высоту вершины
        :param node: элемент дерева
        """
        node.height = max(node.left.height if node.left else 0, node.right.height if node.right else 0) + 1
        pass

    def right_rotate(self, node):
        """
        правый поворот
        :param node: корень поддерева нуждающегося в балансировке
        :return: новый корень поддерева
        """
        q: Node = node.right
        node.right = q.left
        q.left = node
        q.fix_height(q)
        node.fix_height(node)
        return q

    def left_rotate(self, node):
        """
        левый поворот
        :param node: корень поддерева нуждающегося в балансировке
        :return: новый корень поддерева
        """
        q: Node = node.left
        node.left = q.right
        q.right = node
        q.fix_height(q)
        node.fix_height(node)
        return q

    def make_balance(self, node):
        """
        проверяет необходимость балансировки
        :param node: корень поддерева нуждающегося в балансировке
        :return: новый корень
        """
        node.fix_height(node)
        if self.get_balance_factor(node) > 1:
            if self.get_balance_factor(node.left) < 0:
                node.left = node.right_rotate(node.left)
            return node.left_rotate(node)

        if self.get_balance_factor(node) < -1:
            if self.get_balance_factor(node.right) > 0:
                node.right = node.left_rotate(node.right)
            return node.right_rotate(node)

        return node

AVL-Дерево

from Node import Node
from Iterator import Iterator

class AVLTree:

    def __init__(self, __key=None):
        """

        :param __key: компаратор
        :variable root: корень дерева
        """
        self.__root = None
        self.__key = __key if __key is not None else lambda x:x

    def __iter__(self):
        return Iterator(self.__root)

    def find_node(self, key):
        """
        поиск вершины, функция для пользователя
        :param key: ключ который необходимо найти
        :return: данные ключа
        """
        return self.__find_node_recursive(self.__root, key)

    def __find_node_recursive(self, root, key):
        """
        рекурсивная функция поиска вершины
        :param root: корень поддерева
        :param key: ключ которым необходимо найти
        :return: данные найденой вершины
        """
        if root:
            if key == root.key:
                return root.data
            if key < root.key:
                return self.__find_node_recursive(root.left, key)
            else:
                return self.__find_node_recursive(root.right, key)
        else:
            raise AttributeError("no such value")

    def find_min(self, root):
        """
        функция поиска минимального элемента
        :param root: корень поддерева
        :return: найденный элемент
        """
        if root.left:
            return self.find_min(root.left)
        else:
            return root

    def delete_min(self, root):
        """
        удаление минимального элемента из дерева
        :param root: корень текущего поддеерева
        :return: корень поддерева, с удалённым элементом
        """
        if root.left:
            root.left = self.delete_min(root.left)
        if not root.left:
            return root.right
        return root.make_balance(root)

    def insert_node(self, key, data):
        """
        функция всавки для поьзователя
        :param key: ключ нового элемента
        :param data: данные нового элемента
        :return: корень дерева с вставленным элементом
        """
        self.__root = self.__insert_node_recursive(self.__root, key, data)

    def __insert_node_recursive(self, root, key, data):
        """
        вставка элемента
        :param root: корень поддерева
        :param key: ключ нового элемента
        :param data: данные нового элемента
        :return: корень дерева с вставленным элементом
        """
        if not root:
            return Node(key, data)
        if key < root.key:
            root.left = self.__insert_node_recursive(root.left, key, data)
        if key >= root.key:
            root.right = self.__insert_node_recursive(root.right, key, data)
        return root.make_balance(root)

    def delete_node(self, key):
        """
        функция удаления для пользователя
        :param key: ключ уаляемой вершины
        :return: корень дерева с удалённой вершиной
        """
        self.__root = self.__delete_node_recursive(self.__root, key)

    def __delete_node_recursive(self, root, key):
        """
        функция удаления
        :param root: корень поддерева
        :param key: ключ удаляемой вершины
        :return: корень дерева с удалённой вершиной
        """
        if not root:
            return 0
        if key < root.key:
            root.left = self.__delete_node_recursive(root.left, key)
        if key >= root.key:
            root.right = self.__delete_node_recursive(root.right, key)
        if key == root.key:
            left = root.left
            right = root.right
            if not right:
                return left
            min = self.find_min(right)
            min.right = self.delete_min(right)
            min.left = left
            return min.make_balance(min)
        return root.make_balance(root)

C++ Олимпиадный

#include <iostream>
#include <vector>
#include <stack>

struct N {
    int k;
    int height;
    N *left;
    N *right;

    N(int _k) :
            k(_k),
            height(1),
            left(nullptr),
            right(nullptr) {}
};

int GH(N* node){
    if(node)
        return node->height;
    else
        return 0;
}

int BF(N* root){
    if(root)
        return (root->left ? GH(root->left) : 0) - (root->right ? GH(root->right) : 0);
    else
        return 0;
}

void H(N* root){
    root->height = (GH(root->left) > GH(root->right) ? GH(root->left) : GH(root->right)) + 1;
}

N *L(N *n) {
    N *q = n->left;
    n->left = q->right;
    q->right = n;
    H(n);
    H(q);
    return q;
}

N *R(N *n) {
    N *q = n->right;
    n->right = q->left;
    q->left = n;
    H(n);
    H(q);
    return q;
}

N *B(N *root) {
    int balance = BF(root);
    int left_balance = BF(root->left);
    int right_balance = BF(root->right);

    if (balance > 1 && left_balance >= 0)
        return L(root);
    if (balance < -1 && right_balance <= 0)
        return R(root);
    if (balance > 1 && left_balance < 0) {
        root->left = R(root->left);
        return L(root);
    }
    if (balance < -1 && right_balance > 0) {
        root->right = L(root->right);
        return R(root);
    }
    return root;
}

N *Ins(N *root, int k) {
    if (root == nullptr)
        return new N(k);
    if (k < root->k) {
        root->left = Ins(root->left, k);
    } else {
        root->right = Ins(root->right, k);
    }

    H(root);

    return B(root);

}

N *RM(N *root) {
    if (root->left == nullptr) return root->right;
    else root->left = RM(root->left);
    H(root);
    return B(root);
}

N *FM(N *root) {
    return root->left ? FM(root->left) : root;
}

N *D(N *root, int k) {
    if (root == nullptr) return nullptr;
    if (k < root->k) root->left = D(root->left, k);
    if (k > root->k) root->right = D(root->right, k);
    if (k == root->k) {
        N *left = root->left;
        N *right = root->right;
        delete root;
        if (right == nullptr) return left;
        N *min = FM(right);
        min->right = RM(right);
        min->left = left;
        H(min);
        return B(min);
    }
    H(root);
    return B(root);
}

int Search(N *root, int k) {
    if (k == root->k) {
        return root->k;
    }
    if (k < root->k)return Search(root->left, k);
    if (k > root->k)return Search(root->right, k);
    else
        throw std::invalid_argument("No such value");
}

std::vector<int> Traverse(N *node) {
    std::vector<int> v;
    std::stack<N*> s;
    while (node || size(s) > 0) {
        if (node) {
            s.push(node);
            node = node->left;
        } else {
            node = s.top();
            s.pop();
            v.push_back(node->k);
            node = node->right;
        }
    }
    return v;
}
  
  
# С++ Продуктовый
```cpp
template<typename T, typename K, typename NodeComparator>
AVL_tree<T, K, NodeComparator>::AVLNode::AVLNode(const K &_key, const T &_data):// Конструктор структуры
        key(_key),
        data(_data),
        height(1),
        left(nullptr),
        right(nullptr){}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::AVLNode*  AVL_tree<T, K, NodeComparator>::FindMinRecursive(AVLNode* node){
    return node->left?FindMinRecursive(node->left):node;
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::AVLNode* AVL_tree<T, K, NodeComparator>::InsertNodeRecursive(AVLNode *node, const K &key, const T &data) {
    if (node == nullptr)
        return new AVLNode(key, data);
    if (comparator(key, node->key)) {
        //node->height++;
        node->left = InsertNodeRecursive(node->left, key, data);
    }
    else if (!comparator(key, node->key)){
        //node->height++;
        node->right = InsertNodeRecursive(node->right, key, data);
    }
    return MakeBalance(node);
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::AVLNode* AVL_tree<T, K, NodeComparator>::DeleteNodeRecursive(AVLNode* node, const K &key){
    if(node == nullptr) return 0;
    if(comparator(key, node->key)) node->left = DeleteNodeRecursive(node->left, key);
    if(!comparator(key,  node->key)) node->right = DeleteNodeRecursive(node->right, key);
    if(key == node->key){
        AVLNode* left = node->left;
        AVLNode* right = node->right;
        delete node;
        if(right == nullptr) return left;
        AVLNode* min = FindMinRecursive(right);
        min->right = RemoveMin(right);
        min->left = left;
        return MakeBalance(min);
    }
    return MakeBalance(node);
}

template<typename T, typename K, typename NodeComparator>
void AVL_tree<T, K, NodeComparator>::clear(AVLNode* node){
    if (node != nullptr) {
        clear(node->left);
        clear(node->right);
        delete node;
    }
}

template<typename T, typename K, typename NodeComparator>
int AVL_tree<T, K, NodeComparator>::GetHeight(AVLNode* node)
{
    return node?node->height:0;
}

template<typename T, typename K, typename NodeComparator>
int AVL_tree<T, K, NodeComparator>::GetBalanceFactor(AVL_tree::AVLNode *node) {
    return GetHeight(node->left) - GetHeight(node->right);
}

template<typename T, typename K, typename NodeComparator>
void AVL_tree<T, K, NodeComparator>::FixHeight(AVLNode* node){
    node->height = ((GetHeight(node->left) > GetHeight(node->right)) ? GetHeight(node->left) : GetHeight(node->right)) + 1;
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::AVLNode* AVL_tree<T, K, NodeComparator>::RemoveMin(AVLNode* node){
    if(node->left == nullptr) return node->right;
    else node->left = RemoveMin(node->left);
    return MakeBalance(node);
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::AVLNode* AVL_tree<T, K, NodeComparator>::LeftRotation(AVLNode *node){
    AVLNode *q = node->left;
    node->left = q->right;
    q->right = node;
    FixHeight(node);
    FixHeight(q);
    return q;
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::AVLNode* AVL_tree<T, K, NodeComparator>::RightRotation(AVLNode *node){
    AVLNode *q = node->right;
    node->right = q->left;
    q->left = node;
    FixHeight(node);
    FixHeight(q);
    return q;
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::AVLNode* AVL_tree<T, K, NodeComparator>::MakeBalance(AVLNode* node){
    FixHeight(node);
    int balance_factor = GetBalanceFactor(node);
    if(balance_factor > 1){
        if(GetBalanceFactor(node->left) < 0){
            node->left = RightRotation(node->left);
        }
        return LeftRotation(node);
    }

    if(balance_factor < -1){
        if(GetBalanceFactor(node->right) > 0){
            node->right = LeftRotation(node->right);
        }
        return RightRotation(node);
    }
    return node;
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::AVLNode *AVL_tree<T, K, NodeComparator>::FindNodeRecursive(AVLNode* root, const K &key){
    if(root) {
        if (key == root->key) {
            return root;
        }
        if (key < root->key) {
            return FindNodeRecursive(root->left, key);
        }
        if (key > root->key) {
            return FindNodeRecursive(root->right, key);
        }
    }
    else
        return nullptr;
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::AVLNode *AVL_tree<T, K, NodeComparator>::copy(AVLNode* node){
    if(!node){
        return nullptr;
    }
    auto newNode = new AVLNode(node->key, node->data);
    newNode->height = node->height;
    newNode->left = copy(node->left);
    newNode->right = copy(node->right);
    return newNode;
}

template<typename T, typename K, typename NodeComparator>
AVL_tree<T, K, NodeComparator>::AVL_tree() : root(nullptr){};

template<typename T, typename K, typename NodeComparator>
AVL_tree<T, K, NodeComparator>::Iterator::Iterator(const Iterator &other){
    this->node = other.node;
    this->post = other.post;
    this->prev = other.prev;
}

template<typename T, typename K, typename NodeComparator>
std::pair<K, T> AVL_tree<T, K, NodeComparator>::Iterator::operator*() const
{
    if(node == nullptr)
        throw std::invalid_argument("No such value");
    std::pair<K, T> A;
    A.first = node->key;
    A.second = node->data;
    return A;
}

template<typename T, typename K, typename NodeComparator>
bool AVL_tree<T, K, NodeComparator>::Iterator::operator==(const Iterator&other){
    return node == other.node;
}

template<typename T, typename K, typename NodeComparator>
bool AVL_tree<T, K, NodeComparator>::Iterator::operator!=(const Iterator&other){
    return node != other.node;
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::Iterator AVL_tree<T, K, NodeComparator>::Iterator::operator++()
{
    node = node->right;
    while (node || size(post) > 0) {
        if (node) {
            post.push(node);
            node = node->left;
        } else {
            node = post.top();
            post.pop();
            return *this;
        }
    }
    return nullptr;
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::Iterator AVL_tree<T, K, NodeComparator>::Iterator::operator--()
{
    node = node->left;
    while (node || size(prev) > 0) {
        if (node) {
            prev.push(node);
            node = node->right;
        } else {
            node = prev.top();
            prev.pop();
            return *this;
        }
    }
    return nullptr;
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::Iterator& AVL_tree<T, K, NodeComparator>::Iterator::operator=(const Iterator &other){
    this->node = other.node;
    this->post = other.post;
    this->prev = other.prev;
    return *this;
}

template<typename T, typename K, typename NodeComparator>
AVL_tree<T, K, NodeComparator>::AVL_tree(const AVL_tree &other){
    this->root = copy(other.root);
    this->comparator = other.comparator;
}

template<typename T, typename K, typename NodeComparator>
AVL_tree<T, K, NodeComparator> &AVL_tree<T, K,NodeComparator>::operator=(const AVL_tree &other) {
    this->root = copy(other.root);
    this->comparator = other.comparator;
    return *this;
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::Iterator AVL_tree<T, K, NodeComparator>::Iterator::begin() {
    while (node) {
        post.push(node);
        node = node->left;
    }
    node = post.top();
    post.pop();
    return *this;
}
template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::Iterator AVL_tree<T, K, NodeComparator>::Iterator::end(){
    return Iterator(nullptr);
}

template<typename T, typename K, typename NodeComparator>
std::pair<K, T> AVL_tree<T, K, NodeComparator>::RIterator::operator*() const
{
    if(node == nullptr)
        throw std::invalid_argument("No such value");
    std::pair<K, T> A;
    A.first = node->key;
    A.second = node->data;
    return A;
    //return node->data;
}

template<typename T, typename K, typename NodeComparator>
AVL_tree<T, K, NodeComparator>::~AVL_tree(){
    clear(root);
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::RIterator AVL_tree<T, K, NodeComparator>::RIterator::operator++()
{
    node = node->left;
    while (node || size(post) > 0) {
        if (node) {
            post.push(node);
            node = node->right;
        } else {
            node = post.top();
            post.pop();
            return *this;
        }
    }
    return nullptr;
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::RIterator AVL_tree<T, K, NodeComparator>::RIterator::operator--()
{
    node = node->left;
    while (node || size(prev) > 0) {
        if (node) {
            prev.push(node);
            node = node->right;
        } else {
            node = prev.top();
            prev.pop();
            return *this;
        }
    }
    return nullptr;
}

template<typename T, typename K, typename NodeComparator>
bool AVL_tree<T, K, NodeComparator>::RIterator::operator==(const RIterator&other){
    return node == other.node;
}

template<typename T, typename K, typename NodeComparator>
bool AVL_tree<T, K, NodeComparator>::RIterator::operator!=(const RIterator&other){
    return node != other.node;
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::RIterator AVL_tree<T, K, NodeComparator>::RIterator::begin() {
    while (node) {
        post.push(node);
        node = node->right;
    }
    node = post.top();
    post.pop();
    return *this;
}
template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::RIterator AVL_tree<T, K, NodeComparator>::RIterator::end(){
    return RIterator(nullptr);
}

template<typename T, typename K, typename NodeComparator>
void AVL_tree<T, K, NodeComparator>::InsertNode(const K &key, const T &data){
    root = InsertNodeRecursive(root, key, data);
}

template<typename T, typename K, typename NodeComparator>
void AVL_tree<T, K, NodeComparator>::DeleteNode(int key){
    root = DeleteNodeRecursive(root, key);
}

template<typename T, typename K, typename NodeComparator>
typename AVL_tree<T, K, NodeComparator>::Iterator AVL_tree<T, K, NodeComparator>::FindNode(const K &key){
    AVLNode* node = FindNodeRecursive(root, key);
    if(Iterator(node) == end())
        throw std::invalid_argument("No such value");
    else
        return Iterator(node);
}

#ifndef AVL_TREE_AVL_TREE_H
#define AVL_TREE_AVL_TREE_H
#include <utility>
#include <stack>
#include <stdexcept>

template <typename T, typename K, typename NodeComparator = std::less<K>>
class AVL_tree{

private:

    struct AVLNode{
        /*
         * структура узла дерева
         */
        const K key;
        T data;
        int height;
        AVLNode* left;
        AVLNode* right;

        AVLNode(const K &_key, const T &_data);
    };

private:
    /*
     * корень и компратор
     */
    AVLNode *root;
    NodeComparator comparator;

public:

    class Iterator{
    /*
     * итератор по дереву
     */
    private:
        AVLNode* node;
        std::stack<AVLNode*> post;
        std::stack<AVLNode*> prev;
    public:

        Iterator(AVLNode* node):node(node){};
        Iterator(const Iterator &other);

        Iterator& operator=(const Iterator &other);

        std::pair<K, T> operator*() const;

        Iterator operator++();

        Iterator operator--();

        bool operator==(const Iterator&other);

        bool operator!=(const Iterator&other);

        Iterator begin();
        Iterator end();
    };

    class RIterator{
    /*
     * обратный итератор по дереву
     */
    private:
        AVLNode* node;
        std::stack<AVLNode*> post;
        std::stack<AVLNode*> prev;
    public:

        RIterator(AVLNode* node):node(node){};
        std::pair<K, T> operator*() const;

        RIterator operator++();

        RIterator operator--();

        bool operator==(const RIterator&other);

        bool operator!=(const RIterator&other);

        RIterator begin();
        RIterator end();
    };

    RIterator r_begin(){
        if(root)
            return RIterator(root).begin();
        else
            return nullptr;
    }
    RIterator r_end(){
        return RIterator(nullptr).end();
    }

    Iterator begin() {
        if(root)
            return Iterator(root).begin();
        else
            return nullptr;
    }
    Iterator end(){
        return Iterator(root).end();
    }

public:
    AVL_tree();

    AVL_tree(const AVL_tree &other);

    AVL_tree &operator=(const AVL_tree& other);

    ~AVL_tree();

public: // functions

    Iterator FindNode(const K &key);

    void InsertNode(const K &key, const T &data);

    void DeleteNode(int key);

private:

    AVLNode* FindNodeRecursive(AVLNode* root, const K &key);

    AVLNode* FindMinRecursive(AVLNode* node);

    AVLNode* InsertNodeRecursive(AVLNode *node, const K &key, const T &data);

    AVLNode* DeleteNodeRecursive(AVLNode* node, const K &key);

    AVLNode* copy(AVLNode* node);

    void clear(AVLNode* node);

    int GetHeight(AVLNode* node);

    int GetBalanceFactor(AVLNode* node);

    void FixHeight(AVLNode* node);

    AVLNode* RemoveMin(AVLNode* node);

    AVLNode* LeftRotation(AVLNode *node);

    AVLNode* RightRotation(AVLNode *node);

    AVLNode* MakeBalance(AVLNode* node);

};

#include "AVL_tree.tpp"
#include "AVL_tree_private.tpp"
#endif //AVL_TREE_AVL_TREE_H