黑马程序员技术交流社区
标题: TreeSet的存储问题 [打印本页]
作者: Jim-剣◆﹏ 时间: 2013-10-17 00:24
标题: TreeSet的存储问题
本帖最后由 Jim-剣◆﹏ 于 2013-10-18 13:47 编辑
视频中说，TreeSet的数据结构是二叉树，存储的时候，是从头开始比较，比头小的放左边，大的放右边，但是当元素很多的时候，会取中间值开始比较，存储效率是提高了，但是这个就不再是一个严格的顺序了，就成为一个相对的顺序了，这是为什么？怎么理解这段话
图中的90，如果一开始选择和22比较，就会出现在现在的位置上，可是如果一开始选择30比较，就会出现在图片中36的位置上，这个次序不是唯一的吗？为什么不是唯一的？望有哥们给讲解下
作者: 呆萌 时间: 2013-10-17 02:54
我是这样子理解的，但是只是我自己这样子理解，不知道对不对！{:soso_e115:}
我们在录入的时候是从22开始的，左边放小的，右边放大的，形成上图。
存储的时候比如以40为中间值的时候，左边小的有两个叉，右边大的有一个。那左边两个小的就有相对顺序了，22比30小，所以相对22在左边，30在右边。
作者: 風諾 时间: 2013-10-17 02:57
首先，你说的严格的顺序存在是必要的吗？Set集合本身就是无序的，不论是TreeSet还是HashSet。
TreeSet的排序通过元素自身的比较性实现，元素不具备比较性的时候
1、可以通过实现comparable接口复写compareTo方法让元素强制具备比较性
2、给TreeSet集合的构造函数传递比较器
因此，只能说TreeSet元素是可排序的，而非TreeSet本身就是有序的
作者: To 时间: 2013-10-17 13:49
楼主你好，如果问题已解决请将帖子状态修改为提问结束，如果未解决请继续提问，谢谢合作
如果不会修改请看解释帖：http://bbs.itheima.com/thread-89313-1-1.html
作者: Jim-剣◆﹏ 时间: 2013-10-17 22:57
哥们，确实不理解，就以上面那副图来说，TreeSet在存储的时候就会给元素排序，按大小指定的位置存放，取的时候从二叉树左子树开始取，取出来就是正好严格的从小到大，如果说元素多了，存进去时选中间值比较，那么取出来就不是从小到大了，那么排序还有什么意义呢？确实不太理解，不要嫌我啰嗦啊
作者: Jim-剣◆﹏ 时间: 2013-10-17 22:58
还没解决呢
作者: 風諾 时间: 2013-10-17 23:10
本帖最后由 風諾 于 2013-10-17 23:37 编辑
本来写了一堆，后来百度了下有序：存储顺序和添加顺序一致
无序：存储顺序和添加顺序不一致
单单就存储来说，TreeSet按照你定义的规则存储
规则就是Comparator或者compareTo()
作者: 呆萌 时间: 2013-10-18 02:21
存入和取出是两个动作，可能存入的时候是从22开始存的，但取出的时候是从40当作中间值取的。
我就是这么理解的，我也不知道对不对....:(
版主，我要分！！！！技术分~~~~~~~~~~~~~~~~~~
作者: 斗胆潇洒 时间: 2013-10-18 13:30
兄弟，要解决这个问题，
你得先了解下什么是红黑二叉树(或红黑树)
它是以棵平衡二叉树，不会出现左子树和右子树相差两层(或以上)的情况，
这也就要求左右相对平衡(近似均匀)，一般根节点在构建树时会调整为一个平衡数(接近中间的数，像二分法)，
也就是说根节点最终是确定的，你设想是30，你按红黑树去构造看看，能形成一个平衡二叉树吗？
就算先拿30比较再拿90，最终红黑树也会自行调整到：任一层的左右子树最多差一层，
任一层左子树任一节点都要小于右子树任一节点，所以你说的那个90的序列排法是不存在的，要不按取值从左往右为什么都只是从小到大呢
作者: 斗胆潇洒 时间: 2013-10-18 13:33
道友..
第二张图，一般的树行，但TreeSet的是红黑树，
不会出现左子树比右子树多两层的情况
作者: 呆萌 时间: 2013-10-18 18:11
:(知道啦！
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |