前言：#
严格来说，01Trie 并不是传统意义上的平衡树；这里只是把它作为“可以解决普通平衡树题目的一类有序结构”一起放进来比较。
这篇总览不是教科书式定义罗列，而是一次面向实现的复盘。我把自己手写过的几类结构——B 树、AVL、红黑树、Splay、Treap 和 Trie 方案——放到同一张桌子上，从实现难度、扩展性、基础操作效率三个维度做一轮对比，方便后面回看时快速定位：哪一类结构适合练手，哪一类结构适合比赛模板，哪一类结构更适合继续扩展功能。
下面的评价都带有明显的实践经验色彩，不追求绝对客观，但会尽量把判断依据说清楚。
实现难度： B > RB > AVL > Splay > 带旋Treap≈无旋fhq-Treap。
B树我觉得是最难的，没有之一，可能是因为B树是多叉树导致的，而且清晰的教程比较少，我在写的时候也没找到数据结构可视化的网站([Data Structure Visualization (USFCA)](https://www.cs.usfca.edu/~galles/visualization/Algorithms.html) ) 实现的时候真的痛苦至极，删除策略真的很要人命。之后的红黑树，其实在有AVL树基础的时候容易理解了很多，只是红黑树的几个性质不是非常好理解。AVL树比较难主要是因为这是我第一个接触的旋转平衡树，所以耗的时间比较长。后面三个真的很简单，基本上没难度，代码也非常短。
拓展性：带旋Treap≈无旋fhq-Treap≈Splay > AVL≈RB > B
这是平衡条件所决定的，平衡条件越苛刻，效率越高，拓展性越差。
基本功能效率：RB≈AVL > 带旋Treap > 无旋Treap≈Splay > B
RB和AVL平衡条件苛刻，基本效率比较高；Treap因为随机的原因趋于平衡；Splay效率说实话比较随缘；B树如果找不到一个合适的阶数效率不高。
所以考虑基本功能效率的话就是RB和AVL，这两者再考虑实现难度的话，首推AVL树；考虑有比较好的效率的同时有很好的拓展性，就是Splay，无旋fhq-Treap，带旋Treap，再考虑实现难度，还是推荐无旋fhq-Treap。
关于旋转，我觉得对于Treap，Splay，RB，AVL来说，旋转有着各自不同的含义，很有趣，在不同方面都有应用吧（大概，纯主观。）
AVL树是平衡树的始祖，旋转主要是最基本的降低左右子树高度差的同时保持二叉排序树的性质，搜索的效率最高。 如果是自用的话，搓一个AVL树的模板，效率一点不比stl红黑树map差。
RB在AVL基础上看到了旋转的父亲兄弟节点位置的变化，借由染色操作，模拟4阶B树，实现了搜索，插入，删除的综合，应用范围最广，stl中map和set就是红黑树，所以只需要重载小于符就能用。
Splay侧重于旋转对于一个孩子节点来说可以实现位置的抬高，一步一步实现节点到达根。（或许在缓存方面会有应用？）
Treap侧重于旋转对于一个父亲节点来说可以实现位置的降低，这让它实现了fix值的堆性质。又因为随机数的原因，让它不容易被卡，所以竞赛常见。
想法：如果目标是把“平衡树”真正写明白，最有效的方式仍然是自己把其中几种结构完整敲一遍，再回头看它们之间的数据维护差异。
B-树：#
AVL树：#
RB树：#
带旋Treap：#
无旋fhq-Treap#
Splay树：#
01Trie树：#
包括从高位开始和从低位开始两种思路。