平衡二叉树学习

平衡二叉树

平衡二叉树的特点是,小的值在左边,大的值在右边。

VisuAlgo画一个简单的平衡二叉树:

再随机生成一个:

可以发现规律:整棵树中,所有节点的值从左至右逐渐增大。

什么是高度平衡(AVL)二叉树?

WiKi解释如下:

在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

高度平衡树经常涉及到旋转这个概念,简单来说就是高度平衡树插入或删除某个节点可能破坏平衡,这时就需要旋转一些(3个)节点来恢复树的平衡。
旋转哪三个呢?实际上只有四种情况,根据不同情况选择不同的旋转方法。很多人讲得很详细,不搬运了,可以参考这里:高度平衡的二叉搜索树(AVL树)-逝者如斯,不舍昼夜

AVL树的四种旋转

由于整棵树中,从左至右逐渐增大,旋转可理解为左右顺序不变,垂直映射到