平衡二叉树
1.定义平衡二叉树,又称AVL树,用于解决二叉排序树高度不确定的情况,如果二叉排序树的子树间的高度相差太大,就会让二叉排序树操作的时间复杂度升级为O(n),为了避免这一情况,为最坏的情况做准备,就出现了平衡二叉树,使树的高度尽可能的小,其本质还是一棵二叉搜索树。平衡二叉树的性质:左子树和右子树的高度之差的绝对值小于等于1左子树和右子树也是平衡二叉树为了方便起见,给树上的每个结点附加一个数字,给出该
1.定义
平衡二叉树,又称AVL树,用于解决二叉排序树高度不确定的情况,如果二叉排序树的子树间的高度相差太大,就会让二叉排序树操作的时间复杂度升级为O(n),为了避免这一情况,为最坏的情况做准备,就出现了平衡二叉树,使树的高度尽可能的小,其本质还是一棵二叉搜索树。
平衡二叉树的性质:
- 左子树和右子树的高度之差的绝对值小于等于1
- 左子树和右子树也是平衡二叉树
为了方便起见,给树上的每个结点附加一个数字,给出该结点左子树与右子树的高度差,这个数字称为结点的平衡因子(BF)
平衡因子=结点左子树的高度-结点右子树的高度。
因此平衡二叉树所有结点的平衡因子只能是-1、0、1,如下图,是一个平衡二叉树
平衡二叉树的高度为logn
2.失衡
当我们在一个平衡二叉树上插入一个结点时,有可能会导致失衡,即出现平衡因子绝对值大于1 的结点,如下图,当插入结点后,其中key为53的结点失去了平衡,我们称该结点为失衡结点,我们必须重新调整树的结构,使之恢复平衡。
不一定只有一个结点失去平衡,有可能插入一个结点会让多个结点失衡。这时候找 最小的失衡子树的根节点作为失衡结点。
3.恢复平衡
那如何去恢复平衡,使得二叉搜索树依然成立为一棵平衡树?先来看平衡调整的四种类型:
举个例子:如第一个,当平衡二叉树为AB时,插入一个C结点,使得失衡了,失衡结点为A,此时因为C结点插入的位置为失衡结点的左孩子的左孩子,所以是LL型,以此类推。
为了恢复平衡,针对每一种都不一样,但目的都是调整为平衡的,且不能违背二叉搜索树的性质:如下图是每种失衡类型的解决方法,每个都不太一样,目的都是一样的,把key的值为中等的变为树的根,最小的放在左孩子,做大的放右孩子,通过这一目的,降低树的高度,也不用死记硬背。
如书上所说,这一操作被称为树的旋转,如LL型被称为右旋,RR型称为左旋,LR型是先左旋,再右旋,RL型先右旋再左旋。
3.1LL型调整
如下,在实际情况中,调整的内容可能看起来更复杂,如下方块的表示省略了n个结点,调整的方式如下(右旋):
步骤为:
- B结点带左子树(α和新添加的C结点)一起上升
- A结点成为B的右子树
- 原来的B的右子树成为A的左子树,因为A的左子树是B,上升了,所以空着的
可以看成是A右旋为B的右子树
3.2RR型
LL型和RR型是最简单的几种情况,所以放在了前面。RR型即插入的结点位置在失衡结点的右子树的右子树中,如下图:
调整的步骤和LL的差不多
步骤为:
- B结点和它的右子树(β和新添加的C结点)一起上升
- A结点变为B结点的左子树
- 原来B的左子树α变为A的右子树
可以看成是A左旋至B的左子树
3.3LR型调整
LR型的跳转如下(左旋再右旋):
- 首先让B和它的子树(除了C)左旋至C的左子树,把C为根的树接入A的左子树
- 然后让A右旋,成为C的右子树
其过程就是把中位数的C上升,成为AB的双亲
3.4RL型调整
RL型如下(先右旋再左旋):
- 首先让B和它的子树(除了C)右旋至C的右子树,把C为根的树接入A的右子树
- 然后让A左旋,成为C的左子树
和LR差不多
例题:输入关键字序列(16,3,7,11 ,9,26,18,14,15)给出AVL树
参考答案:
4.代码实现
public class AVLTree {
private AVLNode root;
public class AVLNode {
public int data;
public int height;
public AVLNode parent;
public AVLNode left;
public AVLNode right;
public AVLNode(int data) {
this.data = data;
this.height = 1;
}
@Override
public String toString() {
return "AVLNode{" +
"data=" + data +
'}';
}
public void inOrder() {//中序遍历
if (this.left != null) {
this.left.inOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.inOrder();
}
}
}
private int calcHeight(AVLNode root) {
if (root.left == null && root.right == null) {
return 1;
} else if (root.right == null) {
return root.left.height + 1;
} else if (root.left == null) {
return root.right.height + 1;
} else {
return root.left.height > root.right.height ? root.left.height + 1 : root.right.height + 1;
}
}
private int calcBF(AVLNode root) {
if (root == null) {
return 0;
} else if (root.left == null && root.right == null) {
return 0;
} else if (root.right == null) {
return root.left.height;
} else if (root.left == null) {
return -root.right.height;
} else {
return root.left.height - root.right.height;
}
}
public AVLNode leftRotate(AVLNode root) {
AVLNode oldRoot = root;
AVLNode newRoot = root.right;
AVLNode parent = root.parent;
//1.newRoot 替换 oldRoot 位置
if (null != parent) {
if (oldRoot.parent.data > oldRoot.data) {
parent.left = newRoot;
} else {
parent.right = newRoot;
}
}
newRoot.parent = parent;
//2.重新组装 oldRoot (将 newRoot 的左子树 给 oldRoot 的右子树)
oldRoot.right = newRoot.left;
if (newRoot.left != null) {
newRoot.left.parent = oldRoot;
}
//3. oldRoot 为 newRoot 的左子树
newRoot.left = oldRoot;
oldRoot.parent = newRoot;
//刷新高度
oldRoot.height = calcHeight(oldRoot);
newRoot.height = calcHeight(newRoot);
return newRoot;
}
public AVLNode rightRotate(AVLNode root) {
AVLNode oldRoot = root;
AVLNode newRoot = root.left;
AVLNode parent = root.parent;
//1.newRoot 替换 oldRoot 位置
if (null != parent) {
if (oldRoot.parent.data > oldRoot.data) {
parent.left = newRoot;
} else {
parent.right = newRoot;
}
}
newRoot.parent = parent;
//2.重新组装 oldRoot (将 newRoot 的右子树 给 oldRoot 的左子树)
oldRoot.left = newRoot.right;
if (newRoot.right != null) {
newRoot.right.parent = oldRoot;
}
//3. oldRoot 为 newRoot 的左子树
newRoot.right = oldRoot;
oldRoot.parent = newRoot;
//刷新高度
oldRoot.height = calcHeight(oldRoot);
newRoot.height = calcHeight(newRoot);
return newRoot;
}
public void insert(int data) {
if (null == this.root) {
this.root = new AVLNode(data);
return;
}
this.root = insert(this.root, data);
}
public AVLNode insert(AVLNode root, int data) {
//插入左子树
if (data < root.data) {
if (null == root.left) {
root.left = new AVLNode(data);
root.left.parent = root;
} else {
insert(root.left, data);
}
}
//插入右子树
else if (data > root.data) {
if (null == root.right) {
root.right = new AVLNode(data);
root.right.parent = root;
} else {
insert(root.right, data);
}
}
//刷新高度
root.height = calcHeight(root);
//旋转
//1. LL 型 右旋转
if (calcBF(root) == 2) {
//2. LR 型 先左旋转
if (calcBF(root.left) == -1) {
root.left = leftRotate(root.left);
}
root = rightRotate(root);
}
//3. RR型 左旋转
if (calcBF(root) == -2) {
//4. RL 型 先右旋转
if (calcBF(root.right) == 1) {
root.right = rightRotate(root.right);
}
root = leftRotate(root);
}
return root;
}
public void inOrder() {
root.inOrder();
}
}
测试:
AVLTree tree = new AVLTree();
tree.insert(16);
tree.insert(3);
tree.insert(7);
tree.insert(11);
tree.insert(9);
tree.insert(26);
tree.insert(18);
tree.insert(14);
tree.insert(15);
tree.inOrder();
结果如下:
AVLNode{data=3}
AVLNode{data=7}
AVLNode{data=9}
AVLNode{data=11}
AVLNode{data=14}
AVLNode{data=15}
AVLNode{data=16}
AVLNode{data=18}
AVLNode{data=26}
就是上面例题中的平衡二叉树。
更多推荐










所有评论(0)