因為我個人才疏學淺，所以偷了一篇落谷題解的整理，以下是原文:

我说呀
作为一个自认为对平衡树这套理论深有研究的人
对每种平衡树（正常的）做个评价吧

1.RedBlackTree 碾压性的速度优势和代码量，可以分裂合并，但是是log方的，可以可持久化，非常厉害的一个DS (没人写
(唐狗針補 : 拿來裝特好用，5個規則8個調整，13條誰愛學誰學，但速度是真的快

2.ScapegoatTree 代码量小，随机数据下非常快，然而还是不如RBT 不能分裂合并，可以部分可持久化 但是在卡链的数据或者构造数据下表现就一般了
(唐狗針補 : 這東東我沒學過，平衡的方式挺酷的

3.Treap（旋转式） 代码量小，速度较快 不能分裂合并，可以可持久化 挺好的东西

4.Treap（非旋转式） 代码量小，速度非常慢（这个其实看写法，正常人写的都很慢） 可以分裂合并可持久化，功能挺多的 但是速度实在慢 
(唐狗針補 : 這東東建議學，程式量比其他平衡樹小不少，功能比一般平衡樹多，缺點是常數大，運氣不好會被卡成鍊

5.Splay 代码量一般，速度非常慢 可以分裂合并，不能可持久化 一般人学的平衡树
(唐狗針補 : splay的用途通常不在這，主要用途在動態樹問題，LCT ETT之類的，用在這裡反而不好寫，速度還慢

6.AVLTree 代码量较大，速度一般 如果修改少查询多的话AVL会很有优势，因为AVL的查询非常快 可以分裂合并，可持久化，但是分裂合并不怎么好写 好像没什么人会？
(唐狗針補 : 如果對平衡樹有興趣的大推學這個，簡單而且非常經典，只是實作量偏大

7.SizeBalancedTree 所谓的“自己发明的平衡树” 反正我感觉就是AVL然后强行重量平衡。。。 论文中他说速度可以吊打红黑树？ 然而实际上是被RBT吊打出了一条街 好像还是有些人去学的

8.DigitalSearchTree（其实就是Trie和值域线段树） 效率较高，代码量较低 可以分裂合并，可持久化 但是空间较大，为了解决空间问题可以动态开点（多log）或者离线离散化
(唐狗針補 : 01Trie跟線段樹在其他地方有其他用途，可以學，出現在這邊常數挺小

9.RRFGT 效率较高，代码量最小 可以分裂合并，可持久化 通用化的数据结构 嘿嘿嘿
(唐狗針補 : 這也是紅黑樹的一種，中文名:左傾紅黑樹，我也不會

10.B树系列 这个我也不会
(唐狗針補 : 我有去複製B樹的程式來貼，結果超過字數限制、、、

11.值域分块 效率一般，毕竟有根号 也不是很好写
(唐狗針補 : 我翻提解的時候是沒翻到，值域分塊、、、他也不是該出現在這裡的東西

12.排序向量树（其实就是个vector） 非常好写，复杂度O( nm )。。。 但是因为常数问题所以可以过题 而且查kth是O( 1 ) 的

其他的高论东西希望大家补充
(唐狗針補 : 他沒講到且我有看過的:Leafty Tree,pb_ds,跳表,Finger Tree

毕竟我很菜，即将退役，基本上也不会什么东西
(唐狗針補 : 我也很菜

補一個給Python用的第三方library: sortedcontainers.SortedList
如果需要手刻，可以參考PyRival的
https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/SortedList.py