<p>To complete the search process for an element $x$ that is not in the tree, you have to go all the way to a leaf node to confirm that $x$ is not in the tree.  If you repeatedly search for such an element $x$, you have to splay on an unsuccessful search, otherwise the query time for $x$ could indefinitely remain as bad as $\Theta(n)$, even in an amortized sense.</p>

CC BY-SA 2.5
2011-01-17T16:58:46.410Z
Aah, i hadn't thought of that. Makes perfectly sense, thanks!
Aerus
CC BY-SA 2.5
2011-01-17T16:11:30.070Z
2011-01-17T16:11:30.070Z
James King
<p>If you search for a node in a semi-splay tree, it's basically to push certain nodes closer to the root, to reduce future search operations.</p>

<p>My course also says that if you search for a node and the node is not in the semi-splay tree, you <em>still</em> have to perform semi-play on the search path in the tree.<br>
But isn't that basically pushing nodes to the root that aren't actually have been searched for?</p>

<p>So my question would be : why do you still have to perform semi-splay even if the node you search for is not in the tree?</p>

<ds.data-structures><tree><dynamic-algorithms>
Searching nodes in semi-splay tree
Aerus
# Searching nodes in semi-splay tree

(Asked by: username_0 on 2011-01-17)

If you search for a node in a semi-splay tree, it's basically to push certain nodes closer to the root, to reduce future search operations.

My course also says that if you search for a node and the node is not in the semi-splay tree, you *still* have to perform semi-play on the search path in the tree.  
But isn't that basically pushing nodes to the root that aren't actually have been searched for?

So my question would be : why do you still have to perform semi-splay even if the node you search for is not in the tree?

**Tags:** ds.data-structures, tree, dynamic-algorithms

---

## 1 answers

### Answer by username_1 on 2011-01-17. Score: 8 | Accepted answer

To complete the search process for an element $x$ that is not in the tree, you have to go all the way to a leaf node to confirm that $x$ is not in the tree. If you repeatedly search for such an element $x$, you have to splay on an unsuccessful search, otherwise the query time for $x$ could indefinitely remain as bad as $\Theta(n)$, even in an amortized sense.

> **Comments:**
> **username_0**: Aah, i hadn't thought of that. Makes perfectly sense, thanks!  

---

