Red black tree sort: Difference between revisions
m
should be obvious, but...
m (red black deletion is intricate and it should be implemented and tested.) |
m (should be obvious, but...) |
||
Line 3:
Implement red-black tree sorting of fixed width integers. Here, the left branch will only contain nodes with a smaller key and the right branch will only contain nodes with a larger key.
Start with an empty tree, add 30 nodes each with arbitrary (aka "random") keys, then traverse the tree, printing the values from the left node, the key value, then the values from the right node, displaying their value and their color (red or black). Since we are using a red-black tree here, this would eliminate any duplicate values.
Then delete an arbitrary 15 nodes and display the resulting tree.
| |||