黑马程序员技术交流社区

标题: 二叉树分布的理解 [打印本页]

作者: 黄玉昆 时间: 2013-2-24 19:04
标题: 二叉树分布的理解
本帖最后由黄玉昆于 2013-2-24 19:07 编辑

我通过对二叉树分布的测验，画了一个图，不知对否，仅供参考
对于存入时每个元素的比较，并不是连续排下来的，而是随着元素的个数而改变的，如图中所示：
第①步：22比较完了，如图①，之后会重新分布，
第②部：以22为顶部，开始比较，如图②
第③步：比完第一个33后的图示，当比第二个33重复元素的时候，又重新分布了
第④步：分布如图，第二个33是按这个如比较的。
希望这个图能让大家对二叉树有个更深刻的理解。

二叉树分布图示.png (37.36 KB, 下载次数: 31)

TreeSet视图.png (5.21 KB, 下载次数: 33)

作者: 杜鹏飞 时间: 2013-2-24 20:53
抱歉，我没法理解楼主提到的二叉树分布指的是什么。
如果是普通的Binary Search Tree的话，是不会发生自旋的。
就我的经验来看，楼主使用的数据结构应该是红黑树等平衡二叉树。
为何不是Self-adjusting binary search tree呢？我观察到图2与图3的根节点未变化。

作者: 黄玉昆 时间: 2013-2-24 21:01

Pf_D 发表于 2013-2-24 20:53
抱歉，我没法理解楼主提到的二叉树分布指的是什么。
如果是普通的Binary Search Tree的话，是不会发生自旋 ...

确实是红黑树，这个图是每次比较后的结果，不是每次比较前的图。

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

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