AVL树

大数据时代必懂的算法----AVL树

对于AVL树，我很遗憾，我从没有使用过它，但是理解它是理解红黑树的桥梁。

AVL树的特点

AVL树是平衡二叉树。
平衡二叉树的定义：对于任何一个节点，其左右子树的高度之差的绝对值<=1。这保证了查找、插入和删除在平均和最坏情况下都是O(lg n)。增加和删除这个树。
其优点是减少树的平均搜索长度，搜索很快。但是为了得到这个优点，却带来了一个致命的缺点：完全平衡的要求使的插入删除操作需要通过不定次数的旋转来让树重新达到完全平衡。平衡要求太苛刻了，严重降低了AVL树的插入删除性能。使它无法适用于统计业务。

我对AVL树的看法

1. 由于上述原因，AVL树不适合用于统计。
2. 假如用于“一次加载，多次查询”的业务，就是静态查询，它的查找性能虽高，但是又达不到好的哈希的O(1)时间复杂度。
综合这两个特点，我认为它没多大用处。
唯一的用处是用于教学，先搞懂AVL树，然后再深刻延伸向红黑树，起到一个抛砖引玉的作用。
也许有点片面，如果有朋友在哪个领域用这个合适，请告知，期待共同进步。