前言需要介绍
咱们从一个 数列(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}