C++实现AVL树的四种旋转

C++实现AVL树的四种旋转

结构

template
struct AVLNode{
    T data;
    int height;
    AVLNode* lchild, *rchild;
    AVLNode(T dt, AVLNode* l, AVLNode* r):data(dt),lchild(l),rchild(r){}
};

template
class AVLTree{
    public:
        AVLTree(){
            root = nullptr;
        }
        ~AVLTree(){
            Destory(root);
        }
        void Insert(T data){
            _insert(root, data);
        }

        bool Search(T data){
            //return _searchRecursion(root,data);
        
            return _searchNotRecursion(root, data);
        }
        
        bool DeleteData(T data){
            return _deleteData(root, data);
        }

        AVLNode* Left_Rotation(AVLNode* pRoot);       // 左旋
        AVLNode* Right_Rotation(AVLNode* pRoot);      // 右旋
        AVLNode* LR_Rotation(AVLNode* pRoot);         // 先左旋后右旋
        AVLNode* RL_Rotation(AVLNode* pRoot);         // 先右旋后左旋
        
    private:
        AVLNode* root;
        void _insert(AVLNode* pRoot, T data);
        bool _searchRecursion(AVLNode* pRoot, T data);   //递归搜索
        bool _searchNotRecursion(AVLNode* pRoot, T data);//非递归搜索
        void Destory(AVLNode* pRoot);
        bool _deleteData(AVLNode* pRoot, T data);
};

四种旋转场景

通过比较左右子树的高度差(即平衡因子)来反映是否平衡

 

template
AVLNode* AVLTree::Left_Rotation(AVLNode* pRoot)
{
    AVLNode* p = pRoot->rchild;
    pRoot->rchild = p->lchild;
    p->lchild = pRoot;

    pRoot->height = max(pRoot->lchild->height, pRoot->rchild->height)+1;
    p->height = max(p->lchild->height, p->rchild->height)+1;
    return p;
}

template
AVLNode* AVLTree::Right_Rotation(AVLNode* pRoot)
{
    AVLNode* p = pRoot->lchild;
    pRoot->lchild = p->rchild;
    p->rchild = pRoot;

    pRoot->height = max(pRoot->lchild->height, pRoot->rchild->height)+1;
    p->height = max(p->lchild->height, p->rchild->height)+1;
    return p;
}

template
AVLNode* AVLTree::LR_Rotation(AVLNode* pRoot)
{
    Left_Rotation(pRoot->rchild);
    Right_Rotation(pRoot);

    return pRoot->rchild;
}

template
AVLNode* AVLTree::RL_Rotation(AVLNode* pRoot)
{
    Right_Rotation(pRoot->lchild);
    Left_Rotation(pRoot);

    return pRoot->lchild;
}