LuFei_java的博客

伸展树与二叉平衡查找树 AVL树（带有平衡条件的树）查找的时候最坏的情形为0（N）并不坏，只要它不经常发生就可以。任何一次访问，即使花费0（N），任然可能非常快。具有最坏运行时间0（N）但保证对任意M次连续操作最多花费O（MlogN）运行时间确实让人满意了。 伸展树和其它树的区别就是没访问一个节点的时候，那个节点就会成为根节点，这样下次访问的时候时间为0（1）并且与二叉平衡查找树比少了高度的属性

查找二叉平衡树与查找二叉树有什么区别呢？当要进行大规模删除操作时（先不考虑懒惰删除），会出现某种情况，高度会逐渐的变大，是因为我们总是把右边最小的叶子节点变为删除的点，再去删除右边最大的点，这就导致了高度变大，查找数据时间变长，显然这是要优化的。 我们需要在Node(内部节点类)中加入一个高度height的一个变量 思想：当插入的时候左节点和右节点的高度度相差深度超过1的时候，必须要旋转相应的节点来

查找二叉树ADT：性质：对于树中每个节点X，它的左子树所有项的值小于X中的项而它的右子树所有项的值大于X中的项/* * 查找二叉树ADT： * 性质：对于树中每个节点X，它的左子树所有项的值小于X中的项 * 而它的右子树所有项的值大于X中的项 */ public class BinarySearchTree> { /* * 树节点元素 */ private static cl

关于Set接口    Set接口不允许重复元的Collection。由接口SortedSet给出的一种 特殊类型的Set保证其中的各项处于有序的状态。因为一个Set IS-A Collection,所以用于访问继承 Collection的List的项的方法也对Set有效。     由Set所要求的一些独特的操作是一些插入/删除/以及（有效地）执行 基本查找的能力。对于Set，add方法如果执