红黑树和平衡二叉树的优缺点,红黑树为什么是平衡二叉树

首页 > 经验 > 作者:YD1662022-11-14 14:09:12

整体来说左倾红黑树的插入就是这3种情况来回切换,最终达到平衡。

3.4 左倾红黑树删除

删除思路是不删除目标数据,而是找到目标数据的前驱节点后继节点,然后把数据拷贝一份到目标数据进行覆盖。然后转而去删除前驱或后继。删除后再去修补平衡。

从宏观上来看从根节点开始查找,全程利用2-3树思维逐层对红黑树调整,每次保证当前节点树2-3树中非2节点,如果是非2节点则看下一层,如果是2节点则根据兄弟节点调整。

  1. 兄弟节点是2节点,从父节点借个数据跟当前节点及兄弟节点形成临时4节点。
  2. 兄弟节点是非2节点,兄弟节点上升一个数据,父节点下降一个数据。

红黑树和平衡二叉树的优缺点,红黑树为什么是平衡二叉树(17)

删除后就涉及到数据平衡修复了,还是根据2-3树来修复平衡,路上可能会碰到红色右倾节点,遇到就进行一次左旋即可。

红黑树和平衡二叉树的优缺点,红黑树为什么是平衡二叉树(18)

​3.5 工业级红黑树增加

说下实际工程中红黑树的增删操作,增加主要有3种情况:

红黑树和平衡二叉树的优缺点,红黑树为什么是平衡二叉树(19)

情况1:关注节点是 a,它的叔叔节点 d 是红色:

  1. 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色。
  2. 将关注节点 a 的祖父节点 c 的颜色设置成红色。
  3. 关注节点变成 a 的祖父节点 c,实现关注节点的迁移。
  4. 跳到情况2或情况3。

红黑树和平衡二叉树的优缺点,红黑树为什么是平衡二叉树(20)

上一页12345下一页

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.