首页 > 其他 > 详细

红黑树插入详解

时间:2021-03-03 22:29:06      阅读:5      评论:0      收藏:0      [点我收藏+]

红黑树的定义与性质

红黑树是一种含有红黑结点的二叉查找树。它必须满足下面性质:

  • 性质1:每个节点要么是黑色,要么是红色。
  • 性质2:根节点是黑色。
  • 性质3:每个叶子节点(NIL)是黑色。
  • 性质4:每个红色结点的两个子结点一定都是黑色(不存在两个连续的红色结点)。
  • 性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑结点(黑色完美平衡)。

技术分享图片

红黑树的插入

红黑树应先按二叉查找树的插入方法插入到叶子结点,插入的结点先设置为红色,然后再按照红黑树的性质对其进行调整。

红黑树的调整始终优先调整不满足性质的最小子树!

在讲解之前,我们先来约定下各字母含义。

技术分享图片

I表示插入结点,P表示插入结点的父结点,S表示插入结点的叔叔结点,PP表示插入结点的祖父结点。

插入情景1:红黑树为空树

最简单的一种情景,直接把插入结点作为根结点就行,但注意,根据红黑树性质2:根节点是黑色。还需要把插入结点设为黑色。

处理:把插入结点作为根结点,并把结点设置为黑色。

插入情景2:插入结点的Key已存在

可简单认为不对原来的红黑树做任何操作。

插入情景3:插入结点的父结点为黑结点

由于插入结点为红色,不影响平衡。直接插入

插入情景4:插入结点的父结点为红结点

再次回想下红黑树的性质2:根结点是黑色。如果插入的父结点为红结点,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。

插入情景4.1:叔叔结点存在并且为红结点

处理:

  • 将P和S设置为黑色
  • 将PP设置为红色
  • 把PP设置为当前插入结点
    技术分享图片
    技术分享图片

把PP结点设为红色了,如果PP的父结点是黑色,那么无需再做任何处理;但如果PP的父结点是红色,根据性质4,此时红黑树已不平衡了,所以还需要把PP当作新的插入结点,继续做插入操作自平衡处理,直到平衡为止。

插入情景4.2:叔叔结点不存在或为黑色,并且插入结点的父亲结点是祖父结点的左子结点

插入情景4.2.1:插入结点是其父结点的左子结点

处理:

  • 将P设为黑色
  • 将PP设为红色
  • 对PP进行右旋

技术分享图片

插入情景4.2.2:插入结点是其父结点的右子结点

处理:

  • 对P进行左旋
  • 把P设置为插入结点,得到情景4.2.1
    -进行情景4.2.1的处理

技术分享图片

插入情景4.3:叔叔结点不存在或为黑色,并且插入结点的父亲结点是祖父结点的右子结点

该情景对应情景4.2,只是方向反转

插入情景4.3.1:插入结点是其父结点的右子结点

技术分享图片

插入结点是其父结点的左子结点

技术分享图片

原文链接 原文包含红黑树插入删除的详细操作。

红黑树插入详解

原文:https://www.cnblogs.com/Dallas98/p/14477178.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号