（21）Go实现AVL树-算法解析

作者: 哥斯拉啊啊啊哦 | 来源:发表于2019-04-26 07:32 被阅读0次

了解avltree树之前先了解几个概念  //
1）什么是二分搜索树；
2）什么是平衡树；
3）什么自平衡二分搜索树；

1）二分搜索树以及缺陷  //

如上图，是一颗二分搜索树，从添加查找节点，时间复杂度均为O(h)，但在极端情况下，
如按顺序向一个空二分搜索树中添加0，1，2，3，4，二分搜索数会退化为单链，这时候时间
时间复杂度会变成O(n)，如下图，为了避免这种情况需要结合平衡树做改进， //

2）平衡树  //

3）如果一颗二分搜索树按照平衡树的形式分布，可以避免搜索树退化为单链，
时间复杂度将一直是O(logN)，由此有了自平衡二叉树。
平衡二叉树有以下特点：//
1. 左右两颗子树的高度差不超过1；
2. 左右两颗子树也是一颗平衡二叉树；
3. 能够在二叉树不满足平衡二叉树的条件下自动转化为平衡二叉树

AVL树是自平衡树的一种，也是最早的自平衡二分搜索树，在1962年首次提出  //

问1：什么时候维护平衡？
答1：只有在插入或者删除节点中，才有可能导致节点不平衡，在这两个过程中维护平衡

问2：如何维护平衡？
答2：AVL树通过左旋转，右旋转的方式来维护平衡，具体分以下4种情况：
1. 插入或删除的节点在不平衡节点左侧的左侧 LL   -->  右旋转；
2. 插入或删除的节点在不平衡节点左侧的右侧 LR   -->  左节点先左旋转，之后不平衡节点右旋转；
3. 插入或删除的节点在不平衡节点右侧的右侧 RR   -->  左旋转；
4. 插入或删除的节点在不平衡节点右侧的左侧 RL   -->  右节点先右旋转，之后不平衡节点左旋转；

如下面，图演示过程：