2013年（34）
分类： C/C++
2013-05-08 02:02:01
平衡二叉树的定义 （AVL—— 发明者为Adel'son-Vel'skii 和 Landis）
平衡二叉查找树，又称AVL树。它除了具备二叉查找树的基本特征之外，还具有一个非常重要的特点：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值（平衡因子）不超过1。也就是说AVL树每个节点的平衡因子只可能是-1、0和1（左子树高度减去右子树高度）。
那么如何是二叉查找树在添加数据的同时保持平衡呢？基本思想就是：当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若破坏，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子树中节点之间的关系，以达到新的平衡。所谓最小不平衡子树指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
平衡二叉树的操作
1. 查找操作
平衡二叉树的查找基本与二叉查找树相同。
2. 插入操作
在平衡二叉树中插入结点与二叉查找树最大的不同在于要随时保证插入后整棵二叉树是平衡的。那么调整不平衡树的基本方法就是：旋转。下面我们归纳一下平衡旋转的4中情况
1) 绕某元素左旋转
80 90
/ \ 左旋 / \
60 90 -----> 80 120
/ \ / \ /
85 120 60 85 100
/
100
a) BST树 b ) AVL树
分析一下：在插入数据100之前，a图的BST树只有80节点的平衡因子是-1(左高-右高)，但整棵树还是平衡的。加入100之后，80节点的平衡因子就成为了-2，此时平衡被破坏。需要左旋转成b图。
当树中节点X的右孩子的右孩子上插入新元素，且平衡因子从-1变成-2后，就需要绕节点X进行左旋转。
2) 绕某元素右旋转
100 85
/ \ 右旋 / \
85 120 -------> 60 100
/ \ \ / \
60 90 80 90 120
\
80
a) B ST树 b) AVL树
当树中节点X的左孩子的左孩子上插入新元素，且平衡因子从1变成2后，就需要绕节点X进行右旋转。
3) 绕某元素的左子节点左旋转，接着再绕该元素自己右旋转。此情况下就是左旋与右旋 的结合，具体操作时可以分解成这两种操作，只是围绕点不一样而已。
100 100 90
/ \ 左旋 / \ 右旋 / \
80 120 ------> 90 120 ------> 80 100
/ \ / / \ \
60 90 80 60 85 120
/ / \
85 60 85
当树中节点X的左孩子的右孩子上插入新元素，且平衡因子从1变成2后，就需要先绕X的左子节点Y左旋转，接着再绕X右旋转
4) 绕某元素的右子节点右旋转，接着再绕该元素自己左旋转。此情况下就是 右旋与左旋 的结合，具体操作时可以分解成这两种操作，只是围绕点不一样而已。
80 80 85
/ \ 右旋 / \ 左旋 / \
60 100 ------> 60 85 -------> 80 100
/ \ \ / / \
85 120 100 60 90 120
\ / \
90 90 120
当树中节点X的右孩子的左孩子上插入新元素，且平衡因子从-1变成-2后，就需要先绕X的右子节点Y右旋转，接着再绕X左旋转
