Skip to main content

算法

算法相关

红黑树学习笔记-新增节点

Submitted by taotao on Fri, 02/15/2019 - 12:21

概述

利用过年放假的空闲时间,把红黑树又复习了一遍,在复习的过程中又有了一些新的收获,红黑树暴露给外部有查询、 增加、删除功能接口,同时提供了一个非功能性功能,保证所有的查询、增加、删除操作都在O(lgN)的时间内返回结果。这个非功能性特性就是依靠红黑树内部的动态平衡的机制来保持的。我们做系统开发,产品设计的时候,或者设计一个时间阶段的人生目标,都可以参考红黑树的动态平衡思想。本文会解释红黑树的一些特性和新增加节点的时候,它内部维持动态平衡的过程, 然后再另一篇文章里介绍如何在删除节点的时候维持动态平衡,最后会有一篇文章,是基于红黑树的发散思考,我们如何将红黑树的动态平衡思想应用到技术以外的世界里。

红黑树解释

红黑树的标准

1 每个节点必须是红色或者黑色

2 根节点必须是黑色

3 每个路径不能同时包含连续两个红色节点

Tags