C/C++ 红黑树

由于强制平衡所导致付出的代价比较高,所以红黑树出现了。

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

红黑树性质如下:

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

插入操作

  1. 父为黑,直接插。
  2. 父为红,叔为红。父叔变黑,爷爷变红。
  3. 父为红,叔为黑。若爷父子是弯的就掰直。爷父变色再旋转。(旋转以确保第4条规则)

情况1:

情况2:

情况3:

删除操作:

删除的各情况操作见思维导图:

此处内容需要 回复 后才能查看

补充

调换完可能未达到平衡,需要向下,观察其平衡

根据颜色和树深度观平衡,短树可以认为是发生了删除操作,问题又变为了删除操作的n种情况。

删除的节点有两个非叶子节点:

*p节点删除后位置空缺,需要在树中找到一个节点放置此位置,且能满足排序树规则。其*p在左子树的中序直接前驱或右子树的中序直接后续可满足规则。

 

作者:Miracle
来源:麦瑞克博客
链接:https://www.unitymake.com/archives/programming-life/3909
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0许可协议,转载请注明!
THE END
分享
打赏
海报
C/C++ 红黑树
由于强制平衡所导致付出的代价比较高,所以红黑树出现了。 红黑树是一种二叉搜索树,但是它多了一个颜色的属性。通过红黑染色规则来弱平衡二叉树,与AVL的强制……
<<上一篇
下一篇>>
文章目录
关闭
目 录