AVL树

搜索,插入和删除都是$O(\log n)$.

从空树开始插入的摊还时间复杂度是$O(\lg n)$,删除是$O(1)$.

Splay树

每个操作的摊还代价是$O(\log n)$