iOS Swift 实现红黑树

GitHub代码:
https://github.com/yangyu2010/leetcode/tree/master/Swift_LeetCode

红黑树对应4阶 B-tree, 先理解 B-tree.

添加

根据B树, 可知, 所有新添加的元素必须是添加到叶子节点中.
4阶B树所有节点的元素个数都符合1 ≤ x ≤ 3
把红黑树等价转换成B树, 叶子节点如下:

事例:

红黑树描述:
    25(BLACK)        46(BLACK)        76(BLACK)      88(BLACK)
     /    \               \             /
    /      \               \           /
17(RED)    33(RED)        50(RED)    72(RED)
     
B树描述:
17,25,33   46,50   72,76   88
RBR BR RB B

添加1

判定条件: 父节点是 BLACK
有4种情况

加在88的左边
加在88的右边
加在46的左边
加在76的右边

处理: 直接添加, 不用做其他任何处理

添加2

判定条件: parent 是 RED, 同时 uncle(叔父节点) 是 BLACK (空节点默认是黑色)
有4种情况

加在50的左边(RL)
加在50的右边(RR)
加在72的左边(LL)
加在72的右边(LR)

处理:
根据二叉搜索树性质, 添加到对应位置后, 做以下处理:

LL/RR的情况处理 
1. parent 染成 BLACK, grand 染成 RED, 让 parent 成为这个子树的根节点
2. grand 进行旋转
    LL: 右旋转
    RR: 左旋转

LR/RL的情况处理, 让自己成为这个子树的根节点, parent, grand 染红
1. 自己染成 BLACK, grand 染成 RED
2. 进行双旋操作, 
    LR: parent 左旋转, grand 右旋转
    RL: parent 右旋转, grand 左旋转

添加3

判定条件: parent 是 RED, 同时 uncle 也是 RED
有4种情况

加在17的左边
加在17的右边
加在33的左边
加在33的右边

处理:
根据二叉搜索树性质, 添加到对应位置后, 做以下处理:

对应B树的上溢, 当前节点元素满了, 把中间元素向上合并, 左右两边独立成新的节点
所以需要把左右两边染成 BLACK, 只有染成 BLACK 后才是独立成的节点
同时把 grand 作为中间元素, 向上合并

1. parent 染成 BLACK
2. uncle 染成 BLACK
3. grand 染成 RED
4. 把 grand 当成新加入节点再去 check
5. 若上溢到根结点, 把根结点染黑即可

删除

根据B树, 可知, 所有真正被删除的元素都是在叶子节点中.

删除1

判定条件: 真正删除的是 RED
有4种情况

真正删除的是17
真正删除的是33
真正删除的是50
真正删除的是72

处理:
直接添加, 不用做其他任何处理

删除2

判定条件: 真正删除的是 BLACK, 同时该节点至少有1个 RED 子节点
有3种情况

~~真正删除的是25~~
真正删除的是46
真正删除的是76

处理:

真正删除的是25

该节点不可能被直接删除, 因为会找到它的子节点代替
因此不考虑这种情况

真正删除的是46或76

用该节点的 RED 子节点来替代
将代替的子节点染成 BLACK 即可

删除3

判定条件: 真正删除的是 BLACK, 同时该节点也是叶子节点

真正删除的是88

处理:
若真正被删除的节点是根结点, 直接返回
其他情况
(对应的B树中的下溢)

处理:

删除3.1 该节点的兄弟节点是黑色

删除3.1.1 如果兄弟节点至少有1个 RED 子节点, 向兄弟节点借元素 (未理解, 后续注意)

处理方式:

parent 进行旋转操作(如果被删除的是左边, 进行左旋转, 右同)
旋转之后的中心节点继续 parent 的颜色
旋转之后的左右节点染为 BLACK

代码如下:

if isBlack(sibling.left) {
    rotateLeft(sibling)
    sibling = parent.left as! RBTreeNode<T>
}
color(sibling, color: parent.color)
colorBalck(sibling.left)
colorBalck(parent)
rotateRight(parent)

删除3.1.2 如果兄弟节点没有 RED 子节点, parent 节点向下合并

处理方式:

parent = BLACK 
sibling(兄弟节点) = RED 
如果 parent 未染色之前是 BLACK, 也可能下溢, 需要 parent 当作被删除的元素处理

代码如下:

let parentIsBlack = parent.color == BLACK
colorRed(sibling)
colorBalck(parent)
    
// 如果父节点是黑色, 需要对父节点再次 check
if parentIsBlack {
    afterRemove(node: parent, replacement: nil)
}

删除3.2 该节点的兄弟节点是红色

处理方式:

sibling = BLACK
parent = RED
parent 进行旋转(如果被删除的是左边, 进行左旋转, 右同)

进行以上操作后, 回到了 sibling 是 BLACK 的情况, 然后进行删除3.1的操作

代码如下:

colorBalck(sibling)
colorRed(parent)
rotateRight(parent)

学习资料和素材来源于
恋上数据结构与算法（第一季）
https://ke.qq.com/course/385223