Post by Farhang FaridHi guys
I was wondering if any body can help me
with an algortihm to convert AVL trees to Red black trees?
A few years ago I wrote a C library called Austin in which an
existing, populated instance of a dictionary object can be mutated
among different representations. Among the representations are sorted
list, splay tree, AVL tree, regular binary search tree and red-black
tree. You can tell the object to go from any representation to any
other. If no specific conversion algorithm ``override'' exists for
that combination, then it's done by converting to a linear list, and
then from the list to the target. (All of the back-ends support
flattening to a list, and construction from a sorted list).
See http://users.footprints.net/~kaz/austin.html
I can't remember whether there is a handler for going straight from
AVL to red-black, but like it's been said elsethread, it should just
involve a coloring of the nodes. There is a function for going from
sorted list to red-black in O(N); a balanced tree is constructed and
colored.
AVL trees are more strictly balanced than Red-Black Trees, so all you
have to do is color the nodes.
Tips:
If you anticipate that the re-colored tree will be subject to the
insertion of a lot more items just color all of the internal nodes
black, with the exception of unbalanced leaf nodes that must be
colored red in order to maintain the black height property. By
painting as much of the tree black as possible, you allow for the
insertion of lots of red nodes without rebalancing.
Alternately, if you anticipate lots of deletions, then paint the tree
in alternating red-black layers, which maximizes the red content.