欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树搜索树---AVL树插入节点

程序员文章站 2022-06-07 08:21:38
...

1.AVL树的概念:
AVL树或则是空树,或是具有下列性质的二叉搜索树

  • 它的左右子树都是AVL树;
  • 左子树和右子树的高度之差简称(平衡因子)的绝对值不超过1;

2.AVL树的实现原理
与二叉搜索树的节点插入方法相同,具体步骤如下:
二叉树搜索树---AVL树插入节点

当树不平衡时,我们需要做出旋转调整,有四种调整方法,分别为右单旋、左单旋、先左单旋再右单旋、先右单旋在左单旋

  • 左单旋
    二叉树搜索树---AVL树插入节点

  • 右单旋
    二叉树搜索树---AVL树插入节点

  • 先右旋再左旋
    二叉树搜索树---AVL树插入节点

  • 先左旋再右旋
    二叉树搜索树---AVL树插入节点

3.代码实现

#include<stdio.h>
#include<iostream>
using namespace std;

template<class k,class v>
struct AVLTreeNode
{
    AVLTreeNode(const k& key,const v& value)
        :_key(key)
        ,_value(value)
        ,_bf(0)
        ,_pLeft(NULL)
        ,_pRight(NULL)
        ,_pParent(NULL)
    {}

    AVLTreeNode<k,v>* _pLeft;
    AVLTreeNode<k,v>* _pRight;
    AVLTreeNode<k,v>* _pParent;
    k _key;
    v _value;
    int _bf;
};


template<class k,class v>
class AVLTree
{
public:
    typedef AVLTreeNode<k,v> Node;
    AVLTree()
        :_pRoot(NULL)
    {}

    bool Insert(const k& key,const v& value)//插入节点
    {
        return _Insert(key,value);
    }

    bool IsBalanceTree()
    {
        return _IsBalanceTree(_pRoot);
    }
private:
    bool _IsBalanceTree(Node* pRoot)//判断该树是否是平衡二叉树
    {
        if(pRoot == NULL)
            return true;
        size_t leftHeight = _Height(pRoot->_pLeft);
        size_t rightHeight = _Height(pRoot->_pRight);

        if(rightHeight-leftHeight != pRoot->_bf || abs(pRoot->_bf)>1)
        {
            cout<<pRoot->_key<<"-->"<<pRoot->_bf<<endl;
            return false;
        }
        return _IsBalanceTree(pRoot->_pLeft)&&_IsBalanceTree(pRoot->_pRight);
    }
    size_t _Height(Node* pRoot)
    {
        if(pRoot == NULL)
            return 0;
        if(pRoot->_pLeft == NULL && pRoot->_pRight == NULL)
            return 1;

        size_t leftHeight = _Height(pRoot->_pLeft);
        size_t rightHeight = _Height(pRoot->_pRight);

        return 1+(leftHeight > rightHeight? leftHeight:rightHeight);
    }
    bool _Insert(const k& key,const v& value)
    {
        if(_pRoot == NULL)
        {
            _pRoot = new Node(key,value);
            return true;
        }

        //找到要插入节点的位置
        Node* pCur = _pRoot;
        Node* pParent = NULL;

        while(pCur)
        {
            if(key < pCur->_key)
            {
                pParent = pCur;
                pCur = pCur->_pLeft;
            }
            else if(key > pCur->_key)
            {
                pParent = pCur;
                pCur = pCur->_pRight;
            }
            else
                return false;
        }
        //已经找到插入位置
        pCur = new Node(key,value);
        if(pParent->_key < key)
        {
            pParent->_pRight = pCur;
            pCur->_pParent = pParent;
        }
        else
        {
            pParent->_pLeft = pCur;
            pCur->_pParent = pParent;
        }


        while(pParent)
        {
            //更新平衡因子
            if(pParent->_pLeft == pCur)
                (pParent->_bf)--;
            else
                (pParent->_bf)++;

            if(pParent->_bf == 0)//pParent只有左孩子或者只有右孩子,在其空指针域插入一个节点后,平衡因子为0,
                return true;     //此时树的高度没有发生变化,该树任然是是AVL树
            else if(pParent->_bf == -1 || pParent->_bf == 1)//pParent是叶子节点,插入节点后其平衡因子可能是1或-1
            {                                             //此时树的高度可能发生了改变,我们要向上判断其祖先节点是否平衡
                pCur = pParent;
                pParent = pCur->_pParent;
            }
            else
            {
                //不满足平衡树,要做旋转处理
                if(pParent->_bf == 2)//右子树
                {
                    if(pCur->_bf == 1)//右侧
                        _RotateL(pParent);//左旋调整
                    else//左侧
                        _RotateRL(pParent);//先右旋再左旋
                }
                else//左子树
                {
                    if(pCur->_bf == -1)//左侧
                        _RotateR(pParent);
                    else//右侧
                        _RotateLR(pParent);
                }
                break;//调整完后跳出循环
            }
        }
        return true;
    }

    void InOrder()
    {
        cout<<"InOrder ";
        _InOrder(_pRoot);
        cout<<endl;
    }

private:
    void _InOrder(Node*& pRoot)
    {
        if(pRoot)
        {
            _InOrder(pRoot->_pLeft);
            cout<<pRoot->_key<<" ";
            _InOrder(pRoot->_pRight);
        }
    }
    void _RotateL(Node* pParent)
    {
        Node* pSubR = pParent->_pRight;
        Node* pSubRL =pSubR->_pLeft;

        pParent->_pRight = pSubRL;
        if(pSubRL)//情况四之一
            pSubRL->_pParent = pParent;

        pSubR->_pLeft = pParent;

        Node* pPParent = pParent->_pParent;
        pParent->_pParent = pSubR;
        if(pPParent == NULL)
        {
            _pRoot = pSubR;
            pSubR->_pParent = NULL;
        }
        else if(pPParent->_pLeft == pParent)
        {
            pPParent->_pLeft = pSubR;
            pSubR->_pParent = pPParent;
        }
        else
        {
            pPParent->_pRight = pSubR;
            pSubR->_pParent = pPParent;
        }

        //更新平衡因子
        pParent->_bf = pSubR->_bf = 0;
    }

    void _RotateR(Node* pParent)
    {
        Node* pSubL = pParent->_pLeft;
        Node* pSubLR = pParent->_pRight;

        pParent->_pLeft = pSubLR;
        if(pSubLR)
            pSubLR->_pParent = pParent;
        pSubL->_pRight = pParent;

        Node* pPParent = pParent->_pParent;
        pParent->_pParent = pSubL;

        if(pPParent == NULL)
        {
            _pRoot = pSubL;
            pSubL->_pParent = NULL;
        }
        else if(pPParent->_pLeft == pParent)
        {
            pPParent->_pLeft = pSubL;
            pSubL->_pParent = pPParent;
        }
        else
        {
            pPParent->_pRight = pSubL;
            pSubL->_pParent = pPParent;
        }
        //更新平衡因子
        pParent->_bf = pSubL->_bf = 0;
    }

    void _RotateRL(Node* pParent)//先右单旋再左单旋
    {
        Node* pSubR = pParent->_pRight;
        Node* pSubRL = pSubR->_pLeft;
        int bf = pSubRL->_bf;

        _RotateR(pParent->_pRight);
        _RotateL(pParent);

        //判断平衡因子应该如何更新
        if(bf == 1)
            pParent->_bf = -1;
        else
            pSubR->_bf = 1;
    }

    void _RotateLR(Node* pParent)//先左单旋再右单旋
    {
        Node* pSubL = pParent->_pLeft;
        Node* pSubLR = pSubL->_pRight;
        int bf = pSubLR->_bf;

        _RotateL(pParent->_pLeft);
        _RotateR(pParent);

        //判断平衡因子应该如何修改
        if(bf == 1)
            pSubL->_bf = -1;
        else
            pParent->_bf = 1;
    }

private:
    Node* _pRoot;
};

测试代码:

void funtest()
{
    int array[] = {2,1,4,3,5,6};//测试左单旋
    AVLTree<int,int> bst;
    for(size_t idx= 0 ;idx < sizeof(array)/sizeof(array[0]);++idx)
        bst.Insert(array[idx],idx);

    AVLTree<int,int> bst1;
    int array1[] = {5,3,6,2,1,4};//测试右单旋
    for(size_t idx1= 0 ;idx1 < sizeof(array1)/sizeof(array1[0]);++idx1)
        bst1.Insert(array1[idx1],idx1);
}

void funtest1()
{
    int array[] = {3,2,1,4,5,6,7,10,9,8};//测试左单旋
    AVLTree<int,int> bst;
    for(size_t idx= 0 ;idx < sizeof(array)/sizeof(array[0]);++idx)
        bst.Insert(array[idx],idx);
    if(bst.IsBalanceTree())
    {
        cout<<"IS AVLTree"<<endl;
    }
    else
    {
        cout<<"NO IS AVLTree"<<endl;
    }
}

int main()
{
    //funtest();
    funtest1();
    getchar();
    return 0;
}