# btree

btree is a library of a self balanced binary search tree. The class btree is used as a base class on the objects in the tree. For the tree itself a btree * is used, which needs to be initialized to null for an empty tree.

The interface to put elements into the tree, get elements from the tree or find elements in the tree, a set of public static member functions is used. All these functions use the btree *, which is the reference to the tree as first argument. The put and get functions may change this btree *, so in this case the btree * is passed as reference.

The static member functions all map one to one to non-static member functions with the tree as this, so the non-static member functions could be used as well, except for an empty tree the btree * would be null and according to C++ standard, it is forbidden to call a non-static member with a null this pointer, so it is recommended to use the static member functions.

By convention the elements in the tree are sorted from left to righ, left being the "smallest" element and right the "biggest". For this the compare functions need to be according to the conventions below.

## File information

File | common/ilib/btree.h
Virtual functions | btree_compare leak_check
Public static functions | btree_find btree_find_first_left btree_find_first_right btree_find_next_left btree_find_next_right btree_find_left btree_find_right btree_put btree_get get_count tree_leak_check
Public functions | btree_find btree_find_first_left btree_find_first_right btree_find_next_left btree_find_next_right btree_find_left btree_find_right btree_put btree_get get_count print_tree tree_leak_check

### Virtual Functions

btree_compare

        virtual int btree_compare(void * key) = 0;
        virtual int btree_compare(class btree * b) = 0;

Compare functions, which need to be implemented for the sorting. The value addressed by the argument is compared to the value of the object. If the argument is smaller the the value of the object, the function should return a negative value, if the argument is bigger a positive value, if the value is identical 0. This way the elements are sorted left to right from small to big.

There are two versions of the compare function. One which takes a void * key as argument, which should be cast to the actual value to which to compare. This function is used by the library to find elements in the tree.
The other function takes a btree * b as argument. This function is used to put elements into the tree or remove elements from the tree. b should be case to the type of the element so that the real sorting value inside the element can be addressed.

Sample:

    int myObject::btree_compare(void * key) {
        return strcmp(name,(char * )key);
    }
    int myObject::btree_compare(btree * b) {
        return strcmp(name,((myObject *)b)->name);
    }

leak_check

    virtual void leak_check() {};

When the tree_leak_check function is called on an element, this function is called on this element and each element in the tree below this element. Typicall called on the root to perform leak_check on all elements.

### Public static functions

btree_find

    static class btree * btree_find(class btree * tree, const void * key);

Find an object in the tree. The argument 'key' is a pointer to the value used for comparing the objects

btree_find_first_left

    static class btree * btree_find_first_left(class btree * tree, const void * key);

Find the first element from the left matching key or being bigger then key.

btree_find_first_right

    static class btree * btree_find_first_right(const void * key);

Find the first element from the right matching key or being smaller then key.

btree_find_next_left

    static class btree * btree_find_next_left(class btree * tree, const void * key);

Find the first element from the left being bigger then key.

btree_find_next_right

    static class btree * btree_find_next_right(class btree * tree, const void * key);

Find the first element from the right being smaller then key.

btree_find_left

    static class btree * btree_find_left(class btree * tree);

Returns the left most element

btree_find_right

    static class btree * btree_find_right(class btree * tree);

Returns the right most element

btree_put

    static void btree_put(class btree * & tree, class btree * in);
    static class btree * btree_put(class btree * & tree, class btree * in, bool & before, class btree * & p);

Function called to insert an object into the tree. The argument in is the pointer to the new object.

There is a second version of this function which take the additional arguments bool & before and class btree * & p. These argumnents are used to return the neighbor of the added element. If before is true the new element was inserted before p, if before is false the element was inserted after p.

btree_get

    void btree_get(class btree * & tree, class btree * out);

Removes the object out from the tree. If the object does not exists the call will assert.

get_count

    int get_count(class btree * tree) { return count; };

Returns the number of elements in the subtree. This is the number of elements below the element plus one.

tree_leak_check

    void tree_leak_check(class btree * tree);

Calls the leak_check functions of all elements in the tree.

### Public functions

btree_find

    class btree * btree_find(const void * key);

Find an object in the tree. The argument 'key' is a pointer to the value used for comparing the objects

btree_find_first_left

    class btree * btree_find_first_left(const void * key);

Find the first element from the left matching key or being bigger then key.

btree_find_first_right

    class btree * btree_find_first_right(const void * key);

Find the first element from the right matching key or being smaller then key.

btree_find_next_left

    class btree * btree_find_next_left(const void * key);

Find the first element from the left being bigger then key.

btree_find_next_right

    class btree * btree_find_next_right(const void * key);

Find the first element from the right being smaller then key.

btree_find_left

    class btree * btree_find_left();

Returns the left most element

btree_find_right

    class btree * btree_find_right();

Returns the right most element

btree_put

    class btree * btree_put(class btree * in);
    class btree * btree_put(class btree * in, bool & before, class btree * & p);

Function called to insert an object into the tree. The argument in is the pointer to the new object. The return value is the new root. This function is called as member function on the root of the tree, which is a null pointer for an empty tree.

There is a second version of this function which take the additional arguments bool & before and class btree * & p. These argumnents are used to return the neighbor of the added element. If before is true the new element was inserted before p, if before is false the element was inserted after p.

btree_get

    class btree * btree_get(class btree * out);

Removes the object out from the tree. If the object does not exists the call will assert.

get_count

    int get_count() { return count; };

Returns the number of elements in the subtree. This is the number of elements below the element plus one.

print_tree

    void print_tree(int level);

This is a platform specific function to print the content of the tree for debugging.

tree_leak_check

    void tree_leak_check();

Calls the leak_check functions of all elements in the tree.