C ++实现平衡二叉树

平衡二叉树（AVL树）必须首先满足二叉树的定义，如下所示

下图显示了不平衡的二进制排序树和平衡的二进制排序树

描述: 节点上方的数字是平衡度（balance factor）. 图9中节点的左子树比右子树高2，这不符合AVL树的定义，因此它是不平衡树

图b中所有节点的度数的绝对值不超过1，因此满足平衡树的定义，是平衡树

当前树的结构

11

/ \

7 15

/ \ / \

3 9 14 18

/ \ / / \

1 5 12 16 20

/

26

平衡因子可以是右子树的高度减去左子树的高度. 不同的教科书有不同的定义. 我将在这里跟随左右树

template<class K, class V>struct AVLTreeNode
{
    K _key;                //树权值    V _value;    int  _bf;            //平衡因子 -1,0,1        (每个节点的平衡因子等于左子树的高度减去右子树的高度) 
                        //有的教材定义平衡度是左子树高度减去右子树，都是可以的
    AVLTreeNode<K, V>* _parent;    //指向父节点的指针
    AVLTreeNode<K, V>* _left;            //指向左孩子的指针
    AVLTreeNode<K, V>* _right;        //指向右孩子的指针
    AVLTreeNode(const K& key = K(), const V& value = V())
        :_key(key)
        , _value(value)
        , _bf(0)
        , _parent(NULL)
        , _left(NULL)
        , _right(NULL)
    {}
};

左右重组是为了方便我们在插入和删除二叉树时引入平衡而引入的概念

LL型和LR型（a），LR（b），LR（c）型图的左重组

首先声明一个构造的左子树，subL实际上是危机节点，subLR是危机节点的右子树，ppNode是祖先节点

建立父子树并连接父子L和子L

如果祖先节点为空，则将当前节点subL设置为根节点，请参考上述（a’）的情况，B为危机节点，调整后成为根节点

否则，将祖父节点分配给subL的父节点，以确定父节点是否是祖先节点的左子树. 如果是这样，请将其替换为构造的左侧子树

否，只需使用subL替换祖先节点的右子树

//左改组LL型template<class K, class V>void AVLTree<K, V>::_RotateLL(AVLTreeNode<K, V>*&  parent)
{
    AVLTreeNode<K, V>* subL = parent->_left; //构造的左子树
    AVLTreeNode<K, V>* subLR = subL->_right;//subL的右子树
    AVLTreeNode<K, V>* ppNode = parent->_parent;//标记祖先节点    //1.构建parent子树 将parent和subLR链接起来
    parent->_left = subLR;    if (subLR) subLR->_parent = parent;    //2.构建subL子树 将subL与parent链接起来
    subL->_right = parent;
    parent->_parent = subL;    //3.将祖先节点与subL链接起来
    if (ppNode == NULL)
    {    //如果祖先为NULL，说明当前subL节点为根节点
        subL->_parent = NULL;
        _root = subL;
    }    else
    {
        subL->_parent = ppNode;        if (ppNode->_left == parent)
            ppNode->_left = subL;        else if (ppNode->_right == parent)
            ppNode->_right = subL;
    }    //4.重置平衡因子
    parent->_bf = 0;
    subL->_bf = 0;    //5.更新subL为当前父节点
    parent = subL;
}

pNode是当前父节点平衡二叉排序树，subR是构造的右子树，subLR是subR的左子树

当前父节点LL的左重组，然后右重组

根据平衡系数确定哪种类型的LR，请参考上图（b），（c），（d）的情况

//左改组LR型template<class K, class V>void AVLTree<K, V>::_RotateLR(AVLTreeNode<K, V>*&  parent)
{
    AVLTreeNode<K, V>* pNode = parent;
    AVLTreeNode<K, V>* subR = parent->_right;
    AVLTreeNode<K, V>* subLR = subR->_left;    int bf = subLR->_bf;
    _RotateLL(parent->_right);
    _RotateRR(parent);    //LR(b)型
    if (bf == -1)
    {
        pNode->_bf = 0;
        subR->_bf = 1;
    }    //LR(a)型
    else if (bf == 1)
    {
        pNode->_bf = -1;
        subR->_bf = 0;
    }    //LR(c)型
    else
    {
        pNode->_bf = 0;
        subR->_bf = 0;
    }
}

右调整和左调整镜像对称，相反

AVL树为空，直接将当前节点设置为根节点

AVL树满足平衡的要求，与二元排序树一致平衡二叉排序树，密钥小于当前节点，转到当前节点左子树，密钥大于当前节点，转到当前节点右子树<

将父级的左子树分配给当前节点，更新平衡因子_bf ++

将父级的右子树分配给当前节点，更新平衡因子_bf-

如果合法，即平衡系数= 0，则终止当前周期

如果当前节点是危机节点，即余额的绝对值等于1，则当前节点将备份并成为父节点，并继续检查其余额

以下是异常平衡的情况. 父节点的余额为2，当前节点（危机节点）的余额为1. 输入左重组LL，LL引入参考2.2左重组LL

当前节点余额为-1，输入左重组LR，LR介绍参见2.3左重组LR

权利重组的情况类似

template<class K, class V>bool AVLTree<K, V>::Insert(const K& key, const V& value)
{    //1.空树
    if (_root == NULL)
    {
        _root = new AVLTreeNode<K, V>(key, value);        return true;
    }    //2.AVL树不为NULL
    AVLTreeNode<K, V>* parent = NULL;
    AVLTreeNode<K, V>* cur = _root;    //找到数据插入位置
    while (cur)
    {        if (cur->_key < key)
        {
            parent = cur;
            cur = cur->_right;
        }        else if (cur->_key > key)
        {
            parent = cur;
            cur = cur->_left;
        }        else
        {            return false;
        }
    }    //插入数据
    cur = new AVLTreeNode<K, V>(key, value);
    cur->_parent = parent;    if (parent->_key > key)
        parent->_left = cur;    else
        parent->_right = cur;    while (parent)
    {        //更新平衡因子
        if (cur == parent->_left)
            parent->_bf++;        else if (cur == parent->_right)
            parent->_bf--;        //检验平衡因子是否合法
        if (parent->_bf == 0)            break;        else if (parent->_bf == -1 || parent->_bf == 1)
        {    // 回溯上升 更新祖父节点的平衡因子并检验合法性
            cur = parent;
            parent = cur->_parent;
        }        //    2 -2 平衡因子不合法 需要进行旋转 降低高度
        else   
        {            if (parent->_bf == -2)
            {                if (cur->_bf == -1)
                    _RotateRR(parent);                else
                    _RotateLR(parent);
            }            else if (parent->_bf == 2)
            {                if (cur->_bf == 1)
                    _RotateLL(parent);                else
                    _RotateRL(parent);
            }            break;
        }
    }
}

//中序遍历template<class K, class V>void AVLTree<K, V>::_InOrder(AVLTreeNode<K, V>* root)
{    if (root == NULL)        return;
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
}//前序遍历template<class K, class V>void AVLTree<K, V>::_PreOrder(AVLTreeNode<K, V>* root)
{    if (root == NULL)        return;
    cout << root->_key << " ";
    _PreOrder(root->_left);
    _PreOrder(root->_right);
}//后序遍历template<class K, class V>void AVLTree<K, V>::_PostOrder(AVLTreeNode<K, V>* root)
{    if (root == NULL)        return;
    _PostOrder(root->_left);
    _PostOrder(root->_right);
    cout << root->_key << " ";
}

运行效果如下

源代码: ％E5％B9％B3％E8％A1％A1％E4％BA％8C％E5％8F％89％E6％A0％91 / 61.％E5％B9％B3％E8％A1％ A1％E4％BA％8C％E5％8F％89％E6％A0％91

作者: Rest Pathfinder

来源:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-168551-1.html