优化二叉搜索树的科普

本文目的在日后再看到这些名词时能有扫盲的作用，所以未做深入探讨。

二叉搜索树的查询时间复杂度为O(h)，但是h的大小和数据密切相关，随机构建二叉搜索树可以保证期望高度h为O(lgn)，但是我们并不总能随机地构造二叉搜索树。所以就有二叉搜索树的变体来保证基本操作具有好的最坏情况性能，如AVL树，红黑树，treap树，splay树等。它们在二叉搜索树的基础上增加了额外的约束，操作更加复杂，但是保证最坏情况的动态集合操作时间复杂度为O(lgn)。下面按照时间介绍之。

AVL树

AVL树是最早发明的自平衡二叉搜索树，查找、插入、删除在平均和最坏情况下都是O(lgn)，自平衡是通过插入和删除时一次或多次树旋转来完成的。节点的平衡因子是左子树减去右子树的高度，1、0、-1被认为是平衡的，-2或2被认为是不平衡的，需要重新平衡树。平衡因子储存在节点中，或是通过计算算出。

根据不平衡的情况，AVL分成左左、右右、左右、右左四种情况，分别需要1、1、2、2次旋转调整。图略。

由于AVL是高度平衡树，所以节点插入、删除后，重新平衡需要的旋转次数较多，但是因此带来的搜索效率更高。

红黑树

最常见的平衡二叉树，统计性能最好的二叉搜索树。红黑树是满足下列性质的二叉搜索树：

• 每个节点都是黑色或是红色
• 根节点是黑色
• 每个叶节点都是黑色
• 如果一个节点是红色，那么它的两个子节点都是黑色
• 对于每个节点，从它到其所有子孙叶节点的路径包含的黑色节点数目相同

由于没有AVL树对平衡的高度要求，红黑树在节点插入、删除时，只需最多3次旋转操作即可完成。虽然牺牲了查找效率，但是在经常改动的动态数据集合中，红黑树的性能要更好。可以说红黑树在复杂度和旋转次数上有比较好的折中，因此常用作数据结构的设计。

Treap树

Treap树得名于搜索树trea和堆reap，是有一个附加域满足堆特征的二叉搜索树，结构相当于随机插入数据的二叉搜索树，相较其他平衡二叉树，特点是实现简单，且能基本实现随机平衡。

在构成Treap树时，还需要满足堆特征，在插入、删除维护堆性质时，只需要两种旋转，相比Splay，编程复杂度要更小。性能在平衡二叉树和二叉搜索树之间。

Splay树

Splay树又叫伸展树，发明于1985年。它是一种自调整形式的二叉搜索树，利用了频繁查找的数据集有限，在二叉搜索树的每次搜索后，将搜索条目通过一系列旋转搬移到离树根更近的地方。它的优势在于不需要记录平衡树的冗余信息，且编程复杂度小很多。

Splay的操作为旋转，分单旋转、一字型、之字形几种。

这些树的编码都较为复杂，这里略去。