红黑树删除叶子节点的时候,假如被删除的节点有兄弟节点这么处理呢?

很多文章都是说删除叶子节点如果删除的是黑色节点就要处理平衡问题了。但是我思考了一下,如果删除的叶子节点有兄弟节点的话,相当于少了一条路径,既然路径不存在了,也不需要处理平衡了吧。如果没兄弟节点的话,删除叶子节点,经过父节点的路径都会少一个黑色节点。。。这时候才需要处理平衡

为什么大多数文章都说删除黑色叶子节点就要调整呢???

阅读 863
评论
    2 个回答
    • 333

    你把null指针也当作一个黑色节点,算法导论里是做了这种假设的,那么就不存在一个路径会消失的问题了。

      • 1.8k

      红黑树的性质之一:对于任意一个结点,其到叶子结点的每条路径上都包含相同数目的黑色结点。

      只要删除一个黑色的结点,就必须会通过着色或旋转来保证上述的性质。

        撰写回答

        登录后参与交流、获取后续更新提醒

        相似问题
        推荐文章