目录
二叉树
二叉搜索树的查找方式:
AVL树
AVL树节点的实现
AVL树节点的插入操作
AVL树的旋转操作
右旋转:
左旋转:
左右双旋:
右左双旋:
AVL树的不足和下期预告(红黑树)
二叉树
了解AVL树之前,需要先了解一下二叉搜索树的概念,二叉搜索树具有以下性质:
1,如果左子树不为空,则左子树上所有节点的值都小于跟节点的值。
2,如果右子树不为空,则右子树的所有节点的值都大于跟节点的值。
3,根节点的左右子树也是一颗二叉搜索树。
如果使用二叉树的中序遍历方法来遍历一颗二叉树,则可以得到一个有序的序列。
二叉搜索树的查找方式:
根据上图可以对二叉树进行查找从而得到我们想要的节点。
一个完全二叉树的查找效率可以达到 级别,但如果我们插入的数值都是大于根节点的数值,并且是严格递增的,那么此时整个二叉树就会退化成一个链表的结构,那么此时查找的效率也会退化成。因此我们就需要考虑一个问题,无论何时进行插入,都可以让二叉树,保持左右子树的相对平衡,随时更改根节点,这样就可以让查找的时间复杂度一直保持在,所以研究者引入了AVL树的概念。
AVL树
在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis,他们在1962年的论文《An algorithm for the organization of information》中发表了它。
AVL树它本质上其实还是一个二叉树,它的特点符合二叉树的所有特点,在此之外,AVL树还具有平衡的性质,也就是说,它的左子树和右子树的高度差的绝对值不会大于1,因此这样也就保证了AVL树的查找效率。
AVL树节点的实现
为了实现AVL树,我们需要先定义树的节点,和普通的二叉树不同,在定义节点的时候,我们也需要在其中定义一个平衡因子,我们使用bf(balance factor)来表示:AVL树的节点定义如下:
class TreeNode{
//定义树的左右节点索引和父亲索引
public TreeNode left = null;
public TreeNode right = null;
public TreeNode parent = null;
public int val;
public int bf;
//定义构造函数
public TreeNode (int val){
this.val = val;
}
}
我们定义当前节点的平衡因子 = 右树的高度 - 左树的高度。如果当前节点的bf<0,那么左树就高,bf>0右树就高。bf = 0,那么两边一样高。当然这只是其中的一种实现方式而已(本文是这么定义的)。
AVL树节点的插入操作
首先,我们将其分为两步
1,按照二叉树的插入方式进行插入。
2,对不满足条件的节点进行旋转,使树达到平衡。
此时可以看下接下来这几幅图:
假设我要在二叉树种插入一个值为100,那么此时我应该找到100应该插入到哪个位置,每一次寻找定义cur为要插入的位置,定义parent为cur的父亲节点,那么遍历下来就可以找到插入的位置,此时代码如下:
public TreeNode root ;
public void insert(int val){
//1,首先先进行节点的插入操作;
TreeNode node = new TreeNode(val);
if(this.root == null){
//如果树为空,那么node就是新的root
this.root = node;
}else{
TreeNode parent = null;
TreeNode cur = this.root;
// 1.1 先判断要插入的位置,然后再进行插入
while(cur != null){
if(cur.val < val){
parent = cur;
cur = cur.right;
} else if (cur.val == val) {
return;
}else{
parent = cur;
cur = cur.left;
}
}
//此时找到了要插入的位置,对node进行插入,插入的位置为parent所指向的节点
//判断往左边插入还是右边插入,然后再让node指回去。
if(parent.val < val){
parent.right = node;
}else{
parent.left = node;
}
node.parent = parent;
cur = node;
}
}
一定要让node指向指回去,否则子节点会丢失父节点的索引。
AVL树的旋转操作
基于以上的插入,我们可以发现一个问题,就是说,如果每次都插入比上一次大的值,那么势必会让这个树退化成一个链表,那么此时树的存储结构优势将会丢掉,所以AVL树引入了旋转操作来对树进行操作。从而使得这棵树不会退化成链表。
cur插入后,parent的平衡因子一定需要调整,
在插入之前,parent的平衡因子分为三种情况:-1,0, 1
插入时分以下两种情况:
1. 如果cur插入到parent的左侧,只需给parent的平衡因子 -1 即可
2. 如果cur插入到parent的右侧,只需给parent的平衡因子 +1 即可
此时:parent的平衡因子可能有三种情况:0,正负1, 正负2
1. 如果parent的平衡因子为0,说明插入之前parent的平衡因子为正负1,插入后被调整成0,此时满足AVL树的性质,插入成功
2. 如果parent的平衡因子为正负1,说明插入前parent的平衡因子为0,插入后被更新成正负1,此时以parent为根的树的高度增加,需要继续向上更新
3. 如果parent的平衡因子为正负2,则parent的平衡因子违反平衡树的性质,需要对其进行旋转处理
此时更新操作就如下:
while(){
//更新parent的平衡因子
if(cur == parent.right){
parent.bf++;
}else{
parent.bf--;
}
//更新后的平衡因子为0,说明插入后的结果是平衡的,此时无需后续操作
if(parent.bf == 0){
return;
}
if(parent.bf != 1 && parent.bf != -1){
//此时需要继续向上更新
if(parent.bf == 2){
if(cur.bf == 1){
// parent.bf == 2 cur.bf == 1
}else{
// parent.bf == 2 cur.bf == -1
}
}else{
if(cur.bf == 1){
// parent.bf == -2 cur.bf == 1
}else{
// parent.bf == -2 cur.bf == -1
}
}
}
}
那么基于以上操作,我们的更新平衡因子的模板已经搭好了,但是在什么情况下需要进行旋转呢?
右旋转:
假设有上面这种情况,原来的cur.bf == 0 , 但是parent.bf == -1 ,此时在左树的最左边插入一个节点,那么此时的节点情况就变成了cur.bf == -1 , parent.bf == -2 。那么此时就需要对parent节点进行右旋转,从而调整树的结构。
此时需要注意以下几点:
1. 30 节点的右孩子可能存在,也可能不存在。
2. 60 可能是根节点,也可能是子树。如果是根节点,旋转完成后,要更新根节点 如果是子树,可能是某个节点的左子树,也可能是右子树。
在上图中可以看出,当我们想进行右转操作时,需要将parent.left 标记为 subL,将subL.right标记为subLR.
从2图转换为3图可以如上图表示:
1. 修改parent.left = subLR;
2. 修改subL.right = parent;
3. 修改 subLR.parent = parent (此时需要判断subLR是否为空)
4. 保存parent的父亲节点(祖父节点)
5. 修改parent的父亲节点指向subL;
6. 修改祖父节点指向subL(需要确认祖父节点是否存在,如果不存在则parent是根节点)
7. 修改subL.parent属性为祖父节点;
8. 判断完了之后还要修改平衡因子。
代码如下:
private void rotateRight(TreeNode parent) {
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
parent.left = subLR;
subL.right = parent;
if(subLR != null){
subLR.parent = parent;
}
TreeNode pParent = parent.parent;
parent.parent = subL;
if(parent == this.root){
this.root = subL;
this.root.parent = null;
}else{
if(pParent.left == parent){
pParent.left = subL;
}else{
pParent.right = subL;
}
subL.parent = pParent;
}
subL.bf = 0;
parent.bf = 0;
}
左旋转:
左旋转和右旋转的逻辑是一样的,不过是对称的操作。以下是左旋转的代码演示:
此时最初的parent的bf值为1,进行添加节点之后,则是会变成parent.bf 会变成2,此时的cur.bf
会变成1(因为给cur的右树增加了一层)。此时就需要用到左旋转的方法来进行旋转,从而降低AVL树的高度了。具体代码如下:和右旋转是对称的
private void rotateLeft(TreeNode parent) {
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
parent.right = subRL;
subR.left = parent;
if(subRL != null){
subRL.parent = parent;
}
TreeNode pParent = parent.parent;
parent.parent = subR;
if(parent == this.root){
this.root = subR;
this.root.parent = null;
}else{
if(pParent.left == parent){
pParent.left = subR;
}else{
pParent.right =subR;
}
subR.parent = pParent;
}
subR.bf = parent.bf = 0;
}
左右双旋:
讲完了上述两种比较简单的情况,其实还有两种比较复杂的情况,比如说,
假如说是上面这种情况呢,此时我要插入的值为40,但是60节点bf更新为-2,此时的30这个节点的bf值为1,50节点bf值为-1,这时候单纯的旋转已经无法解决这些问题了。因此
此时先对30进行左旋转:可以得到50节点bf为-2,60节点 bf 为-2,30节点 bf 为 0
此时再对60节点进行右旋转:此时的50节点 bf 为 0 ,60节点bf为 1 此时的 AVL树已经达到了平衡。
private void rotateLR(TreeNode parent) {
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
int bf = subLR.bf;
this.rotateRight(parent.left);
this.rotateLeft(parent);
if (bf == -1) {
parent.bf = 1;
subL.bf = 0;
subLR.bf = 0;
} else if (bf == 1) {
subL.bf = -1;
subLR.bf = 0;
parent.bf = 0;
}
}
右左双旋:
和左右双旋是对称的概念,此处便不再赘述了。
直接贴代码:
private void rotateRL(TreeNode parent) {
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
int bf = subRL.bf;
this.rotateRight(parent.right);
this.rotateLeft(parent);
if(bf == 1){
parent.bf = -1;
subR.bf = 0;
subRL.bf = 0;
} else if (bf == -1) {
parent.bf = 0;
subR.bf = 1;
subRL.bf =0;
}
}
总之AVL树,就是为了让整个树不退化成链表,才引入的旋转机制。
AVL树的不足和下期预告(红黑树)
但是AVL树虽然保证了查询的效率,但是还是有一些机制上的问题,比如说,旋转非常消耗时间,比如我们在单旋的时候已经进行了8步操作,这只是其中的一次插入,当数据大量插入的时候AVL树显然是不够用的,因此科学家们又引入了红黑树的机制。下一次我会继续写关于红黑树的博客,希望大家能够多多点赞。