AVL树
一、定义
VL树是一种最早被发明的自平衡二叉搜索树，由苏联的数学家 Adelson-Velsky 和 Landis 于 1962 年提出。AVL树通过保持树的平衡性来确保各种操作的平均时间复杂度为 O(log n)，其中 n 是树中节点的数量。下面详细描述AVL树的特点、性质和操作。
avl树是最早的平衡二叉搜索树之一，有人称"艾薇儿树"
二、特点和性质
- 平衡性：AVL树保持了左右子树的高度差不超过1的特性，即对于树中的每个节点，其左子树的高度和右子树的高度之差的绝对值不超过1。
- 二叉搜索树性质：除了保持平衡外，AVL树仍然满足二叉搜索树的基本性质，即左子树的所有节点都小于根节点，右子树的所有节点都大于根节点。
- 插入和删除操作的平均复杂度：在AVL树中，插入和删除操作的平均时间复杂度为 O(log n)，这是由于树的平衡性质保证了树的高度较低，从而插入和删除操作只需要对树进行少量的调整。
- 旋转操作：为了保持树的平衡性，AVL树使用四种基本的旋转操作：左旋、右旋、左右旋和右左旋。这些旋转操作通过重新调整节点的位置来确保树的平衡。
三、平衡特性
3.1 平衡因子
平衡因子：某节点的左右子树高度差。左子树高度 - 右子树高度
- avl树的每个节点的平衡因子只能是1、0、-1，绝对值≤1，如果超过1，称为失衡。
- 每个节点的高度差不超过1。
- 搜索、添加、删除的复杂度是O(logN)
3.2 恢复平衡
平衡的树：
下述失去平衡的树最后都会变成如下的平衡树：
┌──d──┐
│ │
┌─b─┐ ┌─f─┐
│ │ │ │
a c e g3.2.1 LL
原树：
┌─---f---─┐
│ │
┌──d──┐ g
│ │
┌─b─┐ e
│ │
a c将f节点进行右旋转，最后恢复平衡
3.2.2 RR
原树：
┌─---b---─┐
│ │
a ┌──d──┐
│ │
c ┌─f─┐
│ │
e g将b节点进行左旋转，最后恢复平衡
3.2.3 LR（LLRR）
原树：
┌─---f---─┐
│ │
┌──b──┐ g
│ │
a ┌─d─┐
│ │
c e先将b节点进行向左旋转，然后再将f节点进行右旋转，最后恢复平衡
3.2.4 RL（RRLL）
原树：
┌─---b---─┐
│ │
a ┌──f──┐
│ │
┌─d─┐ g
│ │
c e先将f节点进行右旋转，然后再将b节点进行左旋转，最后恢复平衡
四、应用场景
AVL树广泛应用于需要高效的插入、删除和查找操作的场景，特别是在内存中的数据结构和需要高性能的数据库系统中，例如：
- 数据库系统中的索引结构；
- 编辑器中的自动补全功能；
- 编译器和解释器中的符号表实现；
- 网络路由表的实现；
- 文件系统中的文件索引结构。
五、实现
/**
* @Description avl树
* @Author lcy
* @Date 2020/11/17 11:13
*/
public class AVLTree<E> extends BalanceBinarySearchTree<E> {
public AVLTree(Comparator<E> comparator){
super(comparator);
}
public AVLTree(){
super(null);
}
@Override protected void afterAdd(Node<E> node){
//往上搜索二叉树
while ((node = node.parent) != null) {
//判断是否平衡
if (isBalance(node)) {
//更新高度
updateHeight(node);
} else {
//找到失衡节点--恢复平衡，整颗树也跟着恢复平衡
restoreBalanceNew(node);
break;
}
}
}
@Override protected void afterRemove(Node<E> node){
//往上搜索二叉树
while ((node = node.parent) != null) {
//判断是否平衡
if (isBalance(node)) {
//更新高度
updateHeight(node);
} else {
//找到失衡节点--恢复平衡
restoreBalanceNew(node);
//不调用break是因为需要更新祖父节点的高度
}
}
}
/**
* 恢复平衡
* @param imbalanceNode 失衡节点对象
* @author lcy
* @date 2020/11/18 10:52
**/
private void restoreBalance(Node<E> imbalanceNode){
//获取失衡节点的子节点,即添加节点的父节点
Node<E> parentNode = ((AvlNode<E>)imbalanceNode).tallChild();
//添加的节点
Node<E> node = ((AvlNode<E>)parentNode).tallChild();
//L
if (parentNode.isLeftChild()) {
//如果是LR，先左旋转。
if (node.isRightChild()) {
rotateLeft(parentNode);
}
//如果是LL，则直接右旋转失衡节点，如果是LR先左旋转parent节点后再右旋转失衡节点
rotateRight(imbalanceNode);
} else {
//如果是RL，先右旋转。
if (node.isLeftChild()) {
rotateRight(parentNode);
}
//如果是RR，则直接左旋转失衡节点，如果是RL先右旋转parent节点后再左旋转失衡节点
rotateLeft(imbalanceNode);
}
}
/**
* 恢复平衡--新方法
* @param imbalanceNode 失衡节点对象
* @author lcy
* @date 2020/11/18 10:52
**/
private void restoreBalanceNew(Node<E> imbalanceNode){
//获取失衡节点的子节点,即添加节点的父节点
Node<E> parentNode = ((AvlNode<E>)imbalanceNode).tallChild();
//添加的节点
Node<E> node = ((AvlNode<E>)parentNode).tallChild();
if (parentNode.isLeftChild()) {
//如果是LR，先左旋转。
if (node.isRightChild()) {
//LR
// ┌─---f---─┐
// │ │
//┌──b──┐ g
//│ │
//a ┌─d─┐
// │ │
// c e
rotate(imbalanceNode,parentNode,node.left,node,node.right,imbalanceNode);
} else {
//LL
// ┌─---f---─┐
// │ │
// ┌──d──┐ g
// │ │
//┌─b─┐ e
//│ │
//a c
rotate(imbalanceNode,node,node.right,parentNode,parentNode.right,imbalanceNode);
}
} else {
//RL
//┌─---b---─┐
//│ │
//a ┌──f──┐
// │ │
// ┌─d─┐ g
// │ │
// c e
if (node.isLeftChild()) {
rotate(imbalanceNode,imbalanceNode,node.left,node,node.right,parentNode);
} else {
//RR
//┌─---b---─┐
//│ │
//a ┌──d──┐
// │ │
// c ┌─f─┐
// │ │
// e g
rotate(imbalanceNode,imbalanceNode,parentNode.left,parentNode,node.left,node);
}
}
}
@Override protected void rotateLeft(Node<E> node){
super.rotateLeft(node);
//更新两个节点高度，先更新节点最高的
updateHeight(node);
updateHeight(node.parent);
}
@Override protected void rotateRight(Node<E> node){
super.rotateRight(node);
//更新两个节点高度，先更新节点最高的
updateHeight(node);
updateHeight(node.parent);
}
@Override protected void rotate(Node<E> root,Node<E> b,Node<E> c,Node<E> d,Node<E> e,Node<E> f){
super.rotate(root,b,c,d,e,f);
//更新高度
updateHeight(b);
updateHeight(f);
updateHeight(d);
}
@Override protected Node<E> createNode(E element,Node<E> parent){
return new AvlNode<>(element,parent);
}
/**
* 判断节点是否平衡
* @param node 节点值
* @return boolean
* @author lcy
* @date 2020/11/18 9:03
**/
public boolean isBalance(Node<E> node){
return Math.abs(((AvlNode<E>)node).balanceFactor()) < 2;
}
/**
* 更新AVL树节点的高度
* @param node 节点
* @author lcy
* @date 2020/11/20 9:14
**/
private void updateHeight(Node<E> node){
((AvlNode<E>)node).updateHeight();
}
/**
* 树节点内部类
* @author lcy
* @date 2020/9/7 10:22
**/
protected static class AvlNode<E> extends Node<E> {
int height = 1;
public AvlNode(E element,Node<E> parent){
super(element,parent);
}
/**
* 获取节点的平衡因子
* @return int
* @author lcy
* @date 2020/11/18 8:57
**/
public int balanceFactor(){
int leftHeight = left == null ? 0 : ((AvlNode<E>)left).height;
int rightHeight = right == null ? 0 : ((AvlNode<E>)right).height;
return leftHeight - rightHeight;
}
/**
* 获取节点的平衡因子
* @author lcy
* @date 2020/11/18 8:57
**/
public void updateHeight(){
int leftHeight = left == null ? 0 : ((AvlNode<E>)left).height;
int rightHeight = right == null ? 0 : ((AvlNode<E>)right).height;
//更新自己的高度
height = 1 + Math.max(leftHeight,rightHeight);
}
/**
* 获取传入节点的最高高度的子节点
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.Node<E>
* @author lcy
* @date 2020/11/18 15:13
**/
public Node<E> tallChild(){
//左子节点高度
int leftHeight = left == null ? 0 : ((AvlNode<E>)left).height;
//右子节点高度
int rightHeight = right == null ? 0 : ((AvlNode<E>)right).height;
if (leftHeight > rightHeight) {
return left;
} else if (leftHeight < rightHeight) {
return right;
} else {
return isLeaf() ? left : right;
}
}
@Override public String toString(){
return element.toString();
}
}
public static void main(String[] args){
int[] ageArray = {44,31,3,2,6,88,34,13,32,77,74,35,89,1,78,53,12,23,67,54,34,98,78,67,78,90,97,124,266,243,4,5,7,9,45,33,8};
int[] weightArray = {144,131,103,102,106,188,134,113,132,177,174,135,189,1,78,53,12,23,67,54,34,98,78,67,78,90,97,124,266,243,4,5
,7,9,45,33,8};
AVLTree<Person> avlTree = new AVLTree<>(Comparator.comparingInt(Person :: getAge));
for (int i = 0; i < ageArray.length; i++) {
avlTree.add(new Person(ageArray[i],weightArray[i],String.valueOf(i)));
}
System.out.println("-------------print-------------");
BinaryTrees.print(avlTree);
System.out.println();
avlTree.remove(new Person(7,7,""));
BinaryTrees.print(avlTree);
System.out.println();
avlTree.add(new Person(7,7,""));
avlTree.add(new Person(10,7,""));
avlTree.add(new Person(11,7,""));
BinaryTrees.print(avlTree);
System.out.println();
avlTree.remove(new Person(98,7,""));
BinaryTrees.print(avlTree);
System.out.println();
System.out.println("-------------print-------------");
}