My question concerns link/cut tree structure after an access operation. I am assuming an implementation with splay trees. As far as I can tell, once you access a node v and splay it to the root, it no longer has a preferred child and therefore no longer has a right sub-tree. Furthermore, you move this tree up to the root of the entire structure, thus the link/cut tree is unbalanced at the root.

My question is about intuition. It seems very counter-intuitive to purposefully unbalance the tree at the root. I understand in the amortised sense, unbalanced trees are perfectly fine but I cannot understand the intuition behind the choice. Is the gain you get from having the most recently accessed item at the root outweigh the fact that you only have 1 child? Is there something else I am misunderstanding? Are there other examples of structures were a counter-intuitive choice is still a benefit?

  • $\begingroup$ It looks like you misunderstood splay tree significantly. I cannot see how splay tree is associated to the "the fact that you only have 1 child". I cannot see how splay tree "purposefully unbalance the tree at the root". $\endgroup$ – Apass.Jack Nov 6 '18 at 21:46
  • $\begingroup$ I don't think I misunderstand the use of splay trees, but that you splay something to the root that only has 1 child. $\endgroup$ – Kaari Landry Nov 7 '18 at 2:14
  • $\begingroup$ Cab you give an example what leads to the situation when "you only have 1 child"? I do not know about you, but the operations by splay tree look like magic to me, i.e., magically balancing the tree most of the time. $\endgroup$ – Apass.Jack Nov 7 '18 at 2:46
  • $\begingroup$ This happens specifically in the link/cut structure which stores graphs as a tree of trees(simply put). The graph is broken down in "preferred paths" where each splay tree is made of a path of nodes who are keyed by their position along the path. An access operation to a node will cause it to become the end of its path AND cause it to move to the root of it's splay tree. The result: the are no keys greater than it (nothing further in the path) so it has no right sub-tree AND it's moved to the root. It's like a magic unbalancing. $\endgroup$ – Kaari Landry Nov 7 '18 at 13:32

Your Answer

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

Browse other questions tagged or ask your own question.