calgorithmdata-structuressplay-tree

When I traverse in the splay tree, then now which one is root?

I had a doubt when we are using a splay tree, the last accessed element will come to the root node. consider my tree is 

                     5
                    / \
                   3   7
                  / \ / \
                 2  4 6  8

when I perform a inorder traversal, the output will be

     2 3 4 5 6 7 8

so here the last accessed element is 8, in that I have a doubt, so the 8 will be the last accessed node, so we want to move 8 as a root node or not?

Solution

  • Your logic is correct. But the operation of splaying is only done during insertion and searching and not during traversal. When you insert or search a node it is moved to the top(made as root node) so that it would be accessed quickly thereafter.