张伦聪的技术博客 Research And Development

TreeMap的实现原理-红黑树

2018-05-07

treemap是通过红黑树算法来实现的。R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

红黑树的特性:

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

注意:

  • 特性3中的叶子节点,是只为空(NIL或null)的节点。

  • 特性5,确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

**红黑树的左旋和右旋 **

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后,都会用到旋转方法。为什么呢?道理很简单,添加或删除红黑树中的节点之后,红黑树就发生了变化,可能不满足红黑树的5条性质,也就不再是一颗红黑树了,而是一颗普通的树。而通过旋转,可以使这颗树重新成为红黑树。简单点说,旋转的目的是让树保持红黑树的特性。

左旋

右旋

红黑树的基本操作-添加

第一步: 将红黑树当作一颗二叉查找树,将节点插入。 第二步:将插入的节点着色为”红色”。 第三步: 通过一系列的旋转或着色等操作,使之重新成为一颗红黑树。

**红黑树的基本操作-删除 **

第一步:将红黑树当作一颗二叉查找树,将节点删除。 第二步:通过”旋转和重新着色”等一系列来修正该树,使之重新成为一棵红黑树。


如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

¥ 打赏博主

下一篇 分布式锁

留言