How to build tree with more than 6 vertices, that after operation splay() would have depth = number of vertices? Is it possible?
UPD: Example for n = 4:
- insert 60
- insert 10
- insert 20
- insert 50
- splay(10)
You can use splay tree visualization
$\begingroup$
$\endgroup$
-
$\begingroup$ Are there such examples when the number of vertices is less than or equal to 6? Please show them in the question. $\endgroup$ – John L. Dec 23 '18 at 17:50
-
1$\begingroup$ @Apass.Jack I added an example for n = 4 $\endgroup$ – Gleb Dec 23 '18 at 18:14
-
$\begingroup$ Depth should be $n-1$ instead of $n$. By convention, a tree with only a single vertex (hence both a root and leaf) has depth and height zero. $\endgroup$ – John L. Dec 24 '18 at 2:14
$\begingroup$
$\endgroup$
This is a good question whose answer can help us understand how splay tree tends to keep away from being imbalanced.
No, it is impossible for any rooted tree with more than 5 vertices to become a linear tree after operation splay() one of the deepest vertices, i.e. its depth is one less than the number of vertices.
Why?
For the sake of contradiction, let there be a rooted tree with more than 5 vertices which becomes a linear tree after splaying $x$, one of its deepest vertices. Consider the point of time just before the last splay step that moves $x$ to the root. There are three cases.
- That last step is a zig-step (the following graph) or its mirroring zag-step. Since the resulted tree is linear, part $A$ and $B$ are empty. That means, the left subtree of the root before that step contains node $x$ only. Since $x$ is the deepest node, the whole tree has at most 3 nodes, which is not true.
- That last step is zig-zig step (the following graph) or its mirroring zag-zag. Since the resulted tree is linear, part $A$, $B$ and $C$ are empty. That means, the left subtree of the root before that step contains node $P$ and $x$ only. Part $D$ can have at most two nodes; otherwise, either $x$ was not the deepest node or the resulted tree is not linear. So the whole tree has at most 5 nodes, which is not true.
- That last step is a zig-zag step (the following graph) or its mirroring zag-zig. However, after that step, the root will alway has two children, which is not ture.
Exercise. Draw a tree with 5 vertices that becomes a linear tree after splaying one of its deepest vertices.
