平衡二叉搜索树

二叉搜索树与平衡二叉搜索树

二叉搜索树是一类特殊的带权（点权）二叉树，它的特点是，每个节点的权值总是大于其左子树中任何节点的权值，同时小于其右子树中任何节点的权值。在二叉搜索树中进行查找、插入、删除等操作的时间复杂度为$O(h)$，其中$h$为树高。我们说一棵二叉搜索树是退化的，如果它的所有节点都只有左孩子，或所有节点都只有右孩子。此时二叉搜索树退化为一条链表，查找、插入、删除等操作的时间复杂度为$O(n)$。

特别的，平衡二叉搜索树是指使用一定的构建算法和维护算法的二叉搜索树，其构建和维护算法保证整个二叉搜索树的高度始终为$O(\log n)$级别（也即“平衡”），从而保证查找、插入、删除等操作的时间复杂度为$O(\log n)$。需要注意，这里的时间复杂度可能为摊还时间复杂度。

伸展树（Splay）

顾名思义，伸展树的维护基于伸展（Splay）操作。所谓“伸展”，也即将某一节点逐层旋转到根节点，同时保持整棵树仍然具备二叉搜索树的性质。在树高为$O(\log n)$的情况下，伸展操作的时间复杂度为$O(\log n)$，因此不会增大查找、插入和删除操作的时间复杂度。

极端情况下，比如按照升序查询所有元素，会导致伸展树退化为长链。

伸展树的实现

伸展树最核心的就是伸展操作。伸展的基础是旋转，而旋转的本质是将某一节点上移一层。这样，任何一个节点一定可以经过有限次旋转后成为根节点，从而达到了“伸展”的效果。

根据被旋转节点与其父节点的关系，旋转被分为左旋和右旋。如果被旋转节点是其父节点的左孩子，我们称这一步旋转操作为右旋；否则，我们称这一步旋转操作为左旋。

树堆（Treap）与笛卡尔树

AVL

左偏红黑树

替罪羊树