Admin
1
consider we want just convert BST to red black tree just with coloring without any other change.
Why a Binary search tree with height of 2*log n not always convert to red-black tree using above facts, but fully balanced BST always can convert to red-black tree just with coloring?
Requiring a tree to have a certain height constrains the max depth but not the min depth. You can have a tree of height 2 log n with a shallow left subtree and a deep right subtree:
*
/ \
/ \
* *
/ \
/ \
/ \
/ \
/ \
/___________\
The black height has to be the same for all nodes, which means that the left subtree constrains the black height to be at most 2. There's no way to avoid a red-red edge in the right subtree with only two black nodes on each path, however.
