内容来自尚硅谷Java数据结构与java算法（Java数据结构与算法）_哔哩哔哩_bilibili

写在前面:本文内容大致和原视频内老师的笔记内容相同，会偶尔插入自己的注释和理解，尽量会完成作业

11.5平衡二叉树(AVL树)

11.5.1看一个案例(说明二叉排序树可能的问题)

给你一个数列{1,2,3,4,5,6}，要求创建一棵二叉排序树(BST)，并分析问题所在

左子树全部为空，从形式上看，更像一个单链表

1.      插入速度没有影响

2.      查询速度明显降低(因为需要依次比较)。

3.      不能发挥BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢，

4.      解决方案-平衡二叉树(AVL)

11.5.2基本介绍

1.      平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree）又被称为AVL树，可以保证查询效率较高。

2.      具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

3.      举例说明,看看下面哪些AVL树,为什么?

11.5.3应用案例-单旋转(左旋转)

要求:给你一个数列，创建出对应的平衡二叉树.数列{4,3,6,5,7,8}

思路分析(示意图)

代码实现

11.5.4应用案例-单旋转(右旋转)

要求:给你一个数列，创建出对应的平衡二叉树.数列{10,12,8,9,7,6}

思路分析(示意图)

代码实现

11.5.5应用案例-双旋转

前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列

int[]arr = { 10,11,7,6,8,9};运行原来的代码可以看到，并没有转成AVL树.

int[]arr= {2,1,6,5,7,3};//运行原来的代码可以看到，并没有转成AVL树

1.问题分析

2.解决思路分析

(1)当符号右旋转的条件时

(2)如果它的左子树的右子树高度大于它的左子树的高度

(3)先对当前这个结点的左节点进行左旋转

(4)在对当前结点进行右旋转的操作即可

代码实现(AVL树的完整汇总代码)