【数据结构高阶】终于有人把AVL树给说清了

1.二叉搜索树回顾以及性能分析

1.1二叉搜索数的概念

二叉搜索树又被称为二叉排序树，它是一棵空树，或者是具有一下性质的二叉树

1. 若它的左子树不为空，则左子树上所有的节点的值都小于根节点的值。
2. 若它的右子树不为空，则右子树上所有的节点的值都大于根节点的值。
3. 它的左右子树也分别为二叉搜索树。图例：从上述概念以及图中可以看出，二叉搜索树具有以下的特性：- 二叉搜索树中最左侧的节点是树中最小的节点，最右侧的节点一定是数中最大的节点- 如果采用中序遍历的方式遍历二叉搜索树，可以遍历出一个有序的序列。

1.2 二叉搜索树的查找

既然将其称为二叉搜索树，因此这颗树主要是用来进行查找元素，而且查询的原理特别简单。具体如下：

题目在一棵二叉搜索树中，查找某个值，如果在树中存在这个元素，那么就返回true,否则返回false

图例：

插入和删除操作，都是建立在查找的基础上的。

1.3二叉树查询性能分析

插入和删除操作都必须先要查找，查找效率代表了二叉搜索树中各个操作的性能

对于n个节点的二叉搜索树，若每个元素查找的概率相等。则二叉搜索树的平均查找长度是节点在二叉搜索树的深度的函数，即节点越深，则比较次数越多。

但是对于相同的关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树。

图例：

最优条件下，二叉搜索树为完全二叉树，其平均比较次数为:log2N

最差条件下，二叉搜索树退化为单支树，其平均比较次数为:N/2

但是在图中我们也可以看到，当二叉搜索树退化成单支树的时候，二叉搜索树的性能就是去了。那么怎样才能改进，无论按照怎样的插入关键字码的顺序，都可以让二叉搜索树的性能最佳？

那么就要介绍今天的重头戏了，AVL树，当我们搜索二叉树中插入节点的时候，让加入节点之后的搜索二叉树是一颗平衡二叉树。那么这样就极大的提高了二叉搜索树的查找性能。

2.AVL树

2.1AVL树的概念

二叉搜索树虽然可以缩短查找的效率，但是如果插入这可二叉树是一组有序的序列，那么在最后形成的二叉树就是一棵单支数，我们在查找元素的时候就类似于在顺序表中查找元素，效率低下。因此我们的前辈们就发明出了一种解决上述问题的方法：当二叉搜索树中插入新节点之后，如果能保证每个节点的左右子树之差的绝对值不超过1(需要对书中的节点进行调整)，即可以降低树的高度，从而减少平均查找长度。

简单的说一棵AVL树，要么是一颗空树，要么就是满足一下性质的二叉搜索树

• 它的左右子树都是AVL树
• 左右子树盖度之差(简称平衡因子)的绝对中不超过1
• ​ 如果一棵二叉搜索树是高度平衡的，它就是AVL树，如果它有n个节点，其高度可保持在O(log2N),搜索时间复杂度就是O(log2N).

2.2AVL树节点的定义

为了实现二叉搜索树简单，AVL树节点在定义得时候维护一个平衡椅子，具体节点定义如下：

staticclassTreeNode{publicint val;//每个节点中的值publicint bf;//每个节点的平衡因子//当前节点的平衡因子，我们默认等于 右树的高度 - 左树的高度publicTreeNode parent;//指向父亲节点publicTreeNode left;//指向左孩子publicTreeNode right;//指向右孩子publicTreeNode(int val){this.val = val;}}

2.3AVL树的插入

AVL树就是在二叉搜索树的基础上引进了平衡因子，因此AVL树也可以看做数一棵二叉搜索树，那么AVL数的插入就可以分为两个步骤：

• 按照在搜索二叉树中的插入节点的方法进行插入节点
• 调整节点的平衡因子

• 插入节点的算法流程：当在一棵二叉树中插入节点的时候，如果这颗树还是空的，那么当前传进来的node节点赋为根节点即root = node。如果此时这颗树不为空，我们要到添加新节点的位置。因为这颗二叉树是二叉搜索树，在根节点的右边都是比根节点的值大的节点，在根节点的左边都是比根节点小的节点。此创建出一个cur节点，用于遍历这颗二叉树，创建出一个parent指向的节点用于跟踪cur节点. parent指针指向的节点时cur的父亲节点，创建初始的时候让cur = root.我们及当前传进来的节点为node.遍历节点的时候，如果node.val < cur.val 那么就在这颗树的左子树进行查找，如果node.val > cur.val 那么就在这颗树的右子树进行查找.否则在二叉树中就存在这个节点，就返回false.当cur == null的时候那就证明此时已经遍历完了二叉树的一支路径，此时要添加节点。而此时的parent指针指向的节点就是二叉树遍历一支路径之后的最后一个节点。此时让node.val 和 parent.val进行比较，如果parent.val > node.val那么parent.left = node,否则就是parent.right = node.因为我们的存储方式是，孩子父亲表示法，所以node/parent = parent.此时的cur = node。****图例：publicbooleaninsert(int val){TreeNode node =newTreeNode(val);//如果此时的跟节点为空，那么就是这棵二叉树还是空的if(root ==null){ root = node;returntrue;}TreeNode parent =null;TreeNode cur = root;while(cur !=null){if(node.val > cur.val){//进入右子树 parent = cur; cur = cur.right;}elseif(node.val == cur.val){returnfalse;}else{//进入左子树 parent = cur; cur = cur.left;}}//此时cur == null，parent指向的是叶子节点if(node.val > parent.val){ parent.right = node;}else{ parent.left = node;} node.parent = parent; cur = node;}

先按照二叉搜索树的规则将节点插入到AVL数中，但是新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要跟心平衡因子，并检测是否破坏了AVL数的平衡性

所以说当前的主要任务就是，我们要知道在这颗二叉搜索树中，那一个分支，子树不是平衡的，知道不平衡的树，把它改成平衡的树。

当在二叉搜索树中插入一个节点之后，我们就要更新它的平衡因子，在默认的情况下，每个节点对应的平衡因子是0，在插入一个节点之后，我们记新插入的这个节点为cur,cur 的父亲节点为parent,parent节点的父亲节点为Pparent.

图例：

• 我们可以分析一下，当插入的这个节点也就是cur,如果在插入节点指向parent节点没有左右孩子，那么就要根据cur.val和parent.val的大小，来判断parent节点的平衡因子在新添节点之后，会变成什么，如果cur节点时parent节点的左孩子，因为我们默认平衡因子 = 右子树的高度 - 左子树的高度。所以说此时的parent.bf就为1，如果cur节点是parent节点的右孩子，所以说此时parent.bf就为-1.
• 让我们分析一下，造成二叉搜索树不平衡的时候的平衡因子是多少？我们可以总结一下：- 如果parent节点的平衡因子为0，说明在插入node节点之后，把paren节点左后子树的节点的高度持平，所以现在满足AVL树的性质，插入成功。- 如果parent节点的平衡因子为±1，说明在插入node节点之前parent的平衡因子一定为0，在插入node 节点之后，以parent为根节点的二叉树的高度就增加了，需要继续继续向上更新。- 如果此时parent的平衡因子为±2，那么就违背了AVL树的性质，所以现在要进行旋转处理，让二叉树的高度降下来。

while(parent !=null){//如果cur 是父亲的右孩子，父亲的平衡因子++if(cur == parent.right){
        parent.bf++;}elseif(cur == parent.left){
        parent.bf--;}//如果平衡因子的值等于0，那么就证明这棵树是平衡的，直接退出if(parent.bf ==0){break;}elseif(parent.bf ==-1|| parent.bf ==1){//向上进行调整
        cur = parent;
        parent = cur.parent;}elseif(parent.bf ==2){if(cur.bf ==1){//进行左旋rotateLeft(parent);}else{rotateRightLeft(parent);}}elseif(parent.bf ==-2){if(cur.bf ==-1){//进行右旋rotateRight(parent);}else{rotateLeftRight(parent);}}}

2.4AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新的节点，可能造成不平衡，此时必须调整数的结构。使二叉搜索树平衡话。根据节点插入位置的不同，AVL树的旋转分为4种.

2.4.1右单旋

新节点插入较高左子树的左侧-右单旋

这种情况是当parent节点没有父亲节点的前提之下：

还有一种情况，就是其实在上述的图中subLR其实这个节点可以没有。还有我们的上述的图中的二叉搜索树仅仅是一棵子树，parent节点还会有自己的父亲节点

还是上图举例：

贴代码：

publicvoidrotateRight(TreeNode parent){TreeNode subL = parent.left;TreeNode subLR = subL.right;//当前的这个parent节点，不一定使用棵树的跟节点，可能是一棵树的跟节点，也可能是一棵树的子树//进行旋转
    parent.left = subLR;if(subL.right !=null){
        subLR.parent = parent;}
    subL.right = parent;TreeNodePparent= parent.parent;
    parent.parent = subL;//如果此时Pparent == null 那么就证明此时这个parent节点就是一棵树的根节点if(parent == root){
        root = subL;
        root.parent =null;}else{if(Pparent.left == parent){Pparent.left = subL;}else{Pparent.right = subL;}
        subL.parent =Pparent;}//修改平衡因子
    subL.bf =0;
    parent.bf =0;}

2.4.2 左单旋

新节点插入较高右子树–左单旋

贴代码：

//左旋publicvoidrotateLeft(TreeNode parent){TreeNode subR = parent.right;TreeNode subRL = subR.left;
    parent.right = subRL;
    subR.left = parent;if(subRL !=null){
        subRL.parent = parent;}TreeNodePparent= parent.parent;
    parent.parent = subR;if(parent == root){
        root = subR;
        root.parent =null;}else{if(Pparent.left == parent){Pparent.left = subR;}else{Pparent.right = subR;}
        subR.parent =Pparent;}
    subR.bf =0;
    parent.bf =0;}

2.4.3 左右双旋

//左右双旋publicvoidrotateLeftRight(TreeNode parent){TreeNode subL = parent.left;TreeNode subLR = subL.right;int bf = subLR.bf;//先进行简单左旋，再进行简单右旋rotateLeft(parent.left);rotateRight(parent);//对平衡因子进行修改if(bf ==-1){
        subLR.bf =0;
        parent.bf =1;
        subL.bf =0;}elseif(bf ==1){
        subL.bf =-1;
        parent.bf =0;
        subLR.bf =0;}}

2.4.4右左双旋

贴代码：

//右左双旋publicvoidrotateRightLeft(TreeNode parent){//先进行简单右旋，在进行简单左旋TreeNode subR = parent.right;TreeNode subRL = subR.left;int bf = subRL.bf;rotateRight(parent.right);rotateLeft(parent);if(bf ==-1){
        parent.bf =0;
        subRL.bf =0;
        subR.bf =1;}elseif(bf ==1){
        parent.bf =-1;
        subR.bf =0;
        subRL.bf =0;}}

2.5AVL树的验证

• 因为AVL树同时也是一个二叉搜索树，我们知道二叉搜索树的中序遍历之后可以得到一个有序序列，所以通过这个验证我们创建出来的AVL树是不是一个二叉搜索树。
• 因为AVL树同时也是一个二叉平衡树，在二叉平衡数中，左树的高度-右树的高度的绝对值要小于等于1，其实这也是leetcode上面的移到算法题。

//使用中序遍历，判断AVL树是不是二叉搜索树publicvoidin_order(TreeNode root){if(root ==null){return;}in_order(root.left);System.out.println(root.val);in_order(root.right);}//得到一棵树的最大深度publicintgetMaxHeight(TreeNode root){if(root ==null){return0;}int leftHeight =getMaxHeight(root.left);int rightHeight =getMaxHeight(root.right);return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}//判断AVL树是否为二叉平衡树publicbooleanisBalance(TreeNode root){if(root ==null){returntrue;}int leftHeight =getMaxHeight(root.left);int rightHeight =getMaxHeight(root.right);//在这个地方一定要进行判断，因为在二叉树中每个节点的平衡因子是我们手动给予的，所以可能会产生错误，在这里用树的高度之差进行验证if(rightHeight - leftHeight != root.bf){System.out.println("avl树存在异常");System.out.println("异常节点为 "+ root.val);}returnMath.abs(leftHeight - rightHeight)<=1&&isBalance(root.left)&&isBalance(root.right);}

publicstaticvoidmain(String[] args){AvlTree avlTree =newAvlTree();int[]array ={16,3,7,11,9,26,18,14,15};for(int i =0;i<array.length;i++){
        avlTree.insert(array[i]);}
    avlTree.in_order(avlTree.root);for(int i =0;i<array.length;i++){
        avlTree.insert(array[i]);}System.out.println(avlTree.isBalance(avlTree.root));}

运行结果：

2.6AVL树的删除

因为AVL树也是二叉搜索树，可以按照二叉搜索树的方式将节点删除，然后在更新平衡因子，只不过于删除不同的是，删除节点后的平衡因子要被更新，最差情况下一直要调整到根节点的位置。

• 找到需要删除的节点
• 按照搜索树的删除规则删除节点
• 更新平衡因子，如果出现了不平衡，进行旋转

2.7AVL树的性能分析

AVL树是一颗绝对平衡的二叉搜索树，器要求每个节点的左右子树的高度差都不超过1，这样可以保证查询是高效的时间复杂度。即log2N,但是如果要对AVL树做一些结果修改的操作，性能非常低下，比如：插入时要维护其绝对品恒，旋转的次数比较多，更差的是删除的时候，有可能一直要让旋转持续到根节点的位置，因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变),可以考虑AVL树，但一个结构经常修稿，就不太适合。