数据结构 (三), 弄懂红黑树 RBTree(多图警告!!!)，帮你突破瓶颈
public Node search(int num) {return doSearch(root, num);}
private Node doSearch(Node root, int num) {if (root == null) {return null;}
if (root.value == num) {return root;} else if (root.value > num) {return doSearch(root.left, num);} else if (root.value < num) {return doSearch(root.right, num);}return null;}
算法时间复杂度 对于 n 个节点的树
最优f(n) = 需要查找的次数 = 二叉树的层数 ~= O(logn)
最差f(n) = 需要查找的次数 = 二叉树的层数 = n = O(n)
但是由于我们插入算法的原因, 基本维持在 O(logn)左右
2. 插入
首先需要明白的前提是:
所有的插入操作都是在叶子节点进行的;
我们默认插入节点都是红色, 这样就不会增加树的高度了, 因为如果树的高度增加, 势必会迭代到父节点里面去处理红黑树黑节点高度平衡问题
以下图示约定:
case 1: 插入的是空树
操作:
I 颜色置黑
I 赋值给
root
case 2: 插入节点值重复
操作:
直接返回, 无操作
case 3: 父节点是黑
操作:
无操作, 不需要修复平衡
case 4: 父节点是红, 叔节点是红
操作:
P 和 U 置黑
GP 置红
GP 作为插入点, 继续迭代一遍, 平衡红黑树
case 5: 父节点是红, 叔节点是黑/Nil, 左左
操作:
GP 置红
P 置黑
GP 右旋
左左: P 是 GP 的左儿子, I 是 P 的左儿子右旋之后: 树的每条路径黑节点数量并没有增加, 符合特征 6, 至此树平衡结束三角形: 代表子树, 可能由 case 4, case 7, case 8,递归到本 case 导致有子树结构
case 6: 父节点是红, 叔节点是黑/Nil, 右右
操作:
GP 置红
P 置黑
GP 左旋
右右: P 是 GP 的右儿子, I 是 P 的右儿子右旋之后: 树的每条路径黑节点数量并没有增加, 符合特征 6, 至此树平衡结束三角形: 代表子树, 可能由 case 4, case 7, case 8,递归到本 case 导致有子树结构
case 7: 父节点是红, 叔节点是黑/Nil, 左右
操作:
GP 置红
P 置黑
P 左旋
继续执行 case 5 逻辑
左右: P 是 GP 的左儿子, I 是 P 的右儿子左旋之后: 转变成了 case 5三角形: 代表子树, 可能由 case 4 递归到本 case 导致有子树结构
case 8: 父节点是红, 叔节点是黑/Nil, 右左
操作:
GP 置红
P 置黑
P 右旋
继续执行 case 6 逻辑
右左: P 是 GP 的右儿子, I 是 P 的左儿子右旋之后: 转变成了 case 6三角形: 代表子树, 可能由 case 4 递归到本 case 导致有子树结构
public void insert(int v) {
final Node node = new Node();node.left = node.right = node.parent = null;node.black = false;node.value = v;
// case 1: 插入节点是根 if (root == null) {root = node;root.black = true;return;} else {Node p = findParent(v);// case 2: 插入值重复 if (p == null) {return;}
setParent(node, p);if (v > p.value) {p.right = node;} else {p.left = node;}
fixInsert(node);}}
// 找到属于 v 的 parent 准备插入 private Node findParent(int v) {Node pre = root;Node index = root;while (index != null) {
// 找到相同值直接返回 if (index.value == v) {return null;}
pre = index;index = v < index.value ? index.left : index.right;}return pre;}
// 平衡红黑树 private void fixInsert(Node node) {
final Node parent = node.parent;final Node uncle = node.uncle();final Node grandparent = node.grandparent();// case 1: 插入节点是根 if (parent == null) {root = node;root.black = true;}// case 3: 插入节点的 父亲 是黑 else if (parent != null && parent.black) {// do nothing}else if (parent != null && !parent.black) {
// case 4: 插入节点的 父亲 是红, 叔叔 也是红 if (uncle != null && !uncle.black) {parent.black = true;uncle.black = true;// 有叔叔必定有祖父 grandparent.black = false;// 祖父的父亲是 红, 和祖父冲突了 fixInsert(grandparent);}else if (uncle == null || uncle.black) {// case 5: 叔叔 是黑/空, 左左if (parent == grandparent.left && node == parent.left) {parent.black = true;grandparent.black = false;rotateRight(grandparent);}// case 6: 叔叔 是黑/空, 左右else if (parent == grandparent.left && node == parent.right) {rotateLeft(parent);fixInsert(parent);}// case 7: 叔叔 是黑/空, 右右else if (parent == grandparent.right && node == parent.right) {parent.black = true;grandparent.black = false;rotateLeft(grandparent);}// case 8: 叔叔 是黑/空, 右左else if (parent == grandparent.right && node == parent.left) {rotateRight(parent);fixInsert(parent);}}}
}
算法时间复杂度
对于有 n 个节点的树(由于树的高度趋近 logn), f(n) = logn 次左右查找对比 + 最多只需要 2 次旋转 + logn 次的颜色替换 = O(logn) + O(1) + O(1) = O(logn)
由于颜色替换十分迅速, 这里可以把 logn 次替换看成是 O(1)复杂度
3. 删除
需要明白的是, 所有的删除操作最终都会变成删除一个叶子节点, 比如下图
以下图示约定
case 1: 树空
操作:
删除失败
case 2: 无匹配项
操作:
删除失败
case 3: d 是红
操作:
直接删除
case 4: d 是黑, s 是红
操作:
P 置红
S 置黑
P 左旋(D 是左儿子) 或者 右旋(D 是右儿子)
旋转之后兄弟节点就变为黑色了, 递归到下面的 case 5, 6, 7 进行处理
三角形: 代表子树, 可能由 case 7,递归到本 case 导致有子树结构递归处理: 之所以需要递归处理, 是因为在旋转之后, 所有路径的黑色节点数和旋转前一样, 若 D 节点路径中少了一个黑色节点, 不满足性质 6 了,需要递归处理一下
P 左旋(D 是左儿子)
右旋(D 是右儿子)
case 5.1: d 是黑, s 是黑, s 右孩子是红 且 d 是左孩子
操作:
P 和 S 颜色互换
P 左旋
三角形: 代表子树, 可能由 case 4,6,7 ,递归到本 case 导致有子树结构左旋: 左旋之后直接平衡了, 可以由下图, 看出, 所有路径旋转之后 D 节点路径中多了一个黑色节点, 其他路径黑色节点数都没变化, 而我们恰巧需要删除 D 节点中的一个黑色节点, 至此, 满足性质 6, 红黑树刚好平衡
case 5.2: d 是黑, s 是黑, s 左孩子是红 且 d 是右孩子
操作:
P 和 S 颜色互换
P 右旋
case 6.1: d 是黑, s 是黑, s 左孩子是红 且 d 是左孩子
操作:
还未添加个人签名 2021.10.31 加入
还未添加个人简介
评论