Skip to content

Splay Trees

Target

Any M consecutive tree operations starting from an empty tree take at most \(O(M \log N)\) time.

So AVL tree is a kind of splay tree.

It just means that the amortized(摊还) time is \(O(\log N)\).

Note: access: 访问、接触

Idea

After a node is accessed, it is pushed to the root by a series of AVL tree rotations.

Insertion

For any nonroot node X, denote its parent by P and grandparent by G:

P is the root

Rotate X and P

image-20240917124518379

P is not the root

Zig-zag

Double rotation

image-20240917124909569

Zig-zig

Single rotation

image-20240917125048610

Splaying roughly halves the depth of most nodes on the path.

Deletion

  1. Find X

X will be at the root.

  1. Remove X

There will be two subtrees \(T_L\) and \(T_R\).

  1. FindMax(\(T_L\))

  2. Make \(T_R\) the right child of the root of \(T_L\)

Problem

1

image-20240917130350862

D

image-20240917131818162

查询完后结果如上图所示

2

image-20240917132053097

A

查询完后，这个最大的节点就会被当作是根。根据二叉搜索树的定义可知，这个树没有右子树