[FEATURE REQUEST] Transfrom AVL tree to Red-Black tree.
WilliamNian opened this issue · 4 comments
What would you like to Propose?
I propose to add the algorithm for this transformation.
I also propose to add the junit tests for them.
Issue details
AVL tree
Red-Black tree
Additional Information
No response
I would like to work on this
I would like to work on this
Your current code does two things:
It ensures that the root of the resulting red-black tree is black.
It gives each new node a red color by default.
But after the conversion, attributes 4 and 5 of the red-black tree may be violated.
Considering that AVL trees are also balanced binary search trees (like red-black trees, but with stricter balancing criteria), a direct conversion needs to ensure that the resulting red-black tree follows its properties. This is very complex, and a direct recursive conversion like yours may not always produce a valid red-black tree. Also you will have too many red nodes than black nodes, which doesn't make sense. I will complete the code for the correct AVL tree to red-black tree conversion afterwards
This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.
Please reopen this issue once you add more information and updates here. If this is not the case and you need some help, feel free to seek help from our Gitter or ping one of the reviewers. Thank you for your contributions!