riteme.github.io
riteme.github.io copied to clipboard
riteme
2-3树与红黑树 - riteme.site
这里讲得是左偏红黑树（下文用LLRB代替），红黑树（下文用RB代替）的对应的是B4树，LLRB可以在插入的时候部分对应B4树（允许新产生的4-node, 然后在后续自平衡的时候可能会被分离，而B4树总是允许4-node，所以只能说部分对应）。
在删除的时候，原始paper里面只给了B3树的对应实现的代码，没有B4的具体实现（这个资料真的少）。
不管类比B3还是B4, 对于理解插/删时的重新平衡的算法，坦白讲，就完全没有用！RB就不挨着，LLRB好像很接近，但实际更是坑：我模拟B4树的插入算法可以写出LLRB的插入算法，但由于部分对应的性质，模拟B4的删除算法根本行不通。
现在网上一些学习资料里介绍LLRB都喜欢比较大篇幅地提及与B3/B4的类比，这从认知角度讲并不有利，还不如只是讲一下RB的平衡因子是黑平衡，对比一下AVL是BF因子。
另外删除的时候，左右子树递归操作的时候只能在分别h.left, h.right 不为null的情况下进行 也就是：
def delete(h, key):
assert h is not None # 确认不是一棵空树
if key < h.key: # 在左子树中
if h.left != null:
if h.left is black and h.left.left is black: # 如果左儿子不是3-节点
h = move_red_to_left(h)
h.left = delete(h.left, key)
else: # 在右子树中或已经找到
if h.left is red:
h = cw_rotate(h) # 将左边的红链接变为右边的红链接
if key == h.key and h.right is None: # 如果已经查找到并且没有儿子
del h # 直接删除
return None
if h.right != null:
if h.right is black and h.right.left is black: # 如果右儿子不是3-节点
h = move_red_to_right(h)
if key == h.key: # 如果已经查找到但有儿子
x = min_node(h.right) # 找到后及节点
# 交换键值和卫星数据
h.key = x.key
h.data = x.data
h.right = delele(h.right, x.key) # 在右子树中删除后继
else: # 如果没有命中，则继续往右边寻找
h.right = delete(h.right, key)
return balance(h)
归根结底，LLRB就是RB发明人之一的Sedgewick老先生的课堂讲义出来的东西，资料很少，而且抄来抄去都是那份不怎么完整的原始资料，也不知道怎么就这么popular...
能通过我自己测试的也就是这个版本，增加了上文提到的两个非NULL的判定（原始版本当有不连续重复的删除操作时可能会挂掉）
另外删除的时候，左右子树递归操作的时候只能在分别h.left, h.right 不为null的情况下进行 也就是：
...归根结底，LLRB就是RB发明人之一的Sedgewick老先生的课堂讲义出来的东西，资料很少，而且抄来抄去都是那份不怎么完整的原始资料，也不知道怎么就这么popular...
能通过我自己测试的也就是这个版本，增加了上文提到的两个非NULL的判定（原始版本当有不连续重复的删除操作时可能会挂掉）
抱歉，你写得应该没什么问题，这个回复只是补个高亮（
def delete(h, key):
assert h is not None # 确认不是一棵空树
if key < h.key: # 在左子树中
if h.left != null:
if h.left is black and h.left.left is black: # 如果左儿子不是3-节点
h = move_red_to_left(h)
h.left = delete(h.left, key)
else: # 在右子树中或已经找到
if h.left is red:
h = cw_rotate(h) # 将左边的红链接变为右边的红链接
if key == h.key and h.right is None: # 如果已经查找到并且没有儿子
del h # 直接删除
return None
if h.right != null:
if h.right is black and h.right.left is black: # 如果右儿子不是3-节点
h = move_red_to_right(h)
if key == h.key: # 如果已经查找到但有儿子
x = min_node(h.right) # 找到后及节点
# 交换键值和卫星数据
h.key = x.key
h.data = x.data
h.right = delele(h.right, x.key) # 在右子树中删除后继
else: # 如果没有命中，则继续往右边寻找
h.right = delete(h.right, key)
return balance(h)
