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.
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);
}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.
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
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.
static class btree * btree_find_first_right(const void * key);Find the first element from the right matching key or being smaller then key.
static class btree * btree_find_next_left(class btree * tree, const void * key);Find the first element from the left being bigger then key.
static class btree * btree_find_next_right(class btree * tree, const void * key);Find the first element from the right being smaller then key.
static class btree * btree_find_left(class btree * tree);Returns the left most element
static class btree * btree_find_right(class btree * tree);Returns the right most element
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.
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.
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.
void tree_leak_check(class btree * tree);Calls the leak_check functions of all elements in the tree.
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
class btree * btree_find_first_left(const void * key);Find the first element from the left matching key or being bigger then key.
class btree * btree_find_first_right(const void * key);Find the first element from the right matching key or being smaller then key.
class btree * btree_find_next_left(const void * key);Find the first element from the left being bigger then key.
class btree * btree_find_next_right(const void * key);Find the first element from the right being smaller then key.
class btree * btree_find_left();Returns the left most element
class btree * btree_find_right();Returns the right most element
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.
class btree * btree_get(class btree * out);Removes the object out from the tree. If the object does not exists the call will assert.
int get_count() { return count; };Returns the number of elements in the subtree. This is the number of elements below the element plus one.
void print_tree(int level);This is a platform specific function to print the content of the tree for debugging.
void tree_leak_check();Calls the leak_check functions of all elements in the tree.