黑马程序员技术交流社区

标题: TreeSet的底部数据结构的实现 [打印本页]

作者: pphdsny3 时间: 2012-8-15 21:24
标题: TreeSet的底部数据结构的实现
前天自己问了个问题，就是TreeSet比较对象排序compareTo()的疑问http://bbs.itheima.com/forum.php ... 1&fromuid=32708
经过自己的多方查阅资料，对其中的一些实现过程也有了一定的了解，现在就发布出来，有兴趣的同学可以去看看：

首先TreeSet的底层实现是TreeMap，TreeMap 的实现是红黑树数据结构，也就说是一棵自平衡的排序二叉树，这样就可以保证当需要快速检索指定节点。
为了理解 TreeMap 的底层实现，必须先介绍排序二叉树和红黑树这两种数据结构。其中红黑树又是一种特殊的排序二叉树。

排序二叉树是一种特殊结构的二叉树，可以非常方便地对树中所有节点进行排序和检索。

排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
它的左、右子树也分别为排序二叉树。
图1：排序二叉树：

创建排序二叉树的步骤，就是不断地向排序二叉树添加节点的过程，向排序二叉树添加节点的步骤如下：
1.以根节点当前节点开始搜索。
2.拿新节点的值和当前节点的值比较。
3.如果新节点的值更大，则以当前节点的右子节点作为新的当前节点；如果新节点的值更小，则以当前节点的左子节点作为新的当前节点。
4.重复 2、3 两个步骤，直到搜索到合适的叶子节点为止。
5.将新节点添加为第 4 步找到的叶子节点的子节点；如果新节点更大，则添加为右子节点；否则添加为左子节点。

TreeMap根据上述理论创建了属于它自己的二叉树过程:
1.当没有节点的时候，第一个添加进去的就是根节点
2.当再次添加节点的时候，就会先与根节点进行比较，大于则添加在右边，小于则添加在左边
3.继续与当前节点比较，大于则添加在右边，小于则添加在左边
4.重复第三步直到叶节点
5.对二叉树根据红白树进行调整，得到一个新的排序二叉树

红白树调整的过程：
什么是红白数：
性质 1：每个节点要么是红色，要么是黑色。
性质 2：根节点永远是黑色的。
性质 3：所有的叶节点都是空节点（即 null），并且是黑色的。
性质 4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
性质 5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
图2JAVA红白树示意图

备注：红黑树中的示意图采用白色代表红色。黑色节点还是采用了黑色表示。
当插入新的节点时，按以下步骤进行调整，已得到新的红白树：
（1）以排序二叉树的方法插入新节点，并将它设为红色。
（2）进行颜色调换和树旋转。使其满足红白树的性质
（备注：在插入操作中，红黑树的性质 1 和性质 3 两个永远不会发生改变，因此无需考虑红黑树的这两个特性。）
其中还有其他的相关信息请参照：http://cl315917525.iteye.com/blog/835107

作者: 黄敏 时间: 2012-8-15 22:14
赞一个！

作者: 柳德彬 时间: 2013-4-7 23:14
很强大啊，貌似没啥作用。。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2