目录
认识AVL树:
插入时的平衡调节:
右单旋:
左单旋:
左右双旋:
右左双旋:
想必大家都了解过二叉搜索树,O(logn)的时间复杂度查找数据,效率可以说很高了,但是在一些场景下,它的效率还是不够理想。当往二叉搜索树里插入的都是有序的值时,就会出现下面的情况:
这样的话二叉树退化成了单支树,时间复杂度就近似O(n),效率大减。
因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
简单来说。这种树可以自己调节平衡性,保证每颗树的左右子树高度不会相差太多,来看看它是如何实现的:
在每个节点,加入一个变量:平衡因子:
AVL树的每一颗子树都必须是AVL树 平衡因子的值==右子树的高度-左子树的高度 合法平衡因子的值只能是-1,0,1,一旦超过或者低于这些值就要调节平衡(旋转)。
为了方便理解,我把下面这棵树的平衡因子标注在旁边,可以自己分析一哈:
每次插入数据时,都有可能改变树的高度,那么该如何精确地做到调节平衡因子,从而改变树地高度呢?这里时通过旋转的方法,我们先列举一下到底什么情况需要旋转,也就是调节平衡,大致可分为4大类,下图时这4大类的树高度趋势图:
接下来一一分析这4种情况:
当树的高度趋向上图趋势时,来看看这种树的具象图:
方括号a,b,c都表示高度为h的子树,当我们在a或b下面插入新节点时,势必会引发不平衡,我们通过右单旋来调节,先看看过程:
右单旋:首先找到旋转点,也就是在插入节点后向上找,第一个平衡因子为-2的祖先,并且祖先的左孩子的平衡因子为-1,此时就需要进行右单旋,为方便叙述,我把刚才讲的祖先和左孩子节点设为,parent和subL。先将subL的右子树(图中的b)给parent的左子树,再将parent给subL的右子树,最后将subL和parent的平衡因子都变为0,完成右单旋。
为了方便找到父亲,每个节点都是都有自己父亲的指针,所以每次调节过程中都要调节自己节点中父亲指针的指向,可以自己看图捋捋,过程我放在代码里;
代码:
void RotateR(node* parent)
{
//调节节点
node* subL = parent->left;
node* subLR = subL->right;
node* ppnode = parent->parent;
parent->left = subLR;
if (subLR)//防止为空
{
subLR->parent = parent;
}
subL->right = parent;
parent->parent = subL;
//调节父节点的指向
if (parent == _root)
{
_root = subL;
subL->parent = nullptr;
}
else
{
if (parent == ppnode->left)//若这整颗树是别人的左子树
{
ppnode->left = subL;
}
else//若这整颗树是别人的右子树
{
ppnode->right = subL;
}
subL->parent = ppnode;
}
//平衡因子
parent->_bf = subL->_bf = 0;
}
讲完右单旋,其实左单旋也是同理,先看看触发左单旋的高度趋势图和具象图:
左单旋:首先找到旋转点,也就是在插入节点后向上找,第一个平衡因子为2的祖先,并且祖先的右孩子的平衡因子为1,此时就需要进行左单旋,为方便叙述,我把刚才讲的祖先和右孩子节点设为,parent和subR。先将subR的左子树(图中的b)给parent的右子树,再将parent给subR的左子树,最后将subR和parent的平衡因子都变为0,完成左单旋。
代码:
void RotateL(node* parent)
{
node* subR = parent->right;
node* subRL = subR->left;
node* ppnode = parent->parent;
parent->right = subRL;
if (subRL)
{
subRL->parent = parent;
}
parent->parent = subR;
subR->right = parent;
if (parent == _root)
{
_root = subR;
subR->parent = nullptr;
}
else
{
if (ppnode->left == parent)
{
ppnode->left = subR;
}
else
{
ppnode->right = subR;
}
subR->parent = ppnode;
}
subR->_bf = parent->_bf = 0;
}
当遇到图中情况,一次单旋已经解决不了问题了,所以需要双旋,如上图,先以30为旋转点进行一次左单旋 ,再以90为旋转点,进行一次右单旋。
在双旋中,如果理解了单旋,旋转已经不成问题了,难的是最后平衡因子的调节,在单旋完后,我们都将parent subL或者subR的平衡因子都改为了0,但在双旋中不一样,上图是在b后面插入,最后的平衡因子为parent为1,其它为0,如果在c后面插入呢?
可以发现,最后的平衡因子:subL为-1,其他为0。还有一种情况就是,60自己作为新节点插入,这里不再画图,直接说结果,最后的平衡因子都为0。
所以,在旋转前,我们先记录subLR(图中60)的平衡因子:
如果为1(在subLR的右边插入),最后调节平衡因子时就将subL的平衡因子设为-1,其它为0; 如果为-1(在subLR的左边插入),最后调节平衡因子时就将parent的平衡因子设为1,其它为0; 如果为0(subLR作为新节点插入),最后所有平衡因子设为0。
代码:
void RotateLR(node* parent)
{
node* subL = parent->left;
node* subLR = subR->right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
subLR->_bf = 0;
if (bf == 1)//在subLR右边插入
{
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == -1)//在subL左边插入
{
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)//subL作为新增
{
subL->_bf = 0;
parent->_bf = 0;
}
}
右左双旋和左右双旋同理:
先以90为旋转点进行一次右单旋 ,再以30为旋转点,进行一次左单旋。
同样最后的平衡因子调节也需要分情况,在旋转前,我们先记录subRL(图中60)的平衡因子:
如果为1(在subRL的右边插入),最后调节平衡因子时就将parent的平衡因子设为-1,其它为0; 如果为-1(在subRL的左边插入),最后调节平衡因子时就将subR的平衡因子设为1,其它为0; 如果为0(subRL作为新节点插入),最后所有平衡因子设为0。
代码:
void RotateRL(node* parent)
{
node* subR = parent->right;
node* subRL = subR->left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
subRL->_bf = 0;
if (bf == 1)//在subRL的右边插入
{
subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)//在subRL的左边插入
{
subR->_bf = 1;
parent->_bf = 0;
}
else if(bf == 0)//subRL作为新增
{
subR->_bf = 0;
parent->_bf = 0;
}
}