查看: 378|回复: 0

二叉树(五)平衡二叉树(AVL树)

[复制链接]
发表于 2020-2-6 04:50:40 | 显示全部楼层 |阅读模式
均衡二叉树(AVL树)的自均衡(LL->R、RR->L、LR->LR、RL->RL)、增、删 等操作。


main.cpp:
  1. #include #include "AVLTree.h"using namespace std;int main(){    AVLTree avl;    auto Add = [&avl](int _key)    {        cout 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;}templatevoid AVLTree::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;}templatevoid AVLTree::LR_LR(Node* _root){    RR_L(_root->left);    LL_R(_root);    if (_root->left == nullptr) _root->bf = 1;}templatevoid AVLTree::RL_RL(Node* _root){    LL_R(_root->right);    RR_L(_root);    if (_root->right == nullptr) _root->bf = -1;}templatevoid AVLTree::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;    }}templatetemplatevoid AVLTree::insert(_Iter _it1, _Iter _it2){    while (_it1 != _it2)    {        insert(*_it1);        ++_it1;    }}templatesize_t AVLTree::erase(const _Ty& _key){    size_t n = 0;    Node* del = find(_key);    if (del != nullptr)    {        ++n;        erase(del);    }    return n;}templatevoid AVLTree::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;            }        }    }}templatetypename AVLTree::Node* AVLTree::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);}templatetypename AVLTree::Node* AVLTree::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;}templatetypename AVLTree::Node* AVLTree::maximum(Node* _node) const{    if (_node == nullptr) return _node;    while (_node->right != nullptr)        _node = _node->right;    return _node;}templatetypename AVLTree::Node* AVLTree::minimum(Node* _node) const{    if (_node == nullptr) return _node;    while (_node->left != nullptr)        _node = _node->left;    return _node;}#endif // !__AVLTREE_H__
复制代码

相关技术服务需求,请联系管理员和客服QQ:2753533861或QQ:619920289
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

帖子推荐:
客服咨询

QQ:2753533861

服务时间 9:00-22:00

快速回复 返回顶部 返回列表