说明:本博客的所有图片来源于慕课网
平衡二叉树(AVL树)也是面试中的一个点,好的回答可以让面试官的印象更深刻
定义 AVL树:对于任何一个节点[任何一个节点,不只是叶子节点],左子树和右子树的高度差不为1
平衡因子: 对于左右子树的高度差[左子树的高度减去右子树的高度]
说明:
AVL是改变二分搜索树极端的情况下为链表的情况,[每个节点只有左孩子],所以AVL引入了平衡因子[但是它仍然是二分搜索树]
AVL维护自平衡的时间:新插入的节点有可能使得整个树不满足平衡性,因此在新加入节点之后沿着这个节点一路找父节点和祖先节点
AVL维护自平衡的机制:左旋转和右旋转
平衡性打破的几种情况:(LL,RR,LR,RL)
1.插入的元素在不平衡节点的左侧的左侧LL
新插入的节点是2,不平衡节点在8,新插入的节点在不平衡节点的左侧的左侧
将这种情况可以抽象成下面这种:
针对这种情况的解决方法是右旋转 分为两步: x.right=y; y.left=T3
2.插入的元素在不平衡节点的右侧的右侧RR
解决办法左旋转:
3.插入的元素在不平衡节点的左侧的右侧LR
首先对x进行左旋转,让这棵树变成LL的情况
然后再使用LL转换为AVL树的办法,将其右旋转
4.插入的元素在不平衡节点的右侧的左侧RL
先将这个树转换为RR树
然后使用RR树的解决办法,将其平衡化(左旋转)
平衡二叉树的删除操作与二分搜索树的删除操作类似,不同的是需要维护平衡操作,执行上面的操作
关于二分搜索树的删除操作:https://blog.csdn.net/if_i_were_a/article/details/89261068