20250224 ‐ splay tree - cywongg/2025 GitHub Wiki

Let’s clarify the difference in the removal logic for a Splay Tree based on the description you shared. Normally (in many standard splay tree implementations), the removal procedure is something like:

1. Find the node (which splays it to the root if found).
2. Remove the root.
3. Reconnect left and right subtrees (e.g., by splaying the max of the left subtree and attaching the right subtree).

However, the description you’ve given uses regular BST deletion first (e.g., swapping with predecessor/successor, etc.) and then it specifically says:

“The node to be splayed is the original node’s parent… If the element is not present, we splay the last element accessed.”

This is a different approach than the conventional “splay the node to remove itself first.” So, yes, you would change the code I shared earlier if you need to follow that definition.

---

Usual (“Conventional”) vs. Your (“Different”) Removal Approach

1. Conventional:

   • Splay the target node to root.
   • Remove root.
   • Reattach children.

2. Your described approach:

   • Do a BST-style delete:
     • If node has 0 or 1 child → remove directly.
     • If node has 2 children → swap with predecessor/successor, then remove.
   • After actually removing that node, splay the (former) parent of the deleted node (or splay the last accessed node if the item wasn’t found).

In other words, you don’t splay the node itself to root before deletion. Instead, you delete it the “old-fashioned” BST way, then you splay its parent.

---

Outline: How to Modify the Code

Let’s see how you might modify the previous code snippet to follow this new logic. The core difference is inside the remove method. Here’s a sample approach:

1. Locate the node (but do not splay it automatically). You can do a standard “search” for it—like a regular BST search that does not do any splaying.
2. If the node is not found:
   • Splay the last accessed node (like a normal splay-tree “not found” scenario).
3. If the node is found:
   • Remember the node’s parent (call it p) or the last accessed node.
   • Perform the standard BST removal procedure (swap with predecessor or successor if 2 children, or remove directly if 0 or 1 child).
   • If p still exists (i.e., the removed node wasn’t root or something), splay p.

Below is a simplified snippet just focusing on how you might do it. For brevity, I’ll pseudo-code some parts:

// We won't call `findNode(val)` which does an automatic splay in its search.
// Instead, we do a separate "searchNoSplay" that only returns the node or null.
// If not found, we splay the last accessed node.

public void remove(E val) {
    if (val == null) return;

    // We'll do a "BST-like" search that doesn't splay automatically
    SearchResult sr = searchNoSplay(val);
    Node target = sr.foundNode;      // the node with 'val' if found
    Node lastAccessed = sr.lastNode; // the last node visited

    if (target == null) {
        // not found, so per the spec: splay the last accessed node
        if (lastAccessed != null) {
            splay(lastAccessed);
        }
        return;
    }

    // If found, store its parent for splaying after we physically delete
    Node p = target.parent;

    // Standard BST removal logic:
    // 1) If target has 0 or 1 child, remove directly.
    // 2) If target has 2 children, swap with predecessor (or successor),
    //    then treat it as 0 or 1 child case.

    if (target.left == null || target.right == null) {
        // easy 0 or 1 child remove
        removeNodeDirect(target);
    } else {
        // swap with predecessor
        Node pred = findMax(target.left);
        // swap the values (not pointers!!) so target is now pred, effectively
        E temp = target.value;
        target.value = pred.value;
        pred.value = temp;
        // Now pred has at most 1 child
        removeNodeDirect(pred);
        // p might change if pred had a different parent
        // but let's keep it simple and let p remain as is
    }

    // Finally, if p != null, we splay p
    if (p != null) {
        splay(p);
    }
}

The searchNoSplay Helper

We need a search that returns both:

1. The node if found.
2. The last node visited if not found (or if found).

Something like:

private class SearchResult {
    Node foundNode;
    Node lastNode;
}

private SearchResult searchNoSplay(E val) {
    SearchResult sr = new SearchResult();
    sr.foundNode = null;
    sr.lastNode = null;

    Node current = root;
    Node parent = null;

    while (current != null) {
        parent = current;
        int cmp = val.compareTo(current.value);
        if (cmp == 0) {
            sr.foundNode = current; // found it
            sr.lastNode = current;
            return sr;
        } else if (cmp < 0) {
            current = current.left;
        } else {
            current = current.right;
        }
    }

    // if we get here, we never found it
    sr.foundNode = null;
    sr.lastNode = parent; // the last node we visited
    return sr;
}

The removeNodeDirect Helper

This removes a node with at most one child in normal BST fashion, adjusting parents:

private void removeNodeDirect(Node node) {
    Node child = (node.left != null) ? node.left : node.right;
    // Link child's parent to node's parent
    if (child != null) {
        child.parent = node.parent;
    }
    // If node is root
    if (node.parent == null) {
        root = child;
    } else if (node == node.parent.left) {
        node.parent.left = child;
    } else {
        node.parent.right = child;
    }
    // 'node' is effectively removed now
}

Summarizing the Differences

• In most splay tree textbooks: we do “splay the node we want to remove” to the root, then remove root.
• Your described approach: do “normal BST removal” (including predecessor/successor swap if 2 children) and then splay the parent of the removed node.

Both are valid ways of implementing a splay tree. They each have slightly different performance characteristics but still maintain the amortized efficiency splay trees are known for.

---

TL;DR

1. Yes, using that definition changes the code from the conventional approach.
2. Instead of splaying the node being removed first, you do a standard BST delete, then splay the parent afterward.
3. If the node isn’t found, you splay the last node visited just like normal splay trees do.

So to answer your question directly: Yes—if you need the removal method to behave exactly as described (swap with predecessor and then splay the parent of the original node), you do have to modify the removal logic from the conventional “splay the node to root, then remove.”