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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.