平衡二叉树
我们知道，对于二叉查找树，树的层数越少，查找数据的平均查找时间就会越少。二叉排序树在很多情况下都不能保证树的高度是最优的，例如在极端情况，如果插入排序树的数据是有序的，那么二叉树就会退化成为单链，这时查找的时间复杂度也退化成O(n)的了。为了解决这个问题，我们希望二叉树是尽量平衡的，也就是说对于树中的任意一个结点，都能使其左子树上结点的个数和右子树上结点的个数相差不太多。
定义
平衡二叉树也叫AVL树。AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis，他们在1962年的论文"Analgorithm for the organization of information"中发表了它。
平衡二叉树是具有以下性质的二叉查找树：对于树中的任意一个结点，都有该结点的左子树的高度与右子树的高度之差的绝对值小于2。与普通的BST相比，AVL树只是多定义了旋转操作，使得当左右子树的高度差的绝对值大于或者等于2时，平衡树可以自动地进行树形调整，以重新满足上述性质。
名词
平衡因子：每个结点的平衡因子就是该结点的左子树的高度减去右子树的高度，平衡二叉树的每个结点的平衡因子的绝对值不会超过2(或者大于1)。
例子
记住两张图一口诀即可。
口诀：左子作父，父为右子，右孙变左孙
右旋示意图
image
考虑顺序向二叉查找树中插入数据5,3,6,2,4,1，所得到的二叉查找树的形状如图 2.12(a) 所示。对于数据为 5 的这个结点，它的左子树高度与右子树高度之差为 2，我们可以通过改变5号结点和3号结点的相关指针将其变为如图 2.12(b) 所示的形状。由于3号结点的右孩子指针指向了5号结点，4号结点暂时脱离了二叉树，但注意到5号结点的左孩子指针变为空，我们可以将4号结点挂在5号结点的左孩子上，得到如图 2.12(c) 。这样，整棵树还继续满足平衡二叉树的性质。这个操作就像把树像旋纽一样向右旋转了下，我们把这个操作形象地称为右旋。右旋的口诀可以简单总结为“左子作父，父为右子，右孙变左孙”。由此可见，右旋操作的效果是原来的右孩子的深度(注意不是高度)加1，左孙的深度减1，而右孙的深度不变。而左旋的情况与右旋互为镜像，不再赘述。
如果插入的顺序变成了5,2,6,1,3,4，所得到的二叉查找树的形状则如图 2.13(a) 所示。此时，5号结点的左子树与右子树的高度差仍然为2，这时再执行右旋行不行呢？我们可以尝试着做一下，右旋的结果如图 2.13(b) 所示，这时，新的树根2号结点的平衡因子为-2，显然直接右旋并没有使树重新平衡。这是因为右旋时右孙变左孙以后，深度没有变化，而显然造成树不平衡的主要原因在于右孙3号结点的深度过大。为了解决这个问题，尝试把它转化为第一个例子，就是对2号结点进行一次左旋，得到图 2.13(c) 。这样会使得右孙的深度转移到左孙。现在树的形状与上例相同了，再对这棵树进行右旋操作，会使得左孙深度减1，右孙不变。得到新的树是满足平衡二叉树的性质的，如图 2.13(d) 。
image
通过上面的两个例子，我们可以找出规律了。当向一棵平衡二叉树中插入一个新的结点时，有可能会使得某个结点的子树高度发生变化，从而影响了这个结点的平衡因子。当该结点的平衡因子为2时，就应该考虑对该点执行右旋操作。在执行右旋之前，还要检查一下左子树上的左孙和右孙的高度，如果是左孙的高度比较大，那么直接右旋就可以重新平衡，如果是右孙的高度比较大，那么就要在左孩子结点上先执行一次左旋。
具体代码
整体思路：
- 构建树的节点
- 插入方法
- 计算平衡因子
- 右旋
- 左旋
- 计算节点深度
树节点
组成部分：
- 父亲
- 左子
- 右子
- 数据域
- 平衡因子
- 当前树的深度
public class AVLNode {
public int data;
public int depth;
public int balance;
public AVLNode parent;
public AVLNode left;
public AVLNode right;
public AVLNode(int data) {
this.data = data;
this.depth = 1;
this.balance = 0;
this.left = null;
this.right = null;
}
}
插入方法
普通的插入操作，同二叉树没啥区别
public void insert(AVLNode root, int data) {
if (data < root.data) {
if (root.left != null) {
insert(root.left, data);
} else {
//左子出生了
root.left = new AVLNode(data);
//把爹指定了
root.left.parent = root;
}
} else {
if (root.right != null) {
insert(root.right, data);
} else {
root.right = new AVLNode(data);
root.right.parent = root;
}
}
}
计算平衡因子
然后要先获取平衡因子，计算方法前面已经提到过
该结点的左子树的高度减去右子树的高度
private int calcBalance(AVLNode p) {
int left_depth;
int right_depth;
if (p.left != null) {
left_depth = p.left.depth;
} else {
left_depth = 0;
}
if (p.right != null) {
right_depth = p.right.depth;
} else {
right_depth = 0;
}
return left_depth - right_depth;
}
计算节点深度
计算节点深度，初始深度都为1
public int calcDepth(AVLNode p) {
int depth = 0;
if (p.left != null) {
depth = p.left.depth;
}
if (p.right != null && depth < p.right.depth) {
depth = p.right.depth;
}
depth++;
return depth;
}
插入流程
当该结点的平衡因子为2时，就应该考虑对该点执行右旋操作。在执行右旋之前，还要检查一下左子树上的左孙和右孙的高度，如果是左孙的高度比较大，那么直接右旋就可以重新平衡，如果是右孙的高度比较大，那么就要在左孩子结点上先执行一次左旋。
//插入新节点之后，先计算树的平衡因子
root.balance = calcBalance(root);
//左子树高，右旋
if (root.balance >= 2) {
//右孙高，左旋
if (root.left.balance == -1) {
left_rotate(root.left);
}
right_rotate(root);
}
if (root.balance <= -2) {
if (root.right.balance == -1) {
right_rotate(root.right);
}
left_rotata(root);
}
root.balance = calcBalance(root);
root.depth = calcDepth(root);
右旋
口诀
左子作父，父为右子，(左子)右孙变(右子)左孙
一次操作包括爷爷、父亲和孙子
爷爷：pParent = p.parent
左子：pLeftSon = p.left
(左子的)右孙:pRightGrandSon = pLeftSon.right
具体写法可以参考一下子步骤(参考上一页的图1)
- 将节点3变为爷爷
- 将节点5变为节点3的右子
- 将节点5的爸爸变为节点3
- 将节点5的左子变为节点4
- 将节点4的爸爸变为节点5
private void right_rotate(AVLNode p) {
//爷爷
AVLNode pParent = p.parent;
//左子
AVLNode pLeftSon = p.left;
//左子的右孙
AVLNode pRightGrandSon = pLeftSon.right;
// 节点3为爷爷
pLeftSon.parent = pParent;
// 节点3的右子为节点5 (左子为父的过程)
pLeftSon.right = p;
if (pParent != null) {
if (p == pParent.left) {
pParent.left = pLeftSon;
} else if (p == pParent.right) {
pParent.right = pLeftSon;
}
}
// 节点5的爸爸为节点3
p.parent = pLeftSon;
// 节点5的左子变为节点4
p.left = pRightGrandSon;
// 考虑节点4为空的情况，不为空就把节点4的爸爸变为节点5
if (pRightGrandSon != null) {
pRightGrandSon.parent = p;
}
p.depth = calcDepth(p);
p.balance = calcBalance(p);
pLeftSon.depth = calcDepth(pLeftSon);
pLeftSon.balance = calcBalance(pLeftSon);
}
左旋
参考右旋写法即可
private void left_rotate(AVLNode p) {
AVLNode pParent = p.parent;
AVLNode pRightSon = p.right;
AVLNode pLeftGrandSon = pRightSon.left;
pRightSon.parent = pParent;
pRightSon.left = p;
if (pParent != null) {
if (p == pParent.right) {
pParent.right = pRightSon;
} else if (p == pParent.left) {
pParent.left = pRightSon;
}
}else {
root = pRightSon;
}
p.parent = pRightSon;
p.right = pLeftGrandSon;
if (pLeftGrandSon != null) {
pLeftGrandSon.parent = p;
}
p.depth = calcDepth(p);
p.balance = calcBalance(p);
pRightSon.depth = calcDepth(pRightSon);
pRightSon.balance = calcBalance(pRightSon);
}
按层遍历
再写一个按层遍历二叉树的方法，为了简单，这里直接用递归法
public List<List<Integer>> levelOrder() {
List<List<Integer>> result = new ArrayList();
helper(result, root, 0);
return result;
}
private void helper(List<List<Integer>> result, AVLNode node, int level) {
if (node == null) {
return;
}
if (result.size() == level) {
result.add(new ArrayList());
}
result.get(level).add(node.data);
helper(result, node.left, level + 1);
helper(result, node.right, level + 1);
}
为了方便测试，调整了整体的代码，现将完整代码列出：
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class MyAVLTree {
private AVLNode root;
public void insert(int data) {
if (root == null) {
root = new AVLNode(data);
} else {
insert(root, data);
}
}
private void insert(AVLNode root, int data) {
if (data < root.data) {
if (root.left != null) {
insert(root.left, data);
} else {
//左子出生了
root.left = new AVLNode(data);
//把爹指定了
root.left.parent = root;
}
} else {
if (root.right != null) {
insert(root.right, data);
} else {
root.right = new AVLNode(data);
root.right.parent = root;
}
}
//插入新节点之后，先计算树的平衡因子
root.balance = calcBalance(root);
//左子树高，右旋
if (root.balance >= 2) {
//右孙高，左旋
if (root.left.balance == -1) {
left_rotate(root.left);
}
right_rotate(root);
}
if (root.balance <= -2) {
if (root.right.balance == -1) {
right_rotate(root.right);
}
left_rotate(root);
}
root.balance = calcBalance(root);
root.depth = calcDepth(root);
}
private void left_rotate(AVLNode p) {
AVLNode pParent = p.parent;
AVLNode pRightSon = p.right;
AVLNode pLeftGrandSon = pRightSon.left;
pRightSon.parent = pParent;
pRightSon.left = p;
if (pParent != null) {
if (p == pParent.right) {
pParent.right = pRightSon;
} else if (p == pParent.left) {
pParent.left = pRightSon;
}
}else {
root = pRightSon;
}
p.parent = pRightSon;
p.right = pLeftGrandSon;
if (pLeftGrandSon != null) {
pLeftGrandSon.parent = p;
}
p.depth = calcDepth(p);
p.balance = calcBalance(p);
pRightSon.depth = calcDepth(pRightSon);
pRightSon.balance = calcBalance(pRightSon);
}
private void right_rotate(AVLNode p) {
//爷爷
AVLNode pParent = p.parent;
//左子
AVLNode pLeftSon = p.left;
//左子的右孙
AVLNode pRightGrandSon = pLeftSon.right;
// 节点3为爷爷
pLeftSon.parent = pParent;
// 节点3的右子为节点5 (左子为父的过程)
pLeftSon.right = p;
if (pParent != null) {
if (p == pParent.left) {
pParent.left = pLeftSon;
} else if (p == pParent.right) {
pParent.right = pLeftSon;
}
}else {
root = pLeftSon;
}
// 节点5的爸爸为节点3
p.parent = pLeftSon;
// 节点5的左子变为节点4
p.left = pRightGrandSon;
// 考虑节点4为空的情况，不为空就把节点4的爸爸变为节点5
if (pRightGrandSon != null) {
pRightGrandSon.parent = p;
}
p.depth = calcDepth(p);
p.balance = calcBalance(p);
pLeftSon.depth = calcDepth(pLeftSon);
pLeftSon.balance = calcBalance(pLeftSon);
}
private int calcBalance(AVLNode p) {
int left_depth;
int right_depth;
if (p.left != null) {
left_depth = p.left.depth;
} else {
left_depth = 0;
}
if (p.right != null) {
right_depth = p.right.depth;
} else {
right_depth = 0;
}
return left_depth - right_depth;
}
public int calcDepth(AVLNode p) {
int depth = 0;
if (p.left != null) {
depth = p.left.depth;
}
if (p.right != null && depth < p.right.depth) {
depth = p.right.depth;
}
depth++;
return depth;
}
public List<List<Integer>> levelOrder(){
List<List<Integer>> result = new ArrayList();
helper(result, root, 0);
return result;
}
public void helper(List<List<Integer>> result, AVLNode node, int level){
if(node == null){
return;
}
if(result.size() == level){
result.add(new ArrayList());
}
result.get(level).add(node.data);
helper(result, node.left, level+1);
helper(result, node.right, level+1);
}
class AVLNode {
public int data;
public int depth;
public int balance;
public AVLNode parent;
public AVLNode left;
public AVLNode right;
public AVLNode(int data) {
this.data = data;
this.depth = 1;
this.balance = 0;
this.left = null;
this.right = null;
}
}
}
测试程序：
public class TestMyAVLTree {
public static void main(String[] args){
MyAVLTree myAVLTree = new MyAVLTree();
myAVLTree.insert(5);
myAVLTree.insert(2);
myAVLTree.insert(6);
myAVLTree.insert(1);
myAVLTree.insert(3);
myAVLTree.insert(4);
// myAVLTree.insert(5);
// myAVLTree.insert(3);
// myAVLTree.insert(6);
// myAVLTree.insert(2);
// myAVLTree.insert(4);
// myAVLTree.insert(1);
System.out.println(myAVLTree.levelOrder());
}
}
网友评论