AVL平衡二叉树详解与实现
AVL平衡二叉树详解与实现
什么是平衡二叉树？
Adelson-Velsikii和Landis提出了一种结点在高度上相对平衡的二叉查找树，又称为AVL树。其平均和最坏情况下的查找时间都是O(logn)。同时，插入和删除的时间复杂性也会保持O(logn)，且在插入和删除之后，在高度上仍然保持平衡。AVL树又称为平衡二叉树，即Balanced Binary Tree或者Height-Balanced Tree，它或者是一棵空二叉树，或者是具有如下性质的二叉查找树：其左子树和右子树都是高度平衡的二叉树，且左子树和右子树的高度之差的绝对值不超过1。如果将二叉树上结点的平衡因子BF（Balanced Factor）定义为该结点的左子树与右子树的高度之差，根据AVL树的定义，AVL树中的任意结点的平衡因子只可能是-1（右子树高于左子树）、0或者1（左子树高于右子树），在某些图中也会表示为绝对高度差，即0，1，2这种形式，请注意理解。
Rebalance:平衡调整
在平衡二叉树 插入或删除节点会导致不平衡，需要进行旋转操作使得树中每个节点都处于平衡状态
LL型：右旋转
当新插入节点为最近的非平衡子树的根节点的左孩子的左子树时，进行右旋转使其重新恢复平衡：
新插入的 节点A 导致 节点C 不平衡，且 结点A 位于结点C 的左孩子的左子树，因此 以 节点C 为轴进行右旋转
一个复杂的例子：
RR型：左旋转
当新插入节点为最近的非平衡子树的根节点的右孩子的右子树时，进行右旋转使其重新恢复平衡：
新插入的 节点C 导致 节点A 不平衡，且 结点C 位于结点A 的右孩子的右子树，因此 以 节点A 为轴进行右旋转
一个复杂的例子：
LR型：先右旋转再左旋转
当新插入节点为最近的非平衡子树的根节点的左孩子的右子树时，先进行左旋转再进行右旋转，使其重新恢复平衡：
新插入的 节点B 导致 节点A 不平衡，且 结点B 位于结点A 的左孩子的右子树：
①：以结点A为周进行右旋转
此时变成了LL型，再以结点C为轴进行右旋转
一个复杂的例子：
RL型：先右旋转再左旋转
作者：TNT
链接：https://juejin.cn/post/7018800865146306568