The problem was to give an algorithm to determine if a given binary tree can be coloured with red/black such that it satisfies the constraints of a red-black tree.
Solution
A Red black has this property:
For any node, the length of the shortest path (to a leaf node) is atleast half the length of the longest path (to a leaf node). In other words, for any sub-tree, the shortest height is at least half the height.
This condition is actually sufficient too, and can be proved via induction (I am feeling lazy and will leave that to you).
The usage of this condition gives us an $O(n)$ time algorithm to determine if a given binary tree is actually a red-black tree.
Solution
A Red black has this property:
For any node, the length of the shortest path (to a leaf node) is atleast half the length of the longest path (to a leaf node). In other words, for any sub-tree, the shortest height is at least half the height.
This condition is actually sufficient too, and can be proved via induction (I am feeling lazy and will leave that to you).
The usage of this condition gives us an $O(n)$ time algorithm to determine if a given binary tree is actually a red-black tree.
No comments:
Post a Comment