C/C++平衡二叉树

简述

平衡二叉树基于二叉排序树的性质上添加了一个平衡的概念。所谓平衡就是让树的结构平衡,使平衡后的树的查找和添加等操作效率达到最佳。

平衡二叉树是具有下列性质的二叉树,对于它的每个节点来说,其左右子树的高度差的绝对值不超过1。我们称这一个条件为平衡因子。故节点达到平衡的平衡因子的条件为 -1,0,1。

使结构平衡必然需要调整结构,且调整后结构需要满足其二叉排序树的性质。

所以根据失衡的情况可以总结出四个调整操作,分别有左旋,右旋,先左后右旋、先右后左旋。

详解

下面以插入操作为例子来了解一下这四个平衡处理。

我们知道在二叉排序树中插入操作是在按照规则(如左分支小、右分支大)在树中找到一个合适的位置,而平衡二叉树是在这个位置确定下来之后,即树发生变化之后去检测结构是否平衡,如果失衡就去调整。

 

发生失衡的情况可能有

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

发生失衡的对象是某个节点。

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

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

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

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

节点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);
}

 

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

由于强制平衡所导致付出的代价比较高,所以红黑树出现了。关于红黑树的内容,后续会单独写一篇。

红黑树是一种二叉搜索树,但是它多了一个颜色的属性。通过颜色来弱平衡二叉树,与AVL的强制平衡相比,红黑树的树调整次数大大降低。

红黑树性质如下:

  1. 将新添加的结点设置为红,“热乎的”。
  2. 根节点一定是黑的;
  3. 在每个路径的最后都加入一个不带数据的叶子节点,这个叶子节点一定是黑的。
  4. 一节点到任意树尾端(NULL)叶子节点路径上含有的黑色结点个数相同。
  5. 父子层不能连续出现红色节点,如若出现就改变颜色。
  6. 改变颜色后也要保证遵循以上性质。

插入情况:

  1. 父为黑,直接插。
  2. 父为红,叔为红。父叔变黑,爷爷变红。
  3. 父为红,叔为黑。若爷父子是弯的就掰直。上层变色再旋转。(旋转以确保第4条规则)
作者:Miracle
来源:麦瑞克博客
链接:https://www.unitymake.com/archives/programming-life/3545
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0许可协议,转载请注明!
THE END
分享
打赏
海报
C/C++平衡二叉树
简述 平衡二叉树基于二叉排序树的性质上添加了一个平衡的概念。所谓平衡就是让树的结构平衡,使平衡后的树的查找和添加等操作效率达到最佳。 平衡二叉树是具有……
<<上一篇
下一篇>>
文章目录
关闭
目 录