peteinthemorning
August 25th, 2009, 03:31 PM
Here's the scenario. I'm writing a library that gets some information from a file format that stores its data in a sorted list, and I'm writing it out to a file format that stores its data in a red-black tree. Since my input data is already sorted, I have the option of writing out a perfectly balanced binary tree in a single step. So here's my question.
As I write out my perfectly balanced red-black tree, I have the option of making ALL of the nodes black (assuming that there's exactly enough data for all the branches to be exactly the same length...otherwise, the final (non-leaf) node in the branches that are one node longer than the rest will be red.) That would make for a valid tree, but is it a good idea? If you hand a tree like that to someone else (who will be performing insertions and deletions on it), what is the performance impact of an all-black tree? Is that optimal, or would you be better off with some distribution of red nodes as well? Or does it not make any practical difference?
Thanks for any insight you might pass on...
-Pete
As I write out my perfectly balanced red-black tree, I have the option of making ALL of the nodes black (assuming that there's exactly enough data for all the branches to be exactly the same length...otherwise, the final (non-leaf) node in the branches that are one node longer than the rest will be red.) That would make for a valid tree, but is it a good idea? If you hand a tree like that to someone else (who will be performing insertions and deletions on it), what is the performance impact of an all-black tree? Is that optimal, or would you be better off with some distribution of red nodes as well? Or does it not make any practical difference?
Thanks for any insight you might pass on...
-Pete