前言需要介绍
咱们从一个数列(1,2,3,4,5,6)，来阐明形成二叉排序树的一些问题
1.左子树全副为空， 从模式图所看，更像一个单链表
2.查问速度明显降低(因为须要顺次比拟)，不能施展BST
的劣势，因为每次还须要比拟左子树，其查问速度比单链表还慢
那么怎么办？
那么像这样的数列咱们能够是用解决方案--->均衡二叉树(AVL)
一、什么是均衡二叉树
根本介绍
1.均衡二叉树也叫均衡二叉搜寻树(Self balancing binary searchtree)又被称为AVL树， 能够保障查问效率较高。
有以下特点:
1.它是一颗空树或它的左右两个子树的高度差相对超过1
2.左右两个子树都是一棵均衡二叉树。
均衡二叉树的罕用实现:红黑树、AVL(算法)、替罪羊树、Treap、舒展树等。
哪些树是AVL树？为什么?
联合后面咱们介绍的AVL树特点剖析看看，当初你晓得了吗？
简略说来
均衡二叉树之所以将二叉排序树，调整为均衡状态，是为了在二叉排序树近似为链的状况下，加强其查找性能，升高工夫复杂度。
常见调整形式
常见的二叉均衡树调整均衡办法有：LL、LR、RR、RL
RR型介绍
以后这种状况图三，链式就须要均衡调整，否则则影响到查问的效率
均衡调整：一个根节点与两左右子节点的二叉排序树（如下图）
原本Mar节点再插入May时，还保持平衡：满足右子节点大于根节点
当插入麻烦节点Nov时平衡点被毁坏，且Nov节点是在根节点的右子树的右子树上
依据二叉排序的个性：右子树节点比以后节点大
咱们找到Mar、May、Nov的两头数，它们的大小关系是Mar<May<Nov
此时将May作为根节点，Mar作为左子树、Nov作为右子树进行调整
这时，这种插入即称说为RR插入，均衡调整也成为RR旋转（右单转）
LL型介绍
当插入麻烦节点Apr时平衡点被毁坏，且Apr节点是在Mar节点的左子树的左子树上
咱们找到Mar、Aug、Apr的两头数，它们的大小关系是Apr<Aug<Mar
此时将Aug作为根节点，Apr作为左子树、Mar作为右子树进行调整
这时，这种插入即称说为LL插入，均衡调整也成为LL旋转（左单转）
当然插入的节点也可能是左子节点或者右子节点
咱们发现其实进行旋转调整的时候呢
不肯定是根节点才进行旋转。在两头的节点Mar也是能够的
LR介绍
当插入麻烦节点Jan时平衡点被毁坏，且Jan节点是在May节点的左子树的右子树上
咱们找到May、Aug、Mar的两头数，它们的大小关系是Aug<Mar<May
此时将Mar作为根节点，Aug作为左子树、May作为右子树
且Mar>Aug、Jan<Mar 依据个性Jan作为Aug右子树进行调整
这时，这种插入即称说为LR插入，均衡调整也成为LR旋转
RL介绍
当插入麻烦节点Feb时平衡点被毁坏，且Feb节点是在Aug节点的右子树的左子树上
咱们找到Jan、Aug、Dec的两头数，它们的大小关系是Aug<Dec<Jan
此时将Dec作为根节点，Aug作为左子树、Jan作为右子树
且Jan>Dec、Feb>Dec 依据个性Feb作为Jan左子树进行调整
这时，这种插入即称说为RL插入，均衡调整也成为RL旋转
LL、RR、LR、RL四种模式办法怎么判断？
即看插入节点把谁毁坏了，跟被毁坏节点是什么关系？
是右边的右边？左边的左边？还是右边的左边？左边的右边？
然而须要留神的是：均衡调整后仍为二叉排序树
二、通过示例意识均衡二叉树的右旋转
给你一个数列{4,3,6,5,7,8}，让你可能高效的实现对数据的查问和增加
那么依照咱们之前的思路，先构建：一颗二叉排序树
二叉排序树的特点？
非叶子节点特点：左子节点的值比以后节点的值小，右子节点的值比以后节点的值大。
特地阐明:如果有雷同的值，能够将该节点放在左子节点或右子节点
回顾构建二叉排序树思路剖析
- 判断左子节点的值是否比以后节点的值小
- 否则判断右子节点的值比以后节点的值大
- 递归判断是否合乎左子节点、右子节点的条件
那么咱们后面剖析了在二叉排序树近似为链的状况下
1.从模式图所看，更像一个单链表
2.查问速度明显降低(因为须要顺次比拟)，不能施展BST的劣势
所以咱们须要进行调整:均衡状态加强其查找性能，升高工夫复杂度
咱们发现这颗二叉排序树左子树高度为1，左边子树高度为3
此时不合乎均衡二叉树的特点：它是一颗空树或它的左右两个子树的高度差相对超过1
依据下面介绍的四种均衡调整模式介绍，目前比拟合乎的是RR旋转
应用RR旋转图解案例思路剖析
咱们联合下面的图与RR旋转的思路一起来剖析以后的案例
未插入节点8时，还保持平衡：满足右子节点大于根节点
当插入麻烦节点8时平衡点被毁坏，且节点8是在根节点的右子树的右子树上
依据二叉排序的个性：右子树节点比以后节点大
咱们找到4、6、7的两头数，它们的大小关系是 4 < 6 < 7
此时将 6 作为根节点， 4 作为左子树、 7 作为右子树进行调整
RR旋转代码实现思路剖析
- 创立一个新节点newNode等于以后根节点root，值相等
- 新节点newNode的左子树设置为以后根节点root的左子树
- 新节点newNode的
右子树设置为以后根节点root的右子树的左子树
- 以后根节点root的值换为右子节点的值
- 以后根节点root的右子树设置成根节点root的
右子树的右子树
- 以后根节点root的左子树设置为新节点
示例代码实现
大家有没有发现，节点与子树之间的高度是要害的
并不是说退出一个节点得时候就进行旋转，而是左右两个子树的高度差相对超过1才去进行均衡调整
所以须要先实现事件是：统计以后树的高度、统计与左子树、或右子树的高度
那么咱们用代码实际来统计：树的高度、左子树高度、右子树高度
(节点代码、AVL代码可参考二叉排序树相干代码)
class Node{ int value; Node left; Node right; public Node(int value) { this.value = value; } /** * @param value 心愿删除的结点的值 * @return如果找到返回该结点，否则返回null */ public Node search(int value) { if(value == this.value) { //找到就是该结点 return this; } else if(value < this.value) {//如果查找的值小于以后结点，向左子树递归查找 //如果左子结点为空 if(this.left == null) { return null; } return this.left.search(value); } else { //如果查找的值不小于以后结点，向右子树递归查找 if(this.right == null) { return null; } return this.right. search(value); } } public Node searchParent(int value){ //如果以后节点是须要删除节点的父节点则返回 if((this.left!=null && this.left.value == value) || (this.right!=null && this.right.value == value)){ return this; }else{ //如果查找的值小于以后节点的值，并且以后节点的左子节点不为空 if(value <this.value && this.left!=null){ return this.left.searchParent(value); }else if(value >= this.value && this.right!=null){ //如果查找的值大于等于于以后节点的值，并且以后节点的右子节点不为空 return this.right.searchParent(value); }else { return null;//没有找到父节点，比如说节点7 } } } //增加节点办法 //递归形式增加节点，要满足二叉排序树的要求 //要求是：`左子节点的值比以后节点的值小，右子节点的值比以后节点的值大。` public void add(Node node) { if (node == null) { return; } //判断传入的节点的值，和以后节点值的关系 //增加的节点小于以后节点 if (node.value < this.value) { if (this.left == null) { this.left = node; } else { this.left.add(node); } } else {//增加的节点大于以后节点 if (this.right == null) { this.right = node; } else { this.right.add(node); } } } @Override public String toString() { return "Node{" +"value=" + value +'}'; } //中序遍历 public void infixOrder(){ if(this.left != null){ this.left.infixOrder(); } System.out.println(this); if(this.right != null){ this.right.infixOrder(); } }}class AVLTree { private Node root; public Node getRoot() { return root; } public void setRoot(Node root) { this.root = root; } //增加节点的办法 public void add(Node node){ if(root == null){ root = node; }else{ root.add(node); } } /** * @param node 传入的节点（当做新二叉排序树的根节点） * return 返回新跟节点的最小节点的值 */ public int delRigthTreeMin(Node node){ Node target = node; //循环的查找左子节点，找到最小值 while(target.left!=null) { target = target.left; } //删除最小值 delNode(target.value); //返回最小值 return target.value; } public void delNode(int value){ if(root == null){ System.out.println("以后根节点为空！无奈删除节点！"); return; }else{ //1.须要先找到删除的值的对应节点 Node targetNode = search(value); //如果没有找到须要删除的节点 if(targetNode == null){ System.out.println("对不起！没有找到删除节点信息！"); return; } //如果咱们发现根节点没有左子节点与右子节点 if(root.left == null && root.right == null){ root = null; return; } //找到targetNode 的父节点 Node parent = searchParent(value); //如果删除节点是叶子节点 if(targetNode.left == null && targetNode.right == null){ //判断删除节点是父节点的左子节点还是右子节点 if(parent.left!= null && parent.left.value == targetNode.value){ parent.left = null; }else if (parent.right!= null && parent.right.value == targetNode.value){ parent.right = null; } }else if (targetNode.left != null && targetNode.right != null){ int minValue = delRigthTreeMin(targetNode.right); targetNode.value = minValue;//重置值 }else{//删除只有一颗子树的节点 //如果删除节点的子节点是左子节点 if(targetNode.left !=null){ if(parent!=null){ //判断删除节点是父节点的左子节点还是右子节点 if(parent.left.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.left = targetNode.left; }else if (parent.right.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.right = targetNode.left; } }else{ root = targetNode.left; } }else if (targetNode.right != null){ //如果删除节点的子节点是右子节点 if(parent!=null){ //判断删除节点是父节点的左子节点还是右子节点 if( parent.left.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.left = targetNode.right; }else if (parent.right.value == targetNode.value){ //将原删除节点的地位给到子节点 parent.right = targetNode.right; } }else{ root = targetNode.right; } } } } } //查找须要删除节点的办法 public Node search(int value){ if(root == null){ return null; }else{ return root.search(value); } } //查找须要删除节点的父节点信息 public Node searchParent(int value){ if(root == null){ return null; }else{ return root.searchParent(value); } } //调用中序遍历的办法 public void infixOrder(){ if(root == null){ System.out.println("以后二叉排序根节点为空，无奈遍历"); return; }else{ root.infixOrder(); } }}如上图所示，咱们取的该这颗树的高度是为：3 ，算上根节点则是 4
所以咱们求该树的高度，须要晓得左节点与右节点的高度别离是多少
class Node{ //......省略其余要害代码 //返回以后节点的左子树的高度 public int leftHigth(){ if(left == null){ return 0; } return left.hight(); } //返回以后节点的右子树的高度 public int rightHight(){ if(right == null){ return 0; } return right.hight(); } //返回以后节点的高度，若算上根节点则须要 + 1 public int hight(){ return Math.max(left == null? 0 : left.hight(),right == null?0:right.hight()) + 1; } }有没有发现，咱们须要晓得左子树的高度是多少
同时也须要晓得左子树的左子树与左边子树是多少.....
这是一个始终递归的过程。
public static void main(String[] args) { int[] arr ={4,3,6,5,7,8}; AVLTree avlTree = new AVLTree(); for(int i = 0; i<arr.length; i++){ avlTree.add(new Node(arr[i])); } //遍历 System.out.println("中序遍历"); avlTree.infixOrder(); //节点高度 System.out.println("算上跟节点高度为："+avlTree.getRoot().hight());}运行后果如下：中序遍历Node{value=3}Node{value=4}Node{value=5}Node{value=6}Node{value=7}Node{value=8}算上跟节点高度为：4咱们刚刚也说了，算上跟根节点高度就是4，那么咱们看看左子树和右子树
//节点高度System.out.println("节点高度为："+avlTree.getRoot().hight());//节点高度System.out.println("左节点高度为："+avlTree.getRoot().leftHigth());//节点高度System.out.println("右节点高度为："+avlTree.getRoot().rightHight());运行后果如下：节点高度为：4左节点高度为：1右节点高度为：3咱们刚刚说到，左右两个子树的高度差相对超过1才去进行均衡调整，那么以后的状况则须要进行调整：右旋转
class Node{ //......省略其余要害代码 //RR旋转办法 private void RightRotate(){ //创立一个新节点newNode等于以后根节点root，值相等 Node newNode = new Node(value); //新节点newNode的左子树设置为以后根节点root的左子树 newNode.left = left; //新节点newNode的右子树设置为以后根节点root的右子树的左子树 newNode.right = right.left; //以后根节点root的值换为右子节点的值 value = right.value; //以后根节点root的右子树设置成根节点root的右子树的右子树 right = right.right; //以后根节点root的左子树设置为新节点 left = newNode; } //优化增加节点操作 public void add(Node node) { if (node == null) { return; } //判断传入的节点的值，和以后节点值的关系 //增加的节点小于以后节点 if (node.value < this.value) { if (this.left == null) { this.left = node; } else { this.left.add(node); } } else {//增加的节点大于以后节点 if (this.right == null) { this.right = node; } else { this.right.add(node); } } //当增加完一个节点后：如果（右子树的高度 - 左子树的高度）> 1 则执行RR旋转 if(rightHight() - leftHigth() > 1 ){ RightRotate();//执行RR旋转 } }}接下来咱们实际看看，当增加节点满足条件是否会进行均衡调整
public static void main(String[] args) { int[] arr ={4,3,6,5,7,8}; AVLTree avlTree = new AVLTree(); for(int i = 0; i<arr.length; i++){ avlTree.add(new Node(arr[i])); } //遍历 System.out.println("中序遍历"); avlTree.infixOrder(); //节点高度 System.out.println("节点高度为："+avlTree.getRoot().hight()); //节点高度 System.out.println("左节点高度为："+avlTree.getRoot().leftHigth()); //节点高度 System.out.println("右节点高度为："+avlTree.getRoot().rightHight());}运行后果如下：中序遍历Node{value=3}Node{value=4}Node{value=5}Node{value=6}Node{value=7}Node{value=8}节点高度为：3左节点高度为：2右节点高度为：2这时咱们进行均衡调整，从左右两个子树的高度差没有超过1了。
三、通过示例意识均衡二叉树的左旋转
给你一个数列{10,12,8,9,7,6}，让你可能高效的实现对数据的查问和增加
那么依照咱们之前的思路，先构建：一颗二叉排序树
二叉排序树的特点？
非叶子节点特点：左子节点的值比以后节点的值小，右子节点的值比以后节点的值大。
特地阐明:如果有雷同的值，能够将该节点放在左子节点或右子节点
回顾构建二叉排序树思路剖析
- 判断左子节点的值是否比以后节点的值小
- 否则判断右子节点的值比以后节点的值大
- 递归判断是否合乎左子节点、右子节点的条件
咱们发现这颗二叉排序树左子树高度为3，左边子树高度为1
此时不合乎均衡二叉树的特点：它是一颗空树或它的左右两个子树的高度差相对超过1
依据下面介绍的四种均衡调整模式介绍，目前比拟合乎的是LL旋转
依据咱们后面的示例教训，咱们能够间接进行实现思路剖析
- 创立一个新节点newNode等于以后根节点root，值相等
- 新节点newNode的右子树设置为以后根节点root的右子树
- 新节点newNode的
左子树设置为以后根节点root的左子树的右子树
- 以后根节点root的值换为左子节点的值
- 以后根节点root的左子树设置成根节点root的
左子树的左子树
- 以后根节点root的右子树设置为新节点
示例代码实现
class Node{ //......省略其余要害代码 //LL旋转办法 private void leftRotate(){ //创立一个新节点newNode等于以后根节点root，值相等 Node newNode = new Node(value); //新节点newNode的右子树设置为以后根节点root的右子树 newNode.right = right; //新节点newNode的`左子树`设置为以后根节点root的`左子树的右子树` newNode.left = left.right; //以后根节点root的值换为左子节点的值 value = left.value; //以后根节点root的左子树设置成根节点root的`左子树的左子树` left = left.left; //以后根节点root的右子树设置为新节点 right = newNode; } //优化增加节点操作 public void add(Node node) { if (node == null) { return; } //判断传入的节点的值，和以后节点值的关系 //增加的节点小于以后节点 if (node.value < this.value) { if (this.left == null) { this.left = node; } else { this.left.add(node); } } else {//增加的节点大于以后节点 if (this.right == null) { this.right = node; } else { this.right.add(node); } } //当增加完一个节点后：如果（右子树的高度 - 左子树的高度）> 1 则执行RR旋转 if(rightHight() - leftHigth() > 1 ){ RightRotate();//执行RR旋转 } //当增加完一个节点后：如果（左子树的高度 - 右子树的高度）> 1 则执行LL旋转 if(leftHigth() - rightHight() > 1 ){ leftRotate();//执行LL旋转 } }}接下来咱们Demo测试一下为调整之前的高度别离是多少
public static void main(String[] args) { //int[] arr ={4,3,6,5,7,8}; int[] arr ={10,12,8,9,7,6}; AVLTree avlTree = new AVLTree(); for(int i = 0; i<arr.length; i++){ avlTree.add(new Node(arr[i])); } //遍历 System.out.println("中序遍历"); avlTree.infixOrder(); //节点高度 System.out.println("节点高度为："+avlTree.getRoot().hight()); //节点高度 System.out.println("左节点高度为："+avlTree.getRoot().leftHigth()); //节点高度 System.out.println("右节点高度为："+avlTree.getRoot().rightHight());}运行后果如下：中序遍历Node{value=6}Node{value=7}Node{value=10}Node{value=9}Node{value=8}Node{value=12}节点高度为：3左节点高度为：2右节点高度为：2这时咱们进行均衡调整，从左右两个子树的高度差没有超过1了。
四、通过示例意识均衡二叉树的双旋转
给你一个数列{10,11,7,6,8,9}，让你可能高效的实现对数据的查问和增加
那么依照咱们之前的思路，先构建：一颗二叉排序树
咱们发现这颗二叉排序树左子树高度为3，左边子树高度为1
此时不合乎均衡二叉树的特点：它是一颗空树或它的左右两个子树的高度差相对超过1
依照咱们之前思路适宜的是LL旋转，那么咱们执行左旋后的样子发现是
那么呈现这种问题的起因是什么呢？
剖析1：退出节点九时，左子树（节点7）的树高度 > 右子树(节点11) 的高度
剖析2：左子树高度 - 右子树高度 >1 触发LL旋转，就变成下面那样了
那么咱们能够依据下面的LR介绍能够猜到一些思路，解决这个问题.
咱们在合乎：执行LL旋转时条件时
思路1.获取左子树的右子树（节点8）高度，取名为：k
思路2.获取左子树（节点7）的高度，取名为：J
思路3.如果 k > J，对左子树进行RR旋转
思路4.如果 k < J，间接进行LL旋转
简略的一句话：如果K>J，则先旋转子树再旋转本人
同时咱们在合乎：执行RR旋转时条件时
思路1.获取右子树的左子树高度 ，取名为：U
思路2.获取右子树（节点11）的高度，取名为：L
思路3.如果U > L，对右子树进行LL旋转
思路4.如果U < L，间接进行RR旋转
class Node{ //......省略其余要害代码 //优化增加节点操作 public void add(Node node) { if (node == null) { return; } //判断传入的节点的值，和以后节点值的关系 //增加的节点小于以后节点 if (node.value < this.value) { if (this.left == null) { this.left = node; } else { this.left.add(node); } } else {//增加的节点大于以后节点 if (this.right == null) { this.right = node; } else { this.right.add(node); } } //当增加完一个节点后：如果（右子树的高度 - 左子树的高度）> 1 则执行RR旋转 if(rightHight() - leftHigth() > 1 ){ //获取它的右子树的左子树的高度 取名U，获取它的右子树高度L //如果u > l 执行LL旋转 if(right != null && right.leftHigth()> right.rightHight()){ right.leftRotate();//执行LL旋转 RightRotate();//执行RR旋转 }else{ RightRotate(); } return;//避免接着往下走 } //当增加完一个节点后：如果（左子树的高度 - 右子树的高度）> 1 则执行LL旋转 if(leftHigth() - rightHight() > 1 ){ //获取左子树的右子树高度，取名为：k 获取左子树的高度，取名为：J //如果 k > J，对左子树进行RR旋转 if(left != null && left.rightHight() > left.leftHigth()){ left.RightRotate();//执行RR旋转 leftRotate();//执行LL旋转 }else{ leftRotate();//执行LL旋转 } } }}接下来让咱们应用Demo验证一下咱们的思路
public static void main(String[] args) { //int[] arr ={4,3,6,5,7,8}; int[] arr ={10,12,8,9,7,6}; AVLTree avlTree = new AVLTree(); for(int i = 0; i<arr.length; i++){ avlTree.add(new Node(arr[i])); } //遍历 System.out.println("中序遍历"); avlTree.infixOrder(); //节点高度 System.out.println("节点高度为："+avlTree.getRoot().hight()); //节点高度 System.out.println("左节点高度为："+avlTree.getRoot().leftHigth()); //节点高度 System.out.println("右节点高度为："+avlTree.getRoot().rightHight()); System.out.println("右节点高度为："+avlTree.getRoot().rightHight()); System.out.println("以后根节点为："+avlTree.getRoot()); System.out.println("以后根节点的左节点为："+avlTree.getRoot().left); System.out.println("以后根节点的右节点为："+avlTree.getRoot().right);}运行后果如下：中序遍历Node{value=6}Node{value=7}Node{value=8}Node{value=9}Node{value=10}Node{value=11}节点高度为：3左节点高度为：2右节点高度为：2以后根节点为：Node{value=8}以后根节点的左节点为：Node{value=7}以后根节点的右节点为：Node{value=10}