CODEWITHSUNDEEP
algorithmdata-structurestree
Moeb
Moeb

Reputation: 10871

What are the advantages of rotating a tree before destroying it?

I am reading through this article, where it is mentioned that we can get rid of one side of the tree by performing rotations in a specific manner, and then traversing the tree down in one direction and deleting the elements.

Although I understand what they are trying to do, I do not understand why?

What advantages might this type of deletion provide as opposed to a simple postorder deletion?

One advantage I can think of is saving on the memory used by recursion, but I think that is an insignificant overhead as compared to traversing the tree twice, once for rotating, and then for deleting. Am I missing something here?

Upvotes: 2

Views: 89

Answers (1)

mcdowella
mcdowella

Reputation: 19611

The article seems to be staying that the point of this method is to avoid recursion (and its consumption of stack space): "Hmm...what if we rearranged nodes so that they didn't have any left subtrees? Then we could just descend to the right, without need to keep track of anything on a stack."

In general, I prefer to avoid recursion when I cannot be sure that its depth will be reasonable, because you will run out of stack space long before you run out of any other sort of memory - in some cases because the system is designed to limit recursion to catch errors causing infinite recursion. However, I think this is less important here, where you have already admitted that other routines in the same package need recursion. Also, the depth of recursion depends on the depth of the tree, and for a balanced tree this will be roughly the logarithm of the number of nodes it it, and so should never be too deep.

Upvotes: 3

Related Questions