Splay Tree

是什么？

相信大家之前都用过 BST (Binary Search Tree , 二叉排序树）

复习一下 BST 的概念：

BST 或是一棵空树；或者是具有下列性质的二叉树：

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 左、右子树也分别为二叉排序树；

理想情况下 BST 的时间复杂度为 $O(log_2N)$ ，但是如果 BST 建得不好，其有可能退化成一条链，这样时间复杂度就成 $O(N)$ ，实在是前功尽弃。

BBST （Self-balancing binary search tree , 平衡树）就应运而生了。

常见的 BBST 有：Treap, Splay, AVL, RBT, SBT$\dots$

今天我们讲的是其中的 Splay.

为什么？

选择 Splay 的原因主要是它编程难度低（相对而言，依然有250+行）、功能十分强大，几乎能实现 BBST 的所有功能。可谓“麻雀虽小五脏俱全”，是一个性价比很高的数据结构。

怎么做？

基本概念

理解概念十分重要（注重概念理解不意味着重蹈 kigo 的覆辙），下面来简述一下基本概念：

1. ZIG （左旋） , ZAG( 右旋）
   

2. Splay （伸展）