Multiple values in binary trees
April 14, 2005
Posted by on
I had a small ‘ah-hah’ experience while reading Implementing sets efficiently in a functional language. Descriptions of binary tree sorting/searching algorithms, such as the excellent Introduction to Algorithms, state that items to be sorted have to be strictly ordered, which means you can’t have duplicates in the tree. But this is easily solved by storing duplicates together in the same binary tree node. “The implementing sets” article suggests adding a ‘count’ field to the node, which marks how many copies are in the node. Often, though, the key and value of a node are different–which suggests that (if the values are strictly ordered as well) you can use the same kind of binary tree to store values. Often it is the insertion order that matters, in which case this can be used as a key.