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
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityHow 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:
You can use splay tree visualization
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.
Exercise. Draw a tree with 5 vertices that becomes a linear tree after splaying one of its deepest vertices.