C/C++平衡二叉树

插入到某节点的左子树的左子树后发生失衡

很明显它使树发生了左斜，也就说向左失衡。观察此时发生失衡的节点，如果我们要调整平衡，我们应该让左子树中一个节点移动到右子树上，使其平衡。我们知道失衡的节点的左子树都比其大，而失衡的原因是因为右子树的高度少于左子树且达到失衡因子，那我们不是就可以让失衡节点的左孩子代替此时的失衡节点在树中的位置，而让失衡节点调整到左孩子的右子树，不过如果左孩子原本已经存在右子树了，我们让左孩子的右子树调整到失衡节点的左子树上再去调整失衡节点到左孩子的右子树上，这是因为原本左孩子的右子树一定都大于左孩子，又都小于失衡的节点，所以直接让这个右子树调整到失衡节点的左子树上是满足二叉排序树结构的。

好了，我们称这个操作为右旋。

插入到左子树的右子树上后发生失衡

节点A让树发生了左斜，但是与左左位置失衡不同的是我们不能直接使用右旋操作（右旋处理后还是失衡），我们先处理左子树，改造左子树。把节点A改造成发生左左位置失衡的情况。很明显可以先对左子树进行左旋操作，这样原本的左子树作为了它的右孩子的左孩子，而右孩子代替了左子树的位置。这样就把问题变为左左位置失衡，最后对失衡节点进行右旋。

剩下两个失衡情况的处理同理，这里就不赘述了。

很次处理完一个节点之后，我们要更新其平衡因子，因为上层节点也会检测平衡。

示例代码：

template<typename ElementType>
 BTreeNode<ElementType>* BBSTree<ElementType>::left_left(BTreeNode<ElementType> *_node)
 {
    BTreeNode<ElementType> *left=_node->lchild;
    //右旋必须要有左路
    if (left)
    {
        _node->lchild=left->rchild;
        left->rchild=_node;
        //此时遍历的节点的子树节点的高度更新，但此时遍历的节点高度还未更新，仍是未加入新结点前的高度。
        //先更新原根的高度
        _node->height=MAX(GetNodeHeight(_node->lchild),GetNodeHeight(_node->rchild))+1;
        //再更新右旋后新的根
        left->height=MAX(GetNodeHeight(left->lchild),GetNodeHeight(left->rchild))+1;
        //将新根返回
    }
    
    return left;
 }

template<typename ElementType>
 BTreeNode<ElementType>* BBSTree<ElementType>::right_right(BTreeNode<ElementType> *_node)
 {
    //左旋
    BTreeNode<ElementType> *right=_node->rchild;
    //左旋必须要有右路
    if (right)
    {
        //原根与其右子树断开连接，右子树的左子树作原根的右子树。
        _node->rchild=right->lchild;
        //右子树作为新根，将原根作为新根的左子树建立连接
        right->lchild=_node;
        //先更新低层结点的高度 其实只药要更新低层结点高度就好。因为在add方法末尾会对当前遍历结点再进行高度更新
        _node->height=MAX(GetNodeHeight(_node->lchild),GetNodeHeight(_node->rchild))+1;
        right->height=MAX(GetNodeHeight(right->lchild),GetNodeHeight(right->rchild))+1;
    }
    return right;
 }

 template <typename ElementType>
 BTreeNode<ElementType> *BBSTree<ElementType>::left_right(BTreeNode<ElementType> *_node)
 {
    //对插入左子树的右子树的结点 不平衡处理要
    //先旋转低层 再旋转高层
    //先做左旋再右旋。//低层旋转完，将问题转换为一个插入左子树的左子树的结点 的不平衡情况。
    BTreeNode<ElementType> *left=_node->lchild;
    left=right_right(left);
    //左旋失败 说明没有右路，就直接进行右旋。
    if (left)
    {
        _node->lchild=left;
    }
    return left_left(_node);
 }
 template <typename ElementType>
 BTreeNode<ElementType> *BBSTree<ElementType>::right_left(BTreeNode<ElementType> *_node)
 {
    //对插入右子树的左子树的结点 不平衡处理要
    //先旋转低层 再旋转高层
    //先做右旋再左旋。//低层旋转完，将问题转换为一个插入右子树的右子树的结点 的不平衡情况。
    BTreeNode<ElementType> *right=_node->rchild;
    right=left_left(right);
    //右旋失败 说明没有左路，就直接进行左旋。
    if (right)
    {
        _node->rchild=right;
    }
    return right_right(_node);
 }

template<typename ElementType>
void BBSTree<ElementType>::Add(ElementType elem)
{
    node=Add(node,elem);
}


template<typename ElementType>
BTreeNode<ElementType>* BBSTree<ElementType>::Add(BTreeNode<ElementType> *_node,ElementType elem)
{
    if (_node==nullptr)
    {
        _node=new BTreeNode<ElementType>();
        _node->elemValue=elem;
    }
    else if (_node->elemValue>elem)
    {
        //左子树
        _node->lchild=Add(_node->lchild,elem);//向下找左子树
        //是否失衡  因为本次向左子树插入结点。之前达到平衡必然这次插入左子树高度一定不低于右子树 高度
        //因为向上递归回，所以此时遍历的节点的子树节点的高度更新，但此时遍历的节点高度还未更新，仍是未加入新结点前的高度。
        if (GetBF(_node->lchild,_node->rchild)==2)
        {
            //遍历到某一结点时，发生失衡。
            if (_node->lchild->elemValue>elem)
            {
                //如果插入到左子树的左子树。
                //进行右旋
                _node=left_left(_node);
            }
            else if (_node->lchild->elemValue<elem)
            {
                //如果插入到左子树的右子树
                ////先做左旋再右旋。
                _node=left_right(_node);
            } 
        }
    }
    else if (_node->elemValue<elem)
    {
        //右子树
        _node->rchild=Add(_node->rchild,elem);
        //向右子树倾斜
        if (GetBF(_node->lchild,_node->rchild)==-2)
        {
            if (_node->rchild->elemValue<elem)
            {
                //如果插入到右子树的右子树
                //进行左旋
                _node = right_right(_node);
            }
            else
            {
                //如果插入到右子树的左子树
                //先旋转低层 再旋转高层
                _node=right_left(_node);
            }
            
            
        }
        
        
    }
    
    _node->height=MAX(GetNodeHeight(_node->lchild),GetNodeHeight(_node->rchild))+1;
    return _node;
    
}

template<typename ElementType>
int BBSTree<ElementType>::GetBF(BTreeNode<ElementType> *LeftNode,BTreeNode<ElementType> *RightNode)
{
    return GetNodeHeight(LeftNode)-GetNodeHeight(RightNode);
}

在平衡二叉树的删除操作要比插入操作复杂的多，之后有时间再详细写一下。感兴趣的朋友可以留言。