You have a Black-Red Tree of height
hthat has two childs:
- Left child is a full binary tree of height
- Right child is a full binary tree of height
Balance the tree so both childs of root are of the same height (you don't have to keep the other nodes balanced, just the root).
From Wikipedia I understood that:
When a subtree is rotated, the subtree side upon which it is rotated increases its height by one node while the other subtree decreases its height. This makes tree rotations useful for rebalancing a tree.
So the solution would be to right-rotate the root, and then the left and right childs' heights will become
The left child node height did decrease by one, but the right child node increased by two!
- Why is it happening? Is wikipedia wrong?
- How can I do it otherwise?