CODEWITHSUNDEEP
algorithmdata-structuresrecursionsplay-tree
Andrew
Andrew

Reputation: 31

Recursive Splay Tree

I am trying to implement a recursive splay tree, bottom up. I recurse down to the node I am need to splay up, and I find the parent and grandparent of that node. Then I am able to either zig zag or zig zig depending on the situation just fine. The problem is after this is done, I return the node which has been splayed once to the previous recursive call. The previous recursive call is referenced to the parent of the node, which is now the child of that node. How do I recurse up splaying the node as I go up?

Upvotes: 3

Views: 1607

Answers (2)

Harisankar Krishna Swamy
Harisankar Krishna Swamy

Reputation: 39

When the tree gets totally "unbalanced" and really large (say as example 100000 int keys) then recursive algorithms may throw stackoverflow exception. Better to use a parent pointer in each node to get the parent or grand parent. This is one way of doing it. worked fine for me.

The results on the runtime are obvious heresplay tree runtime profiling

Upvotes: 0

comingstorm
comingstorm

Reputation: 26117

If I recall correctly, you build a left and right tree as you recurse down to the target node. When you find the target, you construct the final left and right trees using the (original) children of the target, attach the resulting trees as the new children of the target, and return the result in tail-recursive fashion (i.e., all the way back up the stack without further modification).

Upvotes: 1

Related Questions