CODEWITHSUNDEEP
treebinary-treepascal
Nagarz
Nagarz

Reputation: 166

About binary tree rotations

Im trying to program an AVL on pascal. I already programmed a regular binary tree and it works, im trying to make a self-balanceable one, and i have encountered a problem.

I have a subtree i want to rotate, and the thing is i don't know how to assign the parent of the subtree root node pointer. Meaning given the next tree: root node of the subtree i want to rotate = 30 parent node of the subtree = 55

          55                                      55          
       30    60            ----->           45         60         
   10    45    75                        30   50          75       
  5  15    50    90                     10                    90
                                      5    15

how am i supposed to change the pointer that goes from 55 to 30, to go from 55 to 45? Most of the code i've seen doesnt have a pointer that goes from a node to its parent so i dont know how to change it.

Upvotes: 2

Views: 112

Answers (1)

500 - Internal Server Error
500 - Internal Server Error

Reputation: 28829

You are not showing any code, but normally you would do something along the lines of

Root := Root.Rebalance;

That is, you call on the sub-tree to re-balance itself, and that re-balancing function returns the root as its result. That result may be the same root as previously or - as in your scenario - a new root node.

Upvotes: 3

Related Questions