目录

ThasBlog

学无止境

红黑树

红黑树是特殊的二叉平衡搜索树. 特点:

  1. 所有节点均为黑色或红色节点.
  2. 根节点一定为黑色节点.
  3. 叶子节点均使用NIL黑色节点填充.
  4. 不能出现连续的红色节点.
  5. 根节点到叶子节点的所有路径具有相同数量的黑色节点.

红黑树保证平衡的重要手段是左旋/右旋以及变色. 模拟器:https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

二叉搜索树左子节点<根节点<右子节点, 无论左旋还是右旋始终满足这个大小关系. 左旋/右旋这两种手段适用于全部的二叉搜索树, 而不仅仅是平衡树.

红黑树保持平衡的方式:

大前提: 新插入的节点永远是红色. (如果是黑色, 那就没有红色了, 全靠黑色节点来保障平衡, 那就退化成严格平衡二叉树了)

1 新插入节点的父节点是黑色节点, 红黑树依然保持平衡, 无需操作.

2 新插入节点的父节点是红色节点, 叔叔节点为黑色节点或NIL(直接忽略叔叔节点或者将其看成一个NIL整体):

分为LL/RR 和 LR/RL两大类型. 核心思想一样, 围绕新插入节点+父节点+祖父节点构造一棵局部子树. LR/RL先转换成LL/RR型即可.

3 新插入节点的父节点和叔叔节点都是红色节点:

叔叔节点和父节点变黑色, 祖父节点变成红色(特殊情况: 祖父节点为根节点, 不变色). 将祖父节点及其后续节点视作一个整体, 当做新插入这个红色节点.

如果曾祖父节点为黑色, 则满足情况1; 如果曾祖父节点为红色, 则分情况, 满足情况2(不可能是情况3, 因为曾祖父节点为红色, 则其子节点原本都应为黑色).


标题:红黑树
作者:thas
地址:https://thas.cc/articles/2020/12/05/1607170089855.html