数据结构|数据结构——平衡二叉树(AVL树)(java版)


文章目录

    • 1 引言
      • 1.1 为什么要有树结构?
    • 2 二叉搜索树
      • 2.1 定义
      • 2.2 性质
      • 2.3 节点结构
        • 代码定义:
      • 2.4 创建二叉搜索树
      • 2.5 查找
        • 查找流程:
        • 查找代码:
      • 2.6 插入
        • 插入流程:
        • 图解过程:
        • 代码实现:
      • 2.7 删除
        • (1)删除节点为叶子节点
        • (2) 删除的节点只有左子树
        • (3)删除的节点只有右子树
        • (4) 删除的节点既有左子树又有右子树。
        • 删除代码:
    • 3 平衡二叉树
      • 3.1 定义
        • 3.1.1 AVL
      • 3.2 平衡因子
      • 3.3 节点结构
      • 3.4 左旋与右旋
        • (1) 左旋
        • 图解过程:
        • (2)右旋
        • 图解过程:
      • 3.5 插入
        • (1) A的左孩子的左子树插入节点(LL)
        • 图解过程:
        • 代码实现:
        • (2) A的右孩子的右子树插入节点(RR)
        • 图解过程:
        • 代码实现:
        • (3) A的左孩子的右子树插入节点(LR)
        • 图解过程:
        • 代码实现:
        • (4) A的右孩子的左子树插入节点(RL)
        • 图解过程:
        • 代码实现:
        • 3.6 删除
        • 代码实现:
    • 4 结语
    • 推荐阅读

1 引言 二叉树是数据结构中的重点与难点,也是应用较为广泛的一类数据结构。二叉树的基础知识在之前的数据结构——二叉树基础中已经详细介绍。本篇文章将着重介绍两类二叉树二叉搜索树平衡二叉树
1.1 为什么要有树结构?
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

2 二叉搜索树 2.1 定义
二叉搜索树又称二叉查找树,亦称为二叉排序树。设x为二叉查找树中的一个节点,x节点包含关键字key,节点x的key值记为key[x]。如果y是x的左子树中的一个节点,则key[y] <= key[x];如果y是x的右子树的一个节点,则key[y] >= key[x]
2.2 性质
(1)若左子树不空,则左子树所有节点的值均小于它的根节点的值;
(2)若右子树不空,则右子树所有节点的值均大于它的根节点的值;
(3)左、右子树也分别为二叉搜索树
例如:下图所示的二叉树为一棵二叉搜索树
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

??例如:下图所示不是一棵二叉搜索树,因为节点40左孩子节点值为44不满足二叉搜索树的定义。
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

2.3 节点结构
二叉树的节点结构通常包含三部分,其中有:左孩子的指针右孩子指针以及节点元素。节点的图示如下:
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

代码定义:
private class Node{public E e; public Node left ,right; public Node(E e){ this.e = e; //元素 left = null; //左孩子 right = null; //右孩子 } }

2.4 创建二叉搜索树
现有序列:A = {61, 87, 59, 47, 35, 73, 51, 98, 37, 93}。根据此序列构造二叉搜索树过程如下:
(1)i = 0,A[0] = 61,节点61作为根节点;
??(2)i = 1,A[1] = 87,87 > 61,且节点61右孩子为空,故81为61节点的右孩子
??(3)i = 2,A[2] = 59,59 < 61,且节点61左孩子为空,故59为61节点的左孩子
??(4)i = 3,A[3] = 47,47 < 59,且节点59左孩子为空,故47为59节点的左孩子
??(5)i = 4,A[4] = 35,35 < 47,且节点47左孩子为空,故35为47节点的左孩子
??(6)i = 5,A[5] = 73,73 < 87,且节点87左孩子为空,故73为87节点的左孩子
??(7)i = 6,A[6] = 51,47 < 51,且节点47右孩子为空,故51为47节点的右孩子
??(8)i = 7,A[7] = 98,98 < 87,且节点87右孩子为空,故98为87节点的右孩子
??(9)i = 8,A[8] = 93,93 < 98,且节点98左孩子为空,故93为98节点的左孩子;创建完毕后如下图中的二叉搜索树
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

2.5 查找
查找流程: (1)如果树是的,则查找结束,无匹配返回false
(2)如果被查找的值和节点的值相等,查找成功,返回true
(3)如果被查找的值小于节点的值,递归查找左子树
(4)如果被查找的值大于节点的值,递归查找右子树
查找代码:
//看二分搜索树中是否包含元素e public boolean contains(E e){ return contains(root,e); }//看以node为根的二分搜索树中是否包含元素e , 递归算法 private boolean contains(Node node , E e){ if(node == null){ return false; } if(e.compareTo(node.e) == 0){ return true; }else if(e.compareTo(node.e) < 0){ return contains(node.left,e); }else{//e.compareTo(node.e) > 0 return contains(node.right , e); } }

使用二叉搜索树可以提高查找效率,其平均时间复杂度O(log2n)
2.6 插入
插入流程: (1)先检测该元素是否在树中已经存在。如果已经存在,则不进行插入
(2)若元素不存在,则进行查找过程,并将元素插入在查找结束的位置
图解过程: 数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

代码实现:
//向node为根的二分搜索树中插入元素E,递归算法 //返回插入新节点后二分搜索树的根 //如果node为null,则新建一个节点,然后把传入的值赋值上 //如果compareTo > 0则向它右子树插入元素,反之向左子树 //左子树和右子树重新赋值后,返回的node还是以node为根的二分搜索树 private Node add(Node node , E e){ if(node == null){ size ++; return new Node(e); }if(e.compareTo(node.e) < 0){ node.left = add(node.left,e); }else if(e.compareTo(node.e) > 0){ node.right = add(node.right,e); } return node; }

2.7 删除
(1)删除节点为叶子节点 删除叶子节点的方式最为简单,只需查找到该节点,直接删除即可。例如删除图2.4中的叶子节点37、节点51、节点60、节点73和节点93的方式是相同的。
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

(2) 删除的节点只有左子树 删除的节点只有左子树,将节点的左子树替代该节点位置。例如:删除图2.4中的98节点
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

(3)删除的节点只有右子树 删除的节点若只有右子树,将节点的右子树替代该节点位置。这种情况与删除左子树处理方式类似,不再赘述。
(4) 删除的节点既有左子树又有右子树。 数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

??若删除的节点既有左子树又有右子树,这种节点删除过程相对复杂。其流程如下:
??(1)遍历待删除节点左子树,找到其左子树中最大节点,即删除节点的前驱节点
??(2)将最大节点代替被删除节点
??(3)删除左子树中最大节点
??(4)左子树中删除最大节点一定为叶子节点或者仅有左子树。按照之前情形删除即可。
注:同样可以使用删除节点的右子树中最小节点,即后继节点代替删除节点,此流程与使用前驱节点类似。
删除代码:
//返回以node为根的二分搜索树的最小值所在的节点 private Node minimum(Node node){ if(node.left == null){ return node; } return minimum(node.left); }//从二分搜索树中删除元素为e的节点 public void remove(E e){ root = remove(root, e); }//删除以node为根的二分搜索树中值为e的节点,递归算法 //返回删除节点后新的二分搜索树的根 private Node remove(Node node , E e){ if(node == null){ return null; } if(e.compareTo(node.e) < 0){ node.left = remove(node.left ,e); return node; }else if(e.compareTo(node.e) > 0){ node.right = remove(node.right , e); return node; }else{// e == node.e//待删除节点左子树为空的情况 if(node.left == null){ Node rightNode = node.right; node.right = null; size --; return rightNode; }//待删除节点右子树为空的情况 if(node.right == null){ Node leftNode = node.left; node.left = null; size --; return leftNode; }//待删除节点左右子树均不为空的情况 //找到比待删除节点大的最小节点,即待删除节点右子树的最小节点 //用这个节点顶替待删除节点的位置 Node successor = minimum(node.right); //因为要替换删除节点的位置,所以删除节点右子树的最小节点 successor.right = removeMin(node.right); successor.left = node.left; size++; //将要删除节点的左右子树从二叉树中断开 node.left = node.right = null; //维护二叉树长度 size--; //返回新节点successor,让根节点指向新节点successor return successor; } }//删除掉以node为根的二分搜索树中的最小节点 //返回删除节点后新的二分搜索树的根 //把左孩子删除后,返回右孩子 private Node removeMin(Node node){ if(node.left == null){ Node rightNode = node.right; node.right = null; size --; return rightNode; } node.left = removeMin(node.left); return node; }

3 平衡二叉树 3.1 定义
二叉搜索树一定程度上可以提高搜索效率,但是当原序列有序,例如序列A = {1,2,3,4,5,6},构造二叉搜索树如下图所示。依据此序列构造的二叉搜索树为右斜树,同时二叉树退化成单链表,搜索效率降低为O(n)
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

??在此二叉搜索树中查找元素6需要查找6次二叉搜索树查找效率取决于树的高度,因此保持树的高度最小,即可保证树的查找效率。同样的序列A,改为下图所示方式存储,查找元素6时只需比较3次,查找效率提升一倍
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

??可以看出当节点数目一定,保持树的左右两端保持平衡树的查找效率最高。这种左右子树高度相差不超过1树为平衡二叉树
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

3.1.1 AVL 二分搜索树可能退化成链表,所以引入AVL平衡二叉树的概念,AVL树也是二分搜索树
3.2 平衡因子
定义:某节点的左子树与右子树的高度(深度)差即为该节点平衡因子(BF,Balance Factor)平衡二叉树不存在平衡因子大于1的节点。在一棵平衡二叉树中,节点平衡因子只能取-1、1或者0
?数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

下图蓝色部分为平衡因子黑色部分为层数
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

3.3 节点结构
定义平衡二叉树的节点结构:
private class Node{ public K key; public V value; public Node left,right; public int height; //深度,这里计算每个结点的深度,通过深度的比较可得出是否平衡public Node(K key,V value){//默认构造函数 this.key = key; this.value = https://www.it610.com/article/value; left = null; right = null; height = 1; } }

对于给定结点数为n的AVL树最大高度为O(log2n).
3.4 左旋与右旋
(1) 左旋 如下图所示的平衡二叉树
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

如在此平衡二叉树插入节点62,树结构变为:
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

??可以得出40节点左子树高度为1,右子树高度为3,此时平衡因子为-2树失去平衡。为保证树的平衡,此时需要对节点40做出旋转,因为右子树高度高于左子树,对节点进行左旋操作,流程如下:
??(1)节点右孩子替代此节点位置
??(2)右孩子左子树变为该节点右子树
??(3)节点本身变为右孩子左子树
图解过程: 数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

(2)右旋 右旋操作与左旋类似,操作流程为:
??(1)节点左孩子代表此节点
??(2)节点左孩子右子树变为节点左子树
??(3)将此节点作为左孩子节点右子树
图解过程: 数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

3.5 插入
假设一颗AVL 树的某个节点为A,有四种操作会使 A左右子树高度差大于 1,从而破坏了原有AVL 树的平衡性平衡二叉树插入节点的情况分为以下四种
(1) A的左孩子的左子树插入节点(LL) 例如:下图所示的平衡二叉树
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

节点A左孩子为BB左子树为D,无论在节点D左子树或者右子树中插入F均会导致节点A失衡。因此需要对节点A进行旋转操作A平衡因子为2值为正,因此对A进行右旋操作。
图解过程: 数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

代码实现:
//LL //不平衡的原因是左侧的左侧多添加了一个节点 if(balanceFactor > 1 && getBalanceFactor(node.left) >=0){ //返回递归的上一层,继续处理上一层的节点 //至此,新的根节点,就已经保证了,以这个根节点为根的, //整棵二叉树即是一个二分搜索树,又是一棵平衡二叉树 return rightRotate(node); }//获得节点node的平衡因子 private int getBalanceFactor(Node node){ if(node == null){ return 0; } return getHeight(node.left) - getHeight(node.right); } //获得节点node的高度 private int getHeight(Node node){ if(node == null){ return 0 ; } return node.height; }//对节点y进行向右旋转操作,返回旋转后新的根节点x //yx /// \向右旋转(y)/\ //xT4------------>zy /// \/ \/ \ //zT3T1 T2 T3 T4 /// \ //T1T2 private Node rightRotate(Node y){Node x = y.left; Node T3 = x.right; //向右旋转过程 x.right = y; y.left = T3; //更新height y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1; x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1; return x; }

(2) A的右孩子的右子树插入节点(RR) 如下图所示:插入节点F后,节点A平衡因子为-2,对节点A进行左旋操作。
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

图解过程: 数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

代码实现:
//RR if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0){ //新的根节点返回回去,返回给递归调用的上一层 //以这个新的根节点为根的二叉树,就满足了平衡二叉树,又满足了二分搜索树的性质 return leftRotate(node); }//获得节点node的平衡因子 private int getBalanceFactor(Node node){ if(node == null){ return 0; } return getHeight(node.left) - getHeight(node.right); } //获得节点node的高度 private int getHeight(Node node){ if(node == null){ return 0 ; } return node.height; }//对节点y进行向左旋转操作,返回旋转后新的根节点x //yx /// \向左旋转(y)/\ //T1x------------>yz /// \/ \/ \ //T2zT1 T2 T3 T4 /// \ //T3 T4 private Node leftRotate(Node y){Node x = y.right; Node T2 = x.left; //向左旋转过程 x.left = y; y.right = T2; //更新height y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1; x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1; return x; }

(3) A的左孩子的右子树插入节点(LR) 若A左孩子节点B右子树E插入节点F,导致节点A失衡
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

A平衡因子为2,若仍按照右旋调整,调整过程如下:
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

??经过右旋调整发现调整后树仍然失衡,说明这种情况单纯的进行右旋操作不能使树重新平衡。那么这种插入方式需要执行两步操作
??(1)对失衡节点A左孩子B进行左旋操作,即RR情形操作。
??(2)对失衡节点A右旋操作,即LL情形操作。
图解过程: 数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

代码实现:
//LR //左子树比右子树高,高度差比1大,所以是不平衡的 if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){ node.left = leftRotate(node.left); return rightRotate(node); }

(4) A的右孩子的左子树插入节点(RL) 右孩子插入左节点的过程与左孩子插入右节点过程类似,只需对右孩子进行LL操作,然后在对节点进行RR操作。
图解过程: 数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片
数据结构|数据结构——平衡二叉树(AVL树)(java版)
文章图片

代码实现:
//RL //右子树比左子树高,高度差比小于-1,所以是不平衡的 if(balanceFactor < -1 && getBalanceFactor(node.right) > 0){ node.right = rightRotate(node.right); return leftRotate(node); }

3.6 删除 平衡二叉树删除情况与二叉搜索树删除情况相同,同样分为以下四种情况
??(1)删除叶子节点
??(2)删除节点只有左子树
??(3)删除节点只有右子树
??(4)删除节点既有左子树又有右子树
??平衡二叉树节点删除与二叉搜索树删除方法一致,但是需要在节点删除后判断树是否仍然保持平衡,若出现失衡情况,需要进行调整。
代码实现:
//删除掉以node为根的二分搜索树中键为key的节点,递归算法 //返回删除节点后新的二分搜索树的根 private Node remove(Node node, K key){ if(node ==null){ return null; } Node retNode; if(key.compareTo(node.key) < 0){ node.left = remove(node.left,key); retNode = node; }else if(key.compareTo(node.key) > 0){ node.right = remove(node.right , key); retNode =node; }else { //key.compareTo(node.key) == 0 //待删除节点左子树为空的情况 if(node.left == null){ Node rightNode = node.right; node.right = null; size -- ; retNode = rightNode; } //待删除节点右子树为空的情况 else if(node.right == null){ Node leftNode = node.left; node.left = null; size -- ; retNode = leftNode; }else{ //待删除节点左右子树均不为空的情况 //找到比待删除节点大的最小节点,即待删除节点右子树的最小节点 //用这个节点顶替待删除节点的位置 Node successor = minimum(node.right); successor.right = remove(node.right, successor.key); successor.left = node.left; node.left = node.right = null; retNode = successor; } } if(retNode == null){ return null; }else{//更新height retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right)); //计算平衡因子 int balanceFactor = getBalanceFactor(retNode); //平衡维护 //LL //不平衡的原因是左侧的左侧多添加了一个节点 if(balanceFactor > 1 && getBalanceFactor(retNode.left) >=0){ //返回递归的上一层,继续处理上一层的节点 //至此,新的根节点,就已经保证了,以这个根节点为根的, //整棵二叉树即是一个二分搜索树,又是一棵平衡二叉树 return rightRotate(retNode); } //RR if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0){ //新的根节点返回回去,返回给递归调用的上一层 //以这个新的根节点为根的二叉树,就满足了平衡二叉树,又满足了二分搜索树的性质 return leftRotate(retNode); }//LR //左子树比右子树高,高度差比1大,所以是不平衡的 if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){ node.left = leftRotate(retNode.left); return rightRotate(retNode); }//RL if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0){ node.right = rightRotate(retNode.right); return leftRotate(retNode); }return retNode; } }

4 结语 平衡二叉树旋转问题是二叉树学习中的重点与难点,希望读者通过本文可以更好的理解二叉树的操作。
推荐阅读 【数据结构|数据结构——平衡二叉树(AVL树)(java版)】数据结构——二叉树基础

    推荐阅读