Originally posted by Ernest Friedman-Hill:
You just want to store your records in a binary tree. Then you can quickly add a new record in the right place without resorting the whole thing.
For example, a TreeSet with an appropriate Comparator.
@OP: A small side note:
A binary tree (BT) tells nothing about the order of the structure: a BT is just a structure where each node in it has at 0, 1 or 2 children. A binary search tree (BST) however orders the nodes: "smaller" nodes go into the left subtree and "greater" (or equal) nodes into the right subtree of each node. Now a TreeSet or TreeMap is backed up internally by a red-black tree which is a special kind of BST: one that, while inserting nodes, balances itself so that the tree guarantees lookups, insertions etc. in log(n) time, where n is the total number of nodes in the tree.
[ August 29, 2008: Message edited by: Piet Verdriet ]