I am searching for a proof that all AVL trees can be colored like a red-black tree? Can anyone give the proof?
3
votes
I don't understand the question.
– yfeldblum
Although we are willing to help, we won't do your homework. So give it a try first and if you are stuck, come back and ask a specific question.
– Toon Krijthe
@Justice, he is looking for a proof that all avl trees can be colored with two colors without two connected nodes having the same color.
– Toon Krijthe
color(node) = if is_even(depth(node)) then "black" else "red" ... is that really the question? Or is he asking whether an AVL tree can be colored such that it obeys all the properties of a red-black tree?
– yfeldblum
@Justice: The latter, I think
– jpalecek
3 Answers
1
votes
By definition R/B trees can be slightly less balanced then AVL-s, as |maxPath - minPath| must be <= 1 for AVLs and maxPath <= 2 * minPath for R/Bs so that not every R/B is an AVL but on the other hand there is no need for the AVL-s To have Empty subTrees so
4
/ \
3 6
/\ /\
1 E 5 8
is a perfectly legal AVL and it is not an R/B because R/B cannot contain Leaves and must be terminated by Empty trees which are coloured always Black - so that you cannot colour the tree above. To make it R/B you are allowed to convert every leaf x into node E x E and then follow these rules: R/B Tree: Must be a BST must contain only nodes and empty trees which are coloured either Black or Red Every Red node has black children All Empty Trees are Black Given a node, all paths to Empty Trees must have same number of Black Nodes Any Leaf can be replaced with Node whose Left & Right subTrees are Empty Max Path T ≤ 2 * Min Path T
Btw just realized it coloured my nodes and leaves in Red - this was not intended. Karol
-2
votes
