BR 技术头条 技术链接、资讯与社区分享流
cm cmsblogs.com / 2017-12-24 19:58 / by @技术头条

【死磕Java并发】—–J.U.C之ConcurrentHashMap红黑树转换分析

先看红黑树的基本概念:红黑树是一课特殊的平衡二叉树,主要用它存储有序的数据,提供高效的数据检索,时间复杂度为O(lgn)。红黑树每个节点都有一个标识位表示颜色,红色或黑色,具备五种特性:

每个节点非红即黑
根节点为黑色
每个叶子节点为黑色。叶子节点为NIL节点,即空节点
如果一个节点为红色,那么它的子节点一定是黑色
从一个节点到该节点的子孙节点的所有路径包含相同个数的黑色节点

请牢记这五个特性,它在维护红黑树时选的格外重要

赞过的人

@技术头条

发表评论