1
$\begingroup$

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

enter image description here

$\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$ – Apass.Jack 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$ – Apass.Jack Dec 24 '18 at 2:14
1
$\begingroup$

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.

zig-zag from https://en.wikipedia.org/wiki/Splay_tree#Splaying

  • 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.

zig-zig from https://en.wikipedia.org/wiki/Splay_tree#Splaying

  • 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.

zig-zag from https://en.wikipedia.org/wiki/Splay_tree#Splaying


Exercise. Draw a tree with 5 vertices that becomes a linear tree after splaying one of its deepest vertices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.