Below is an explanation in multiple parts:
1. **Code for `findMax`**
2. **Why splay “rotates around the parent”**
3. **Why the rotation sequence is different for Zig-Zag vs. Zig-Zig**
---
## 1. Code for `findMax`
A typical `findMax(Node subtreeRoot)` (or `getMaxNode`) method in a BST is straightforward:
```java
/**
* Returns the node with the maximum value in the subtree rooted at 'node'.
*/
private Node findMax(Node node) {
if (node == null) return null;
while (node.right != null) {
node = node.right; // keep going right until there's no more right child
}
return node; // node is now the rightmost leaf
}
```
This is the same helper many BST-based structures use, including some splay implementations.
---
## 2. Why Splay “Rotates Around the Parent”?
In **splay trees**, the goal is to **move a target node `x` to the root**. However, **tree rotations** are defined around the **parent** node. For example, if we say “rotate left around `p`,” that means `p.right` becomes the new parent, etc.
When we do any rotation (left or right), we are effectively “pivoting” the **parent** and “pulling up” one of its children. Because `x` can’t rotate itself on top (the concept of rotation is always between a node and its parent), each step in the splay process **rotates `x` up** by rotating around `x`’s parent (and sometimes the grandparent).
So you’ll see lines like:
```java
if (x == p.left) {
rotateRight(p); // moves x up, p down
} else {
rotateLeft(p);
}
```
Because to move `x` up *above* `p`, we literally do a rotation that reassigns their positions in the tree.
---
## 3. Zig-Zag vs. Zig-Zig (The Rotation Order)
### Recap of Splay Steps
- **Zig**: The node `x` is a child of the **root**. We do **one** rotation (left or right) to bring `x` up.
- **Zig-Zig**: The node `x` and its parent `p` are either both *left children* or both *right children* of their respective parents (`p` and `g`). We do **two** rotations in a row: first rotate around `g`, then around `p` (or vice versa, depending on your code style).
- **Zig-Zag**: The node `x` is a *right child* and its parent `p` is a *left child* (or the opposite: `x` is left child, `p` is right child). We do **two** rotations again, but we rotate around `p` first, then around `g`.
#### Why the Order Differs
1. **Zig-Zig** (Same Side, e.g., `x == p.left` and `p == g.left`)
- We effectively do **two** rotations *in the same direction*.
- One common approach is:
- **Rotate Right** on `g` first (pull up `p`)
- Then **Rotate Right** on `p` (pull up `x`)
- The idea is that both `p` and `x` want to go up the “left side,” so rotating around `g` first helps “flatten” that chain, and then rotating around the new parent (`p`) finishes putting `x` above `p`.
2. **Zig-Zag** (Different Sides, e.g., `x == p.right` and `p == g.left`)
- We do **two** rotations, but **one** is left and the **other** is right.
- The typical sequence is:
1. **Rotate Left** on `p` (if `x` is a right child),
2. **Rotate Right** on `g`.
- This effectively ‘kicks’ `x` up in a diagonal path. We handle the “inner rotation” first (parent-level), then the “outer rotation” (grandparent-level).
- If we reversed the order in a Zig-Zag without rewriting the pointer assignment logic, you might not get the correct final shape or you risk messing up child pointers.
**Bottom line**: The difference in rotation order for Zig-Zig vs. Zig-Zag is a carefully designed sequence so that after two rotations, `x` ends up *two levels up* in the correct spot, preserving BST properties the whole way.
---
### A Small Diagram Example
Let’s do a quick illustration for **Zig-Zag** with `x = p.right` and `p = g.left`:
```
g
/ \
p ...
\
x
```
- `x` is the **right** child of `p`, and `p` is the **left** child of `g`.
- For Zig-Zag, we do:
1. **Rotate Left** around `p` (this pulls `x` up, puts `p` as `x.left`).
2. **Rotate Right** around `g` (this pulls `x` up again, above `g`).
If both were **left** (Zig-Zig, e.g., `x == p.left && p == g.left`), we do:
1. **Rotate Right** around `g`,
2. **Rotate Right** around `p`.
Or the other approach some code uses is:
1. **Rotate Right** around `p`,
2. **Rotate Right** around `g`.
Both sequences are valid if you systematically track pointer assignments. The key is that you do two same-direction rotations in Zig-Zig, while you do two *different* rotations in Zig-Zag (left then right, or right then left).
---
## Conclusion
1. **`findMax`** is a simple function: keep going right to find the largest value.
2. **Splay rotates around the parent** because that’s how BST rotations are defined—`x` moves up by pivoting around `p` (and sometimes also involving `g`).
3. **Zig-Zag** vs. **Zig-Zig** have different rotation orders because in Zig-Zig, `x` and `p` are on the *same side*, so we do *two rotations in the same direction*, typically rotating around `g` first. In Zig-Zag, `x` is on the *opposite side* of `p`, so we do two *different* rotations, handling the parent-level rotation first, then the grandparent-level.
Great question! Let's break this down step by step to address why rotations in splay trees (or any binary search tree) are always defined around the **parent** (or sometimes the grandparent in the case of splay trees) and why rotations aren't typically performed directly on the target node `x`.
### Why Rotate Around the Parent?
Rotations in binary search trees are defined to maintain the **binary search tree property** while restructuring the tree. The binary search tree property ensures that for any node `n`:
- All nodes in `n`'s left subtree have keys less than `n.key`.
- All nodes in `n`'s right subtree have keys greater than `n.key`.
To maintain this invariant, rotations are carefully structured around the **parent** of a node. Let's consider an example:
#### Rotate Left Around `p`:
- If `p` is the parent of `x` and we perform a left rotation around `p`, then:
- `p.right` (which is `x`) becomes the new parent of `p`.
- `p` becomes the left child of `x`.
- Subtrees are adjusted to maintain the binary search tree property.
This operation is safe because it only involves the **parent-child relationship** and the subtrees directly involved. It doesn't disrupt the rest of the tree structure or the binary search tree property.
#### Why Not Rotate `x` Directly?
If rotations were defined directly around `x` instead of its parent, it would be unclear how to preserve the tree structure and maintain the binary search tree property. The rotation itself is fundamentally about **restructuring the relationship between `x`, its parent, and its grandparent (if it exists)**, as well as their subtrees. Without the parent as the anchor point, the operation becomes ambiguous.
### What About Splay Trees?
In splay trees, the goal is to move the target node `x` to the root through a sequence of rotations. These rotations are carefully defined to involve `x`, its parent, and sometimes its grandparent. This is why we have:
1. **Zig Rotation**: When `x` is the child of the root, a single rotation is performed around `x`'s parent.
2. **Zig-Zig Rotation**: When `x` and its parent are both on the same side of the grandparent, two rotations are performed (first around the grandparent, then around the parent).
3. **Zig-Zag Rotation**: When `x` and its parent are on opposite sides of the grandparent, two rotations are performed in a "zig-zag" pattern (first around the parent, then around the grandparent).
In all these cases, the rotation is still defined with respect to `x`'s **parent or grandparent**, not `x` itself. This is because:
- Rotating directly around `x` doesn't make sense in terms of the parent-child relationships that define the tree structure.
- Rotations are inherently about **rebalancing the relationships between ancestors and descendants**. Without involving the parent (and grandparent, if needed), it would be impossible to properly adjust these relationships.
### Can We Imagine Rotating `x` Directly?
If you were to design a rotation that operated directly on `x`, you'd have to redefine how the parent and grandparent nodes are adjusted, effectively reinventing the concept of rotations. This would lead to more complex operations and wouldn't align with established tree rotation algorithms, which are simple and efficient because they operate around the parent.
### Summary
Rotations are always defined around the parent (or grandparent) because:
1. They preserve the binary search tree property.
2. They maintain the relationship between `x`, its parent, and its grandparent (if any).
3. Rotating directly around `x` is ambiguous and disrupts the clean, well-defined operation of standard rotations.
By rotating around the parent, we keep the operation simple, efficient, and consistent with the structure of binary search trees and splay trees.