Splay Tree Rotations: Follow the Parent and Grandparent
2026-11-18

Splay Tree Rotations: Follow the Parent and Grandparent

Splay Tree Rotations move an accessed key toward the root while retaining binary-search ordering. The adjustment uses the relationship between a node, its parent and its grandparent. Following that three-node configuration explains why the operation is more specific than repeatedly moving a node upward in any convenient way. The examples below use invented numeric keys and empty omitted subtrees, rather than a measured workload.

Keep ordering separate from the tree's shape

In a binary search tree, a node's left subtree contains smaller keys and its right subtree contains larger keys. A rotation changes the local arrangement of links while preserving that ordering. The MIT splay-tree lecture describes the rotation cases used to bring an accessed node to the root. The choice depends on whether the relevant nodes are left or right children.

Take a tree rooted at forty, whose left child is twenty and whose left grandchild is ten. Searching for ten follows two left links. Its depth is two before adjustment, while the root has depth zero. These are positions in an invented tree, not latency measurements. A valid rearrangement must continue to place ten before twenty before forty in an inorder traversal.

An invented left chain40–20–10 becomes a right chain10–20–40.
Two right rotations at40 then20 move the accessed10 to the root; omitted subtrees are empty. Source: Zhilianhai editorial desk, original AI-assisted conceptual illustration.

Follow a same-direction zig-zig step

Call the accessed node x, its parent p and its grandparent g. In the forty, twenty, ten configuration, both links point left. First rotate the parent above the grandparent: twenty becomes the local root, with ten on its left and forty on its right. Then rotate the accessed node above its parent. Ten becomes the local root, twenty becomes its right child, and forty remains to the right of twenty.

The accessed ten has moved from depth two to depth zero through two rotations. The sequence ten, twenty, forty remains unchanged when the resulting tree is read inorder. The two rotations therefore change the route of future searches without changing which keys are stored or their sorted relationship. In a larger tree, the subtrees between these keys must be reattached to their appropriate intervals rather than discarded.

The Carnegie Mellon lecture explicitly distinguishes this zig-zig rule from simply rotating the accessed node with its parent repeatedly. The parent-first order is part of the splay procedure. Merely achieving the same final root on one small example does not make two general restructuring rules interchangeable.

Follow an opposite-direction zig-zag step

Now start again at a root of forty, but give its left child twenty a right child of thirty. The accessed thirty is a right child of a left child. First rotate thirty above twenty using a left rotation at twenty. The local arrangement becomes forty with a left child thirty, and thirty with a left child twenty. Next rotate thirty above forty using a right rotation at forty.

The final local root is thirty, with twenty on its left and forty on its right. This time the accessed node itself moves above its parent first. Both cases use two rotations, but their starting directions and their rotation order differ. The drawings intentionally retain only three keys so that those choices remain visible.

An invented40-left20-right30 tree becomes30 with children20 and40.
Left rotation at20 followed by right rotation at40 preserves inorder20,30,40. Source: Zhilianhai editorial desk, original AI-assisted conceptual illustration.

Use a final zig when only a root parent remains

If an accessed node has a parent but no grandparent, one rotation is enough to bring it to the root. For example, with twenty at the root and ten directly on its left, a right rotation brings ten above twenty. This is the final zig case. If the accessed node is already the root, there is no upward move to perform.

For a longer search path, a splay consists of repeated applicable steps, not necessarily just one pair of rotations. After each local adjustment, identify the node's new parent and grandparent before selecting the next case. Treating an old grandparent pointer as though it still described the tree would mix the before and after configurations.

Interpret the performance statement over a sequence

Sleator and Tarjan's original self-adjusting search-tree paper frames the analysis in amortized terms. A bound over a sequence of operations is different from requiring a short path for every individual search. A splay tree can contain a long path; it does not maintain an explicit height limit merely because it changes after access.

The examples show the structural change directly. After splaying ten, an immediate new search for ten begins at the root. That observation does not predict the cost of a future search for another key, because the arrangement can change again. A meaningful workload comparison needs an actual operation sequence and a stated cost measure.

To check an implementation, record the keys before and after each step, verify unchanged inorder output, and inspect the new parent links. Separately test left-left, right-right and both opposite-direction cases. Related algorithm explanations appear in the technical article collection and the industry information section.

18028484626 CONTACT US

公司:智联海(惠州)科技有限公司

地址:惠州仲恺高新区陈江街道白云山工业大道 5 号六楼 601

Q Q:18028484626

Copyright © 2002-2026

咨询 在线留言 电话:18028484626
微信 微信扫码添加我