kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

平衡二叉树

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对象。
 *
 */