红黑树学习笔记-删除节点
概述
根据前一篇文章中介绍的红黑树性质,现在我们需要考虑如何删除一个节点以及删除一个节点后,是否还能够满足它的5个特性,如果不满足我们需要如何调整使之满足红黑树的特性。
算法相关
根据前一篇文章中介绍的红黑树性质,现在我们需要考虑如何删除一个节点以及删除一个节点后,是否还能够满足它的5个特性,如果不满足我们需要如何调整使之满足红黑树的特性。
利用过年放假的空闲时间,把红黑树又复习了一遍,在复习的过程中又有了一些新的收获,红黑树暴露给外部有查询、 增加、删除功能接口,同时提供了一个非功能性功能,保证所有的查询、增加、删除操作都在O(lgN)的时间内返回结果。这个非功能性特性就是依靠红黑树内部的动态平衡的机制来保持的。我们做系统开发,产品设计的时候,或者设计一个时间阶段的人生目标,都可以参考红黑树的动态平衡思想。本文会解释红黑树的一些特性和新增加节点的时候,它内部维持动态平衡的过程, 然后再另一篇文章里介绍如何在删除节点的时候维持动态平衡,最后会有一篇文章,是基于红黑树的发散思考,我们如何将红黑树的动态平衡思想应用到技术以外的世界里。
1 每个节点必须是红色或者黑色
2 根节点必须是黑色
3 每个路径不能同时包含连续两个红色节点