看完《數據結構與算法分析》，各種二叉查找樹簡直看得要崩潰，這里整理一下，也便于以后自己使用。
| 查找（平均/最壞） | 插入（平均/最壞） | 刪除（平均/最壞） | 優點 | 缺點 | |
| 二叉查找樹BST | O(logN)/O(N) | O(logN)/O(N) | O(logN)/O(N) | 編程代碼最簡單 | 樹可能會不平衡，最壞情況會達到O(N) |
| AVL樹 | O(logN)/O(logN) | O(logN)/O(logN) | O(logN)/O(logN) | 增加了平衡條件，保證了最壞情況依然是O(logN) | 編程復雜，數據結構相對復雜 |
| 伸展樹SplayTree | O(logN)/O(N) | O(logN)/O(N) | O(logN)/O(N) | 數據結構相對簡單，雖然有最壞情況，但并不影響總體速度 | 仍然存在O(N)的情況 |
| 伸展樹（自頂向下） | O(logN)/O(N) | O(logN)/O(N) | O(logN)/O(N) | 相比自底向上，非遞歸實現，且只需要O(1)的額外空間但攤還時間不變 | 代碼復雜 |
| 紅黑樹RedBlackTree | O(logN)/O(logN) | O(logN)/O(logN) | O(logN)/O(logN) | AVL的變種，繼承了AVL的時間，平衡的好 | 有大量的旋轉，刪除復雜，總體代碼也復雜 |
| AA-樹 | O(logN)/O(logN) | O(logN)/O(logN) | O(logN)/O(logN) | 代碼實現會大量簡化，且時間繼續保持 | 旋轉的次數會相對多 |
| treap樹 | O(logN)/O(N) | O(logN)/O(N) | O(logN)/O(N) | 這是最簡單的一種樹了，效率甚至高于伸展樹 | 依然是存在最壞情況的 |
AVL樹：主要使用遞歸實現，非遞歸有點麻煩，通過記錄每個節點的高度，當高度差達到2時，進行旋轉，達到自平衡。實現可以參考：http://blog.csdn.net/d521000121/article/details/54312142
伸展樹SplayTree：思想是每次要找的都通過旋轉放到根上（叫做展開），方便后續的查找，所以當某些數據連續被查找又或者要查找的數據非常接近，此時速度便會非常快。
而且最壞情況不會保持。附上一個大神的博客：
http://www.cnblogs.com/vamei/archive/2013/03/24/2976545.html
伸展樹（自頂向下）：從底向上需要遞歸，同時就是要額外空間，但自頂向下只需要常數空間即可，且可用非遞歸實現，所以個人認為這個算法會更快？
注意這里生成的樹與自底向上的會有區別。實現的話書上已經非常詳細了。
紅黑樹RedBlackTree：AVL的變種，通過標記節點是紅色還是黑色，再給樹一系列的約束條件，達到自平衡的功能，從理論上也證明了生成的樹已經接近最優。
再附上大神博客：http://blog.csdn.net/chenhuajie123/article/details/11951777
AA-樹：先有二叉B-樹，再有BB-樹，再加上一點紅黑樹的條件，就是AA-樹（mdzz。。。）
講解這個比較好：http://blog.csdn.net/zhaojinjia/article/details/8121156，實現書上有
treap樹：很簡單的一個想法，就是查找二叉樹+堆，對于每個節點，會生成一個隨機數叫優先級，treap數除了滿足查找二叉樹的條件外，其節點的優先級要滿足堆序，
不滿足的通過左旋轉和右旋轉維護。詳細參考：http://blog.csdn.net/pi9nc/article/details/12244591
新聞熱點
疑難解答
