平衡二叉树（AVL树）的自平衡（LL->R、RR->L、LR->LR、RL->RL）、增、删 等操作。

 

 

main.cpp：

#include <iostream>
#include "AVLTree.h"
using namespace std;

int main()
{
    AVLTree<int> avl;

    auto Add = [&avl](int _key)
    {
        cout << "Add " << _key << ":" << endl;
        avl.insert(_key);
        avl.levelTraversal();
        cout << endl << "size: " << avl.size() << "  level: " << avl.level() << endl << endl;
    };
    auto il = { 0,1,4,2,5,3,6 };
    for (auto& key : il)
        Add(key);
    auto Del = [&avl](int _key)
    {
        cout << "Del " << _key << ":" << endl;
        avl.erase(_key);
        avl.levelTraversal();
        cout << endl << "size: " << avl.size() << "  level: " << avl.level() << endl << endl;
    };
    Del(4); Del(1); Del(5); Del(6); Del(2);

    return 0;
}

 

AVLTree.h：

#pragma once
#ifndef __AVLTREE_H__
#define __AVLTREE_H__


#include <queue>
#include <initializer_list>
template<typename _Ty>
class AVLTree
{
private:
    struct Node
    {
        _Ty key;
        int bf = 0;
        Node* left = nullptr;
        Node* right = nullptr;
        Node* parent = nullptr;
        Node(const _Ty& _key) :key(_key) {}
    };

public:
    AVLTree() = default;
    template<typename _Iter>
    AVLTree(_Iter, _Iter);
    AVLTree(const std::initializer_list<_Ty>&);
    AVLTree(const AVLTree<_Ty>&);
    AVLTree(AVLTree<_Ty>&&) noexcept;

    ~AVLTree() { clear(root); }
    void clear() { clear(root); root = nullptr; }
    bool empty() const { return size_n == 0; }
    size_t size() const { return size_n; }
    Node* getRoot() const { return root; }
    void show() const { show(root); }
    void showPreorder() const { showPreorder(root); }
    void levelTraversal() const { levelTraversal(root); }
    size_t level() const;
    void swap(AVLTree<_Ty>&);

    void insert(const _Ty&);
    template<typename _Iter>
    void insert(_Iter, _Iter);
    size_t erase(const _Ty&);
    void erase(Node*);

    Node* find(const _Ty& _key) const { return find(root, _key); }
    Node* iterative_find(const _Ty& _key) const { return iterative_find(root, _key); }
    Node* maximum() const { return maximum(root); }
    Node* minimum() const { return minimum(root); }

private:
    void copy(Node*);
    void clear(Node*&);
    void show(Node*) const;
    void showPreorder(Node*) const;
    void levelTraversal(Node*) const;
    Node* find(Node*, const _Ty&) const;
    Node* iterative_find(Node*, const _Ty&) const;
    Node* maximum(Node*) const;
    Node* minimum(Node*) const;
    void LL_R(Node*);
    void RR_L(Node*);
    void LR_LR(Node*);
    void RL_RL(Node*);

private:
    size_t size_n = 0;
    Node* root = nullptr;
};

template<typename _Ty>
template<typename _Iter>
AVLTree<_Ty>::AVLTree(_Iter _it1, _Iter _it2)
{
    while (_it1 != _it2)
    {
        insert(*_it1);
        ++_it1;
    }
}

template<typename _Ty>
AVLTree<_Ty>::AVLTree(const std::initializer_list<_Ty>& _il)
{
    for (const auto& key : _il) insert(key);
}

template<typename _Ty>
AVLTree<_Ty>::AVLTree(const AVLTree<_Ty>& _right)
{
    copy(_right.getRoot());
}

template<typename _Ty>
AVLTree<_Ty>::AVLTree(AVLTree<_Ty>&& _right) noexcept
{
    root = _right.root;
    size_n = _right.size_n;
    _right.root = nullptr;
    _right.size_n = 0;
}

template<typename _Ty>
size_t AVLTree<_Ty>::level() const
{
    if (root == nullptr) 0;
    size_t n = 0;
    std::queue<Node*> nodePointers;
    nodePointers.push(root);
    while (!nodePointers.empty())
    {
        Node* levelBegin = nodePointers.front();
        Node* levelEnd = nodePointers.back();
        Node* cur = levelBegin;
        while (true)
        {
            if (cur->left != nullptr) nodePointers.push(cur->left);
            if (cur->right != nullptr) nodePointers.push(cur->right);
            if (cur == levelEnd)
                break;
            nodePointers.pop();
            cur = nodePointers.front();
        }
        nodePointers.pop();
        ++n;
    }
    return n;
}

template<typename _Ty>
void AVLTree<_Ty>::copy(Node* _node)
{
    if (_node == nullptr) return;
    insert(_node->key);
    copy(_node->left);
    copy(_node->right);
}

template<typename _Ty>
void AVLTree<_Ty>::clear(Node*& _node)
{
    if (_node == nullptr) return;
    clear(_node->left);
    clear(_node->right);
    delete _node;
    _node = nullptr;
    --size_n;
}

template<typename _Ty>
void AVLTree<_Ty>::show(Node* _node) const
{
    if (_node == nullptr) return;
    show(_node->left);
    std::cout << _node->key << " ";
    show(_node->right);
}

template<typename _Ty>
void AVLTree<_Ty>::showPreorder(Node* _node) const
{
    if (_node == nullptr) return;
    std::cout << _node->key << " ";
    show(_node->left);
    show(_node->right);
}

template<typename _Ty>
void AVLTree<_Ty>::levelTraversal(Node* _node) const
{
    if (_node == nullptr) return;
    std::queue<Node*> nodePointers;
    nodePointers.push(_node);
    while (!nodePointers.empty())
    {
        Node* cur = nodePointers.front();
        std::cout << cur->key << " ";
        if (cur->left != nullptr) nodePointers.push(cur->left);
        if (cur->right != nullptr) nodePointers.push(cur->right);
        nodePointers.pop();
    }
}

template<typename _Ty>
void AVLTree<_Ty>::swap(AVLTree<_Ty>& _right)
{
    std::swap(root, _right->root);
    std::swap(size_n, _right->size_n);
}

template<typename _Ty>
void AVLTree<_Ty>::LL_R(Node* _root)
{
    Node* leftNode = _root->left;
    if (_root->parent != nullptr)
    {
        if (_root->parent->left == _root) _root->parent->left = leftNode;
        else _root->parent->right = leftNode;
    }
    else root = leftNode;
    leftNode->parent = _root->parent;
    _root->left = leftNode->right;
    if (leftNode->right != nullptr) leftNode->right->parent = _root;
    _root->parent = leftNode;
    leftNode->right = _root;
    _root->bf = leftNode->bf = 0;
}

template<typename _Ty>
void AVLTree<_Ty>::RR_L(Node* _root)
{
    Node* rightNode = _root->right;
    if (_root->parent != nullptr)
    {
        if (_root->parent->right == _root) _root->parent->right = rightNode;
        else _root->parent->left = rightNode;
    }
    else root = rightNode;
    rightNode->parent = _root->parent;
    _root->right = rightNode->left;
    if (rightNode->left != nullptr) rightNode->left->parent = _root;
    _root->parent = rightNode;
    rightNode->left = _root;
    _root->bf = rightNode->bf = 0;
}

template<typename _Ty>
void AVLTree<_Ty>::LR_LR(Node* _root)
{
    RR_L(_root->left);
    LL_R(_root);
    if (_root->left == nullptr) _root->bf = 1;
}

template<typename _Ty>
void AVLTree<_Ty>::RL_RL(Node* _root)
{

    LL_R(_root->right);
    RR_L(_root);
    if (_root->right == nullptr) _root->bf = -1;
}

template<typename _Ty>
void AVLTree<_Ty>::insert(const _Ty& _key)
{
    ++size_n;
    if (root == nullptr)
    {
        root = new Node(_key);
        return;
    }
    Node* temp = root;
    while (true)
    {
        if (_key == temp->key)
        {
            --size_n;
            return;
        }
        else if (_key < temp->key && temp->left != nullptr)
            temp = temp->left;
        else if (_key < temp->key && temp->left == nullptr)
            break;
        else if (_key > temp->key&& temp->right != nullptr)
            temp = temp->right;
        else
            break;
    }
    Node* newNode = new Node(_key);
    newNode->parent = temp;
    if (_key < temp->key)
    {
        temp->left = newNode;
        temp->bf += -1;
    }
    else
    {
        temp->right = newNode;
        temp->bf += 1;
    }
    if (temp->left != nullptr && temp->right != nullptr) return;
    Node* pa = temp->parent;
    while (pa != nullptr)
    {
        if (temp == pa->left)
            pa->bf += -1;
        else
            pa->bf += 1;
        if (pa->bf == -2)
        {
            if (temp->bf == -1) LL_R(pa);
            else LR_LR(pa);
            break;
        }
        else if (pa->bf == 2)
        {
            if (temp->bf == -1) RL_RL(pa);
            else RR_L(pa);
            break;
        }
        temp = pa;
        pa = pa->parent;
    }
}

template<typename _Ty>
template<typename _Iter>
void AVLTree<_Ty>::insert(_Iter _it1, _Iter _it2)
{
    while (_it1 != _it2)
    {
        insert(*_it1);
        ++_it1;
    }
}

template<typename _Ty>
size_t AVLTree<_Ty>::erase(const _Ty& _key)
{
    size_t n = 0;
    Node* del = find(_key);
    if (del != nullptr)
    {
        ++n;
        erase(del);
    }
    return n;
}

template<typename _Ty>
void AVLTree<_Ty>::erase(Node* _node)
{
    --size_n;
    Node* pa = nullptr;
    Node* temp = nullptr;
    if (_node->left == nullptr && _node->right == nullptr)
    {
        if (_node->parent == nullptr)
        {
            root = nullptr;
            delete _node;
            return;
        }
        if (_node == _node->parent->left)
        {
            _node->parent->left = nullptr;
            _node->parent->bf += 1;
            temp = _node->parent->right;
        }
        else
        {
            _node->parent->right = nullptr;
            _node->parent->bf += -1;
            temp = _node->parent->left;
        }
        pa = _node->parent;
        delete _node;
    }
    else if (!(_node->left != nullptr && _node->right != nullptr))
    {
        if (_node->parent == nullptr)
        {
            if (_node->left != nullptr) root = _node->left;
            else root = _node->right;
            root->parent = nullptr;
            delete _node;
            return;
        }
        if (_node == _node->parent->left)
        {
            _node->parent->left = _node->left == nullptr ? _node->right : _node->left;
            if (_node->left != nullptr) _node->left->parent = _node->parent;
            else _node->right->parent = _node->parent;
            _node->parent->bf += 1;
            temp = _node->parent->right;
        }
        else
        {
            _node->parent->right = _node->left == nullptr ? _node->right : _node->left;
            if (_node->left != nullptr) _node->left->parent = _node->parent;
            else _node->right->parent = _node->parent;
            _node->parent->bf += -1;
            temp = _node->parent->left;
        }
        pa = _node->parent;
        delete _node;
    }
    else
    {
        ++size_n;
        if (_node->right != nullptr)
        {
            Node* de = minimum(_node->right);
            _node->key = de->key;
            erase(de);
        }
        else if (_node->left != nullptr)
        {
            Node* de = maximum(_node->left);
            _node->key = de->key;
            erase(de);
        }
    }
    if (pa != nullptr && pa->bf == 0)
    {
        temp = pa;
        pa = pa->parent;
        if (pa != nullptr)
        {
            if (temp == pa->left)
            {
                temp = pa->right;
                pa->bf += 1;
            }
            else
            {
                temp = pa->left;
                pa->bf += -1;
            }
        }
    }
    while (pa != nullptr)
    {
        if (pa->bf == -2)
        {
            if (temp->bf == -1 || temp->bf == 0) LL_R(pa);
            else LR_LR(pa);
        }
        else if (pa->bf == 2)
        {
            if (temp->bf == -1) RL_RL(pa);
            else RR_L(pa);
        }
        else
            break;
        bool isLeft = temp == pa->left ? 1 : 0;
        pa = temp->parent;
        if (pa != nullptr)
        {
            if (isLeft)
            {
                temp = pa->left;
                pa->bf += -1;
            }
            else
            {
                temp = pa->right;
                pa->bf += 1;
            }
        }
    }
}

template<typename _Ty>
typename AVLTree<_Ty>::Node* AVLTree<_Ty>::find(Node* _node, const _Ty& _key) const
{
    if (_node == nullptr || _node->key == _key)
        return _node;
    if (_key < _node->key)
        return find(_node->left, _key);
    else
        return find(_node->right, _key);
}

template<typename _Ty>
typename AVLTree<_Ty>::Node* AVLTree<_Ty>::iterative_find(Node* _node, const _Ty& _key) const
{
    while (_node != nullptr && _node->key != _key)
    {
        if (_key < _node->key)
            _node = _node->left;
        else
            _node = _node->right;
    }
    return _node;
}

template<typename _Ty>
typename AVLTree<_Ty>::Node* AVLTree<_Ty>::maximum(Node* _node) const
{

    if (_node == nullptr) return _node;
    while (_node->right != nullptr)
        _node = _node->right;
    return _node;
}

template<typename _Ty>
typename AVLTree<_Ty>::Node* AVLTree<_Ty>::minimum(Node* _node) const
{
    if (_node == nullptr) return _node;
    while (_node->left != nullptr)
        _node = _node->left;
    return _node;
}


#endif // !__AVLTREE_H__