红黑树删除节点尝试失败

来源:2-8 红黑树的性能测试

咕叽咕

2023-12-24 08:47:56

(, node):
    node.left :
        node
    .minimum(node.left)

(, node):
    node.left :
        right_node = node.right
        node.right = .size -= right_node

    node.left = .remove_min(node.left)
    node
    (, key):
    node = .get_node(.root, key)
    node :
        .root = ._remove(.root, key)
        .root :
            .root.color = RBTree.BLACK
        node.value
    (, node, key):
    node :
        key < node.key:
        node.left = ._remove(node.left, key)
        ret_node = node
    key > node.key:
        node.right = ._remove(node.right, key)
        ret_node = node
    :
        node.left :
            right_node = node.right
            node.right = .size -= ret_node = right_node
        node.right :
            left_node = node.left
            node.left = .size -= ret_node = left_node
        :
            successor = .minimum(node.right)
            successor.right = .remove_min(node.right)
            successor.left = node.left

            node.left = node.right = ret_node = successor

    ._balance(ret_node)

(, node):
    .is_red(node.right) .is_red(node.left):
        node = .left_rotate(node)

    .is_red(node.left) .is_red(node.left.left):
        node = .right_rotate(node)

    .is_red(node.left) .is_red(node.right):
        .flip_colors(node)

    node

():
    (node):
        node :
            .is_red(node) (.is_red(node.left) .is_red(node.right)):
            left_black_height = check_properties(node.left)
        right_black_height = check_properties(node.right)
        left_black_height != right_black_height:
            left_black_height + (.is_red(node) )

    check_properties(.root) >

bobo老师好,我自己尝试写的红黑树删除函数,好像我尝试删除节点后,调用is_valid_rbtree检查是否是红黑树的时候会提示不是红黑树,请问问题出在哪呢?有没有红黑树删除节点的代码参考一下呢?

写回答

1回答

liuyubobobo

2024-01-11

红黑树的删除操作完全不需要掌握,可以参考我这里的回答:https://class.imooc.com/course/qadetail/316111


如果你想要一个参考代码,可以参考这里的 delete 函数。(这是一个完整的从底层实现的左倾红黑树):https://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html


继续加油!:)

0

算法与数据结构

波波老师5年集大成之作,算法与数据结构系统学习,考试、面试、竞赛通用

2636 学习 · 1090 问题

查看课程