红黑树删除节点尝试失败
来源: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
继续加油!:)
相似问题