This will be a quick (and incomplete) post. I might edit to add more details later.
The goal was to determine if a given binary tree is a red black tree.
A well known necessary condition of a red-black tree: For each node the max height is no more than twice the min height.
This is in fact used to prove that the height is $O(\log n)$.
In fact, this is also sufficient!
Using this property gives us an easy $O(n)$ time algorithm.
I will leave the details of the proof and the algorithm to you :-).
The goal was to determine if a given binary tree is a red black tree.
A well known necessary condition of a red-black tree: For each node the max height is no more than twice the min height.
This is in fact used to prove that the height is $O(\log n)$.
In fact, this is also sufficient!
Using this property gives us an easy $O(n)$ time algorithm.
I will leave the details of the proof and the algorithm to you :-).
No comments:
Post a Comment