Clever Geek Handbook

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

I got a doubt, when we use the splay tree, the last available element will hit the root node. count my tree

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

when i traverse in order the output is

     2 3 4 5 6 7 8

so here is the last accessor 8

, I doubt it, so 8

will be the last available node, so we want to move 8

as root node or not?

+3


source to share


1 answer


Your logic is correct. But the reversal operation is performed only during insert and search, not during traversal. When you insert or search in a node, it moves to the top (made as a root node) so that it is quickly available after that.



0


source






More articles:


All Articles