Red black tree sort: Difference between revisions
Content added Content deleted
(red black trees need a rosettacode task) |
mNo edit summary |
||
| Line 1: | Line 1: | ||
{{draft task}} |
{{draft task}} |
||
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. |
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. |
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. Since we are using a red-black tree here, this would eliminate any duplicate values. |
||
You may use an implementation at [[Algebraic data types]] as a starting point, if you find that helpful. |
You may use an implementation at [[Algebraic data types]] as a starting point, if you find that helpful. |
||
Revision as of 17:14, 13 June 2022
Red black tree sort is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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. Since we are using a red-black tree here, this would eliminate any duplicate values.
You may use an implementation at Algebraic data types as a starting point, if you find that helpful.