Splay Trees 学习笔记

Splays Trees 也是一种二叉搜索树，用于提高连续搜索的效率。Splay Trees 通过将被访问到的节点放于根，提升访问速度。
它与AVL Trees 的效果有所区别。AVL树通过使树balanced降低树的高度至logN，从而使得单次搜索的复杂度为O(logN)。而Splay Trees则通过每次将被访问到的节点置于根，使得m次连续搜索的复杂度为O(mlogN)。
下面我们将介绍Splay Trees的实现及PTA中的相关题目。m次连续搜索复杂度为O(mlogN)我们在摊还分析博文中进行证明。

---

实现

根据不同的情况，Splay Trees采取不同的调整方法，直到被访问的节点置于根节点。
我们记被访问的节点为X，其父节点为P，其祖父节点为G。
首先我们将情况分为P是根节点和不是根节点。

P是根节点

交换P与X。结束调整。

P不是根节点

在该情况下，分为zig-zig情况和zig-zag情况。根据不同情况采取不同的旋转方法，旋转结束后，继续调整，直到被访问的节点处于根节点。

Zig-Zig

X, P, G处于同一方向时，只需旋转一次，将X, P, G颠倒即可。

Zig-Zag

X, P, G处于不同方向时，需要旋转两次，先旋转P, X，再旋转X, G

删除

在删除一个节点时，按如下步骤操作：

1. 找到并删除该节点
2. 访问该节点子树中最大的节点（此时该最大节点会处于该子树的根，且没有right child）
3. 使删除节点的右子树成为 左子树最大节点 的right child

---

题目

For the result of accessing the keys 3, 9, 1, 5 in order in the splay tree in the following figure, which one of the following statements is FALSE? (1分)

A. 5 is the root
B. 1 and 9 are siblings
C. 6 and 10 are siblings
D. 3 is the parent of 4

答案是D