[高级数据结构] 3. 红黑树

删除调整

  1. 删除红色节点,不影响平衡
  2. 删除黑色节点分情况:
    度为0,特殊思维
    度为1,孩子节点一定是红色,没有另一边(路径黑色数量相同)
    度为2可以转换为上面两种

插入调整为了干掉双红,度为0删除调整为了干掉双重黑NIL’

红黑树本质上是平衡二叉树

牢记:保证局部黑色节点数量不变
RR情况:
兄弟是右子树,右孩子节点是红色

为了干掉双黑,大左旋,导致不平衡

51->原根38颜色
38和72->黑

原因:48颜色不确定,防止它是红色,把38染黑,

RL
右兄弟的右孩子一定是黑色

上一篇:[USACO20FEB]Help Yourself P 题解


下一篇:38岁,外企技术经理,失业:职场遇到瓶颈,你可能掉进了“能力陷阱”