红黑树删除一个元素

Question

基于本课程中实现的红黑树。请老师给一个删除元素的思路，或者github上面有代码吗？

Answer 1

liuyubobobo 2019-08-14 01:41:46

课程中曾经说明过，因为红黑树的删除比较复杂，我也没有听说过任何面试问到过红黑树的删除，所以课程中没有做介绍。其实，不只红黑树的删除，连红黑树的添加的具体代码细节，在面试中都近乎不会考察。具体可以参考我的公号文章：《不能白板编程红黑树就是基础差？别扯了》https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247484057&idx=1&sn=c1df69aea5b6fc773e1dbb8cc25523af&chksm=fd8caddfcafb24c96d43df6b37f02b6e1fd20993a4dd5bda58dbad7088554641cd88d8a8eef0&token=987217713&lang=zh_CN#rd

当然，学习算法和数据结构不仅仅是为了应付面试。从实现思路的角度，其实和添加一样，删除的过程也是枚举各种可能的情况，分别处理。如果你看了上面的文章就会明白，正是因为这个“枚举各种可能情况”的思路不具有通用性，所以算法思想上的价值比较少。

具体，《算法导论》上有比较详细的红黑树删除过程的分析。我在这里只是截图（抱歉，我手头只有英文版），说明其分析框架，将删除划分成了四种不同的情况，分别处理。

可以在思考一下，我们分析红黑树的添加过程，也是将添加过程分为三种不同的情况进行处理的。由于删除比添加更复杂，所以我们要分析的情况更多，划分的方式也有所不同。

继续加油！：）

• 提问者 慕设计8353023 #1

  非常感谢！