HashMap之红黑树树化过程

个节点标记为红色或者黑色。 根是黑色的。 如果一个节点是红色的，那么它的子节点必须是黑色的(这就是为什么叫红黑树)。 一个节点到到一个null引用的每一条路径必须包含相同数目的黑色节点(所以红色节点不影响)。 其实RB Tree和著名的AVL Tree有很多相同的地方，困难的地方都在于将一个新项插入到树中。了解AVL Tree的朋友应该都知道为了维持树的高度必须在插入一个新的项后必须在树的结构上进行改变，这里主要是通过旋转，当然在RB Tree中原理也是如此。

上面的图中描述了红黑树中三种典型的变换，其实前两种变换这正是AVL Tree中的两种典型的变换。

04 几个问题

4.1 为什么要进行旋转?

由于P和X节点都为红色节点这破环了红节点下面的节点必须为黑色节点的规则。

4.2 新加入的节点总是红色的，这是为什么呢?

因为被插入前的树结构是构建好的，一但我们进行添加黑色的节点，无论添加在哪里都会破坏原有路径上的黑色节点的数量平等关系，所以插入红色节点是正确的选择。

4.3 为什么要进行颜色变换?

正如第一种旋转新加入的节点X破坏了红黑树的结构不得不进行旋转，后面的就是旋转后的结果，旋转后形成新的结构，此时我们发现两个子节点都是红色的所以执行第三个变换特性，颜色变换，因为如果子节点是红色的那么我们在添加的时候只能添加黑色的节点，然而添加任何黑色叶子节点都会破坏树的第四条性质，所以要对其进行变换。当进行变换后叶子节点是红色的而且我们默认添加的叶子节点是红色的，所以添加到黑色节点后并不会破坏树的第四条结构，所以这种变换很有用。

第二种双变换中在树的内部怎么出现的红色的节点? 正是由于上面的颜色变换导致新颜色变换后的节点与他的父节点产生了颜色冲突。

与AVL树相比? 比AVL树相比优点是不用在节点类中保存一个节点高度这个变量，节省了内存。

而且红黑树一般不是以递归方式实现的而是以循环的形式实现。

一般的操作在最坏情形下花费O(logN)时间。

（编辑：潍坊站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!