This content originally appeared on DEV Community and was authored by Paul Ngugi
An unbalanced tree becomes balanced by performing an appropriate rotation operation. Section, Rebalancing Trees, illustrated how to perform rotations at a node. The code below gives the algorithm for the LL rotation, as illustrated in Figure below.
1 balanceLL(TreeNode A, TreeNode parentOfA) {
2 Let B be the left child of A.
3
4 if (A is the root)
5 Let B be the new root
6 else {
7 if (A is a left child of parentOfA)
8 Let B be a left child of parentOfA;
9 else
10 Let B be a right child of parentOfA;
11 }
12
13 Make T2 the left subtree of A by assigning B.right to A.left;
14 Make A the right child of B by assigning A to B.right;
15 Update the height of node A and node B;
16 } // End of method
Note that the height of nodes A and B can be changed, but the heights of other nodes in the tree are not changed. You can implement the RR, LR, and RL rotations in a similar manner.
This content originally appeared on DEV Community and was authored by Paul Ngugi
Paul Ngugi | Sciencx (2024-07-24T19:58:09+00:00) Implementing Rotations. Retrieved from https://www.scien.cx/2024/07/24/implementing-rotations/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.