专栏首页IT技术小咖红黑树的特性

红黑树的特性

红黑树的特性:

(1)每个节点或者是黑色,或者是红色。 (2)根节点是黑色。 (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!] (4)如果一个节点是红色的,则它的子节点必须是黑色的。 (5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意: (01) 特性(3)中的叶子节点,是只为空(NIL或null)的节点。 (02) 特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是O(lgn),效率非常之高。 例如,Java集合中的TreeSet和TreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树去实现的。

本文分享自微信公众号 - IT技术小咖(IT-arch)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-08-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • redis 集群模式的工作原理能说一下么?在集群模式下,redis 的 key 是如何寻址的?

    在 redis cluster 架构下,每个 redis 要放开两个端口号,比如一个是 6379,另外一个就是 加1w 的端口号,比如 16379。

    IT技术小咖
  • 一致性哈希(Consistent Hashing)算法的原理与实现

    分布式系统中对象与节点的映射关系,传统方案是使用对象的哈希值,对节点个数取模,再映射到相应编号的节点,这种方案在节点个数变动时,绝大多数对象的映射关系会失效而需...

    IT技术小咖
  • 分布式系统架构你必会的 Zookeeper 之基础模块-常用命令-核心原理-集群搭建-实战演练(上)

    1)Zookeeper (文中后续简称 ZK)是一个开源的分布式服务协调系统,最初由雅虎公司开发,后成为 Apache 基金会顶级开源项目。

    IT技术小咖
  • RocketMQ 多副本前置篇:初探raft协议

    Raft协议是分布式领域解决一致性的又一著名协议,主要包含Leader选举、日志复制两个部分。

    丁威
  • PaperReading-图嵌入之node2vec

    不同于图像、自然语言这种欧式空间的数据,网络结构的数据——图,通常无法通过CNN或者RNN来处理,这就需要我们寻找其他的方法来处理图数据。图数据其实非常常见,例...

    beyondGuo
  • DOM(文档对象模型)基础加强

    黑泽君
  • 「容器架构」 K8s 集群如何规划工作节点的大小?

    欢迎来到小巧的Kubernetes学习——一个定期的专栏,讨论我们在网上看到的最有趣的问题,以及Kubernetes专家在我们的研讨会上回答的问题。

    首席架构师智库
  • 最强大的GNN出现了!

    论文:https://arxiv.org/pdf/2009.00142.pdf 代码:https://github.com/snap-stanford/dist...

    Houye
  • Redis Cluster执行流程

    集群(cluster)是Redis提供的分布式数据库解决方案,集群通过分片(sharding)来进行数据共享,并提供数据复制(replication)和故障转移...

    张申傲
  • 小白初识Zookeeper

    首先,了解一个Zookeeper是什么,其是一个开源的分布式协调服务,分布式数据一致性的解决方案。

    Liusy

扫码关注云+社区

领取腾讯云代金券