Supernode Binary Search Trees

Balanced binary search tree structures such as AVL, red-black, and splay trees store exactly one element per node. We propose supernode versions of these structures in which each node may have a large number of elements. Some properties of supernode binary search tree structures are established. Experiments oonducted by us show that the supernode structures proposed by us use less space than do the corresponding one-element-per-node versions and also take less time for the standard dictionary operations: search, insert and delete.