平衡二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| /**
* 平衡二叉搜索（排序）树
*
* 平衡二叉搜索树双称为AVL树，它也是一棵二叉搜索树，是对二叉搜索树的一种改进，或都是具有下列性质的二叉树：它
* 的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
*
* 平衡因子（Balance Factor,BF）定义为该节点的左子树的深度减去其右子树的深度，则平衡二叉树上所有节点的平
* 衡因子只可能是-1、0和1。只要树上有一个节点的平衡因子的绝对值大于1，则该二叉树就是不平衡的了。
*
* 使用二叉排序树保持平衡的基本思想是：每当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若
* 是，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子s树中节点之间的关系，以达
* 到新的平衡。所谓最小不平衡子树指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
*
* 对于平衡二叉搜索树，保持树的平衡的基本机制就是旋转。旋转是对树的元素顺序进行调节。旋转的目的是消除由于临
* 时插入和删除对树的平衡产生的影响。
*
* 有四种旋转：
* 1)绕某元素左旋转
* 80 ← p 90
* / \ / \
* 60 90 ← r → 80 120
* /\ /\ /
* 85 120 60 85 100
* /
* 100
*
* 2)绕某元素右旋转
* p → 100 85
* /\ / \
* l → 85 120 → 60 100
* /\ \ /\
* 60 90 80 90 120
* \
* 80
*
* 3)绕某元素的左子节点左旋转，接着再绕该元素自己右旋转。此情况下就是 左旋与右旋 的结合，具体操作时可以分
* 解成这两种操作，只是围绕点不一样而已
*
* 先绕100的左子节点80左旋转，接着再绕100左旋转
*
* 左旋 右旋
* 100 → p → 100 → 90
* /\ /\ /\
* p → 80 120 l → 90 120 80 100
* /\ / /\ \
* 60 90 ← r 80 60 85 120
* / / \
* 85 60 85
*
* 4)绕某元素的右子节点右旋转，接着再绕该元素自己左旋转。此情况下就是 右旋与左旋 的结合，具体操作时可以分解
* 成这两种操作，只是围绕点不一样而已
*
* 先绕80的右子节点80右旋转，接着再绕80左旋转
* 右旋 左旋
* 80 → 80 ← p → 85
* /\ /\ /\
* 60 100 ← p 60 85 ← r 80 100
* /\ \ / /\
* l → 85 120 100 60 90 120
* \ /\
* 90 90 120
*
* 平衡二叉树实现类 AVLTree 中的很多方法与排序二叉树是一新的，详细请参考 BinSearchTree 类中相应方法
*
* AVLTree中的Entry对象与BinSearchTree中的Entry对象是有区别的，所以AVLTree类不能是BinSearchTree的
* 了类，虽然很多的方法是一样的（如：contains、getEntry、successor、iterator），还有一些方法（add、de
* leteEntry）只是在操作后增加了节点平衡因子调整动作，但不能直接继承于它。
*
* 二叉搜索树与平衡二叉搜索树没有在Java集合框架中实现，但RED-BLACK树在TreeMap实现过，当然TreeSet也是，
* 因为它是基于TreeMap实现的，TreeSet对象基本上就是一个忽略了每个元素值部分的TreeMap对象。
*
*/
|
