背景

BST(Binary Search Tree)：二叉搜索树，是一种常见的数据结构，但是在实际应用中，由于数据问题，二叉搜索树往往是不平衡的，这就会使得查找时间复杂度并非O(logn)这么理想，通常会使用平衡树

BBT(Balanced Binary Tree)：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

平衡树的实现有很多种，归根结底都是通过一些操作，在插入或者删除等操作执行后能够维护树的平衡性，从而保证查找时间复杂度尽可能接近于logn。AVL则是实现平衡树的相对较为简单的方法

AVL：在AVL中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树，n个结点的AVL树最大深度约1.44logn。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树

算法

AVL算法通过左旋与右旋维护二叉树的平衡，进行调整时均在发生不平衡的最近根节点上进行旋转调整，使得该节点为根的树满足左右子树高度差小于等于1，即重新平衡

右旋

右旋：以root节点为根的树进行右旋即：

newRoot = root -> leftChild;
root -> leftChild = newRoot -> rightChild;
newRoot -> rightChild = root;

——————————–>

左旋

左旋：以root为根节点的树进行左旋即：

newRoot = root -> rightChild;
root -> rightChild = newRoot -> leftChild;
newRoot -> leftChild = root;

——————————–>

插入

在插入过程中共有四种情况可能造成平衡树失去平衡，即：左子树高度和右子树高度差大于1

情况一：

插入的节点位于root -> leftChild -> leftChild，此时通过一次右旋，即可重新平衡

—————右旋—————>

情况二：

插入的节点位于root -> leftChild -> rightChild，此时通过以root -> leftChild 为根节点进行一次左旋，转换为情况一，再以root为根节点进行一次右旋，即可重新平衡

–左旋–>–右旋–>

情况三：

插入的节点位于root -> rightChild -> rightChild，此时通过一次左旋，即可重新平衡

—————左旋—————>

情况四：

插入的节点位于root -> rightChild -> leftChild，此时通过以root -> rightChild 为根节点进行一次右旋，转化为情况三，再以root为根节点进行一次左旋，即可重新平衡

–右旋–>–左旋–>

删除

1. 当删除的节点左子树与右子树均存在时，如果左子树高度大于右子树，将左子树最大的节点替换被删除的节点，再递归删除该最大的节点；否则，将右子树最小的节点替换为被删除的节点，再递归删除该最小的节点。
   删除节点后，需要判断当前子树是否失去平衡，如果失去平衡，则需要通过旋转调整
2. 当删除的节点左儿子与右儿子存在一个时，直接用孩子节点替换该被删除的节点，若均不存在，则直接删除

删除导致的不平衡同样有四种情况，对应插入的四种情况，可以看做是逆操作

1. 删除后左子树高度与右子树高度差为2
   1. 如果height(root -> leftChild -> leftChild) > height(root -> leftChild -> rightChild)，则对应插入中情况一
   2. 如果height(root -> leftChild -> rightChild) > height(root -> leftChild ->leftChild)， 则对应插入中情况二
2. 删除后右子树高度与左子树高度差为2
   1. 如果height(root -> rightChild -> leftChild) > height(root -> rightChild -> rightChild)，则对应插入中情况四
   2. 如果height(root -> rightChild -> rightChild) > height(root -> rightChild ->leftChild)， 则对应插入中情况三