Binary Search Trees should be good enough
This program feeds random numbers into a binary search tree (BST) to demonstrate that it is only about 35% worse than the ideal. It is pointer space, not record space that the surcharge pertains to. The time wasted in traversing the random binary tree can be reduced by selecting the first few keys near the root.
If the input data is sorted, or almost so, an almost balanced tree results by selecting the middle element, splitting the list around the pivot, and proceeding similarly in a recursive manner. Elegant ways to reduce the asymmetry in a randomly formed binary tree include red-black trees and balanced trees. They appear to have become rather old reading, given modern computing facilities.