On (02 Jun 97) Neil Burrows wrote to Jerry Coffin...
[ problem situation for keeping a binary tree balanced: ]
 NB> Unless your as thick as me and load in a dictionary file which is
 NB> already in alphabetical order!  :(
This is still fairly easy to handle as a rule.  Load the data into
memory in an array, then create your binary tree out of the data
recursively.  For the moment I'll assume a fixed record size in the
array:
template 
struct node {
    node *left;
    node *right;
    T *data;
    node(node *left, node *right, T *data);
};
template 
class dictionary {
    node *root;
    long entries;
    T *data;
    void create(T *start, long number) {
        create(start, number, root);
	}
    create(dict_entry *start, long number, dict_entry &*root) {
        // create a node for the middle item.
        root = new node(NULL, NULL, start + number / 2);
        // put any items below the middle in the left subtree
        if ( number / 2 > 0 )
            create(start, number / 2, &(*root)->left);
        // put any items above the middle in the right subtree
        if ( number / 2 < number )
            create(start+number/2, &(*root)->right);
    }
public:
    dictionary(ifstream &str) : root(0) {
        str.read(static_cast(&entries), sizeof(entries));
        data = new dict_entry[entries];
        str.read(static_castdata, entries * sizeof(*data));
        create(data, entries);
    }
};
As with many recursive solutions, this is almost deceptively simple.
Due to division on integers truncating instead of rounding, this will
create trees that tend to be skewed slightly to the right, but not
drastically so.
    Later,
    Jerry.
... The Universe is a figment of its own imagination.
--- PPoint 1.90
---------------