平衡二叉树——AVL树
文章目录
平衡二叉树——AVL树1、二叉搜索树的缺点2、AVL树的性质3、为何能保持平衡3.1、判断失衡的方式——平衡因子3.2、四种失衡的情况3.3、解决失衡的方法——旋转3.4、四种情况对应的旋转方式
4、平衡二叉树实现4.1、节点结构4.2、AVL树完整代码4.3、测试
1、二叉搜索树的缺点
平衡二叉树是二叉搜索树的改进版，二叉搜索树用来快速的对数据进行查找，可以将原先O(n)的复杂度降低到O(logn)，但这是在理想情况下的结果，若在原序列是有序的情况下，构建出的二叉搜索树就是线性的，与原先的线性表结构没有差异，时间复杂度会降低为O(n)。因此为避免这种情况下，需要对二叉树保持平衡
（最糟糕的情况下的二叉搜索树）
（理想状态下的二叉搜索树，左右子树高度相差不超过1）
AVL树是最早发明的一种平衡二叉树。AVL树得名于其发明者Adelson-Velsky与Evgenii Landis，其通过每个节点的左右子树的高度差来判断是否失衡，因此也被称为高度平衡树。要注意的是AVL树只是平衡二叉树的一种
2、AVL树的性质
AVL树是二叉搜索树，具有二叉搜索树的性质AVL树的子树也是AVL树AVL树的任一节点的两颗子树的最大高度差不超过1AVL树插入、查找和删除在平均情况和最坏情况下时间复杂度都是O(logn)
3、为何能保持平衡
在最初遇到这个问题时，是不是有人与我一样一位需要用到一些精妙的数据结构，事实上并不是，平衡二叉树保持平衡的奥秘就在于在每次对节点进行插入和删除时会对失衡的节点进行调整。需要知道应当如何调整，首先需要知到如何判断失衡以及失衡的几种情况
3.1、判断失衡的方式——平衡因子
平衡因子的定义：某节点的左子树与右子树的高度差即该节点的平衡因子
在平衡二叉树中平衡因子应当只有-1、0、1三个值，其他情况则视为失衡，需要重新平衡。在插入或删除一个节点时，若二叉树中的每一个节点的平衡因子都为-1、0、1，那么该二叉树是平衡的，否则需要重新平衡
3.2、四种失衡的情况
二叉搜索树的失衡情况总结下来有四种：LL型、LR型、RL型与RR型，不同的情况适用不同的处理方法
LL型：失衡节点在基准节点左子树的左孩子上
LR型：失衡节点在基准节点左子树的右孩子上
RL型：失衡节点在基准节点右子树的左孩子上
RR型：失衡节点在基准节点右子树的右孩子上
3.3、解决失衡的方法——旋转
左旋
右旋
3.4、四种情况对应的旋转方式
上一节中的左旋与右旋显然分别对应着RR与LL的情况，因此LL仅需要进行一次右旋便能重新平衡，RR仅需要进行一次左旋就能重新平衡。而LR与RL的情况则较为复杂，一次旋转并不能完成重新平衡，需要进行两次旋转
LL
LRRLRR
4、平衡二叉树实现
4.1、节点结构
class Node {
int val
;
Node left
;
Node right
;
int height
;
public Node(int val
) {
this.val
= val
;
height
= 1;
left
= null
;
right
= null
;
}
}
4.2、AVL树完整代码
public class AVLTree {
private Node rNode
;
private int getHeight(Node p
) {
return p
== null
? 0 : p
.height
;
}
public Node
rightRotate(Node base
) {
Node left
= base
.left
;
base
.left
= left
.right
;
left
.right
= base
;
base
.height
= Math
.max(getHeight(base
.left
), getHeight(base
.right
)) + 1;
left
.height
= Math
.max(getHeight(left
.left
), base
.height
) + 1;
return left
;
}
public Node
leftRotate(Node base
) {
Node right
= base
.right
;
base
.right
= right
.left
;
right
.left
= base
;
base
.height
= Math
.max(getHeight(base
.left
), getHeight(base
.right
)) + 1;
right
.height
= Math
.max(base
.height
, getHeight(right
.right
)) + 1;
return right
;
}
public Node
leftRightRotate(Node base
) {
base
.left
= leftRotate(base
.left
);
return rightRotate(base
);
}
public Node
rightLeftRotate(Node base
) {
base
.right
= rightRotate(base
.right
);
return leftRotate(base
);
}
public void add(int val
) {
rNode
= add(rNode
, val
);
}
private Node
add(Node root
, int val
) {
if (root
== null
) {
root
= new Node(val
);
} else {
if (val
< root
.val
) {
root
.left
= add(root
.left
, val
);
if (getHeight(root
.left
) - getHeight(root
.right
) > 1) {
if (val
< root
.left
.val
) {
root
= rightRotate(root
);
}
else {
root
= leftRightRotate(root
);
}
}
}
else if (val
> root
.val
) {
root
.right
= add(root
.right
, val
);
if (getHeight(root
.left
) - getHeight(root
.right
) < -1) {
if (val
> root
.right
.val
) {
root
= leftRotate(root
);
}
else {
root
= rightLeftRotate(root
);
}
}
} else {
System
.out
.println("插入的值已存在，请勿重复添加");
}
}
root
.height
= Math
.max(getHeight(root
.left
), getHeight(root
.right
)) + 1;
return root
;
}
public Node
get(int val
) {
Node p
= rNode
;
while (true) {
if (p
== null
) {
return null
;
} else {
if (p
.val
== val
) {
return p
;
} else if (val
< p
.val
) {
p
= p
.left
;
} else {
p
= p
.right
;
}
}
}
}
public void remove(int val
) {
rNode
= remove(rNode
, val
);
}
private Node
remove(Node root
, int val
) {
if (root
== null
) {
return null
;
}
if (val
== root
.val
) {
if (root
.left
!= null
&& root
.right
!= null
) {
if (root
.left
.height
< root
.right
.height
) {
int min
= minimum(root
.right
);
root
.val
= min
;
root
.right
= remove(root
.right
, min
);
} else {
int max
= maximum(root
.left
);
root
.val
= max
;
root
.left
= remove(root
.left
, max
);
}
}else{
Node tmp
= root
;
root
= root
.left
== null
? root
.right
: root
.left
;
tmp
= null
;
}
}
else if (val
< root
.val
) {
root
.left
= remove(root
.left
, val
);
if (getHeight(root
.left
) - getHeight(root
.right
) < -1) {
if (getHeight(root
.right
.left
) < getHeight(root
.right
.right
)) {
root
= leftRotate(root
);
}
else {
root
= rightLeftRotate(root
);
}
}
}
else {
root
.right
= remove(root
.right
, val
);
if (getHeight(root
.left
) - getHeight(root
.right
) > 1) {
if (getHeight(root
.left
.left
) > getHeight(root
.left
.right
)) {
root
= rightRotate(root
);
}
else {
root
= leftRightRotate(root
);
}
}
}
return root
;
}
private int maximum(Node root
) {
while (root
.right
!= null
) {
root
= root
.right
;
}
return root
.val
;
}
private int minimum(Node root
) {
while (root
.left
!= null
) {
root
= root
.left
;
}
return root
.val
;
}
public void preOrder() {
preOrder(rNode
);
System
.out
.println();
}
private void preOrder(Node root
) {
if (root
== null
) {
return;
}
preOrder(root
.left
);
System
.out
.print(root
.val
+ " ");
preOrder(root
.right
);
}
public void sequeueTrav() {
Queue
<Node> queue
= new LinkedList<Node>();
queue
.offer(rNode
);
while (!queue
.isEmpty()) {
Node tmp
= queue
.poll();
if (tmp
== null
) {
System
.out
.print("null ");
} else {
System
.out
.print(tmp
.val
+ " ");
queue
.offer(tmp
.left
);
queue
.offer(tmp
.right
);
}
}
System
.out
.println();
}
}
4.3、测试
public static void main(String
[] args
) {
AVLTree tree
= new AVLTree();
int[] array
= new int[]{2,1,0,3,4,5,6,16,15,14,13,12,11,10,8,9};
for (int i
:array
){
tree
.add(i
);
}
tree
.preOrder();
tree
.sequeueTrav();
tree
.add(7);
tree
.preOrder();
tree
.sequeueTrav();
tree
.remove(6);
tree
.preOrder();
tree
.sequeueTrav();
}
输出
0 1 2 3 4 5 6 8 9 10 11 12 13 14 15 16
6 3 13 1 5 11 15 0 2 4 null 9 12 14 16 null null null null null null 8 10 null null null null null null null null null null
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
6 3 13 1 5 9 15 0 2 4 null 8 11 14 16 null null null null null null 7 null 10 12 null null null null null null null null null null
0 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16
7 3 13 1 5 9 15 0 2 4 null 8 11 14 16 null null null null null null null null 10 12 null null null null null null null null
最初建立好的AVL树如下：
插入节点7后
删除节点6后
