AABBCC
Reputation: 77
Is it possible to convert all AVL trees to red-black trees?
While I was studying Search Trees, I found a problem
Show that the nodes of any AVL tree T can be colored "red" and "black" so that T becomes a red-black tree.
And now I wonder whether converting any AVL tree to red black tree is possible.
Upvotes: 1
Views: 732
Answers (1)
bottaio
Reputation: 5093
Yes, it is possible.
General idea is to turn red some of nodes that are roots of subtrees of odd height. More specifically, we turn red only those whose parents are root of subtrees of even height. You can prove that using recursion.
Upvotes: 1
Related Questions
- Is there any red black tree or avl tree implementation in c++ standard library?
- Red-black tree over AVL tree
- Convert AVL Trees to Red Black tree
- Convert Red-Black tree to AVL tree
- Do Red-Black tree and AVL tree have same balance condition?
- Difference between red-black trees and AVL trees
- Comparison of Avl Tree and Red Black Tree
- AVL tree rotation and red-black tree color flips
- Mass operations on Red-Black Trees?
- Can I represent a Red-black tree as binary leaf tree?