详解平衡二叉树(AVL)

说明:本博客的所有图片来源于慕课网

平衡二叉树(AVL树)也是面试中的一个点,好的回答可以让面试官的印象更深刻

定义     AVL树:对于任何一个节点[任何一个节点,不只是叶子节点],左子树和右子树的高度差不为1

平衡因子:   对于左右子树的高度差[左子树的高度减去右子树的高度]

说明:

AVL是改变二分搜索树极端的情况下为链表的情况,[每个节点只有左孩子],所以AVL引入了平衡因子[但是它仍然是二分搜索树]

AVL维护自平衡的时间:新插入的节点有可能使得整个树不满足平衡性,因此在新加入节点之后沿着这个节点一路找父节点和祖先节点

AVL维护自平衡的机制:左旋转和右旋转

平衡性打破的几种情况:(LL,RR,LR,RL)

1.插入的元素在不平衡节点的左侧的左侧LL

详解平衡二叉树(AVL)

新插入的节点是2,不平衡节点在8,新插入的节点在不平衡节点的左侧的左侧

将这种情况可以抽象成下面这种:

详解平衡二叉树(AVL)

详解平衡二叉树(AVL)针对这种情况的解决方法是右旋转   分为两步: x.right=y; y.left=T3

详解平衡二叉树(AVL)

2.插入的元素在不平衡节点的右侧的右侧RR

详解平衡二叉树(AVL)

解决办法左旋转:
详解平衡二叉树(AVL)

3.插入的元素在不平衡节点的左侧的右侧LR

详解平衡二叉树(AVL)

首先对x进行左旋转,让这棵树变成LL的情况

详解平衡二叉树(AVL)

然后再使用LL转换为AVL树的办法,将其右旋转

4.插入的元素在不平衡节点的右侧的左侧RL

详解平衡二叉树(AVL)

先将这个树转换为RR树

详解平衡二叉树(AVL)

然后使用RR树的解决办法,将其平衡化(左旋转)

平衡二叉树的删除操作与二分搜索树的删除操作类似,不同的是需要维护平衡操作,执行上面的操作

关于二分搜索树的删除操作:https://blog.csdn.net/if_i_were_a/article/details/89261068

上一篇:AVL树(自平衡二叉查找树)


下一篇:数据结构【查找】—平衡二叉树AVL