I have to implement a red-black tree in C++ for a project, but I don't know much about red-black trees. I've been trying to do my research for a few days now, but I still feel pretty lost.
1. Here is what I know:
a. They are binary trees.
b. Every node is either red or black.
c. The root is black.
d. Every path from the root to a leaf contains the same number of black nodes.
e. Red nodes can only have black children.
f. Every leaf is NULL and black.
2. Are this properties correct? Are there any other properties that I need to know?
3. I'm assuming it is more common to use an array rather than pointers. Is this true?
4. What make a node red or black? And what advantage do I get out of having red and black nodes.
5. Anyone know of any good sites with good examples?
1. Here is what I know:
a. They are binary trees.
b. Every node is either red or black.
c. The root is black.
d. Every path from the root to a leaf contains the same number of black nodes.
e. Red nodes can only have black children.
f. Every leaf is NULL and black.
2. Are this properties correct? Are there any other properties that I need to know?
3. I'm assuming it is more common to use an array rather than pointers. Is this true?
4. What make a node red or black? And what advantage do I get out of having red and black nodes.
5. Anyone know of any good sites with good examples?
