Introduction
At least one of the binary tree projects on this site mentions the need for a balanced tree, but none of them provide a balancing function. This project does provide a balancing function.
C++ language features used
- Pointers to class member functions
- Templates
- Exceptions
How a binary tree works
The heart of a binary tree is a node. The node contains three pointers, and in this implementation, two counters. The left
pointer points to a node containing a pointer to the value less than the value of the current node. The right
pointer points to a node containing a pointer to the value greater than the value of the current node. The data
pointer points to the class that contains the data. The counters each count the number of nodes under the left
and right
pointers. These counters are currently used during the balance function to allocate the correct number of pointers. Placing these counters in the node allows for easier detection that the tree needs to be rebalanced, but I leave the coding of that detection to someone else.
template <class <code>T>
struct SNode
{
SNode* left; SNode* right; T* data; unsigned left_count; unsigned right_count;
SNode( T* init )
{
left = NULL;
right = NULL;
data = init;
left_count = 0;
right_count = 0;
}
}
Flags
When the node is deleted, the data
member is deleted first if delete_data
is true
.
It is a complete overkill for only one flag. Allow the initialization of all flags by setting the value flags_value
.
union flags_union_type
{
unsigned flags_value;
struct flags_type
{
unsigned delete_data:1;
} flags;
} flags_union;
The balancing function creates a new binary tree by creating new nodes and then deletes the old nodes. An array is initialized by transversing the tree in a low to high order. The array is then loaded into a new tree by selecting the midpoint of the array and inserting it. Next, the function to insert from the array into the binary tree is called recursively to load the rest of the array. When the function to load the new binary tree is completed, the new head replaces the old head and the balancing is complete.
Binary tree public functions
template <class T>
class CBinTree
{
public:
CBinTree(bool (T::*lt)(T&), bool (T::*gt)(T&));
void Add( T* data );
void InOrderLowToHigh( void (T::*fp)() );
void InOrderHighToLow( void (T::*fp)() );
void Balance();
bool Search( T* target, T*& found );
void DeleteData( bool value );
bool Remove( T* target );
};
Using the code
To allow multiple binary trees to be used on a single data object, the binary tree constructor takes two pointers to member functions on the data class: a less than function pointer and a greater than function pointer. To see how this is done, check out the demo project.
- The
Add
function is called to add a data class to the binary tree. - The
InOrderLowToHigh
function is used to iterate over every node in the tree, and calls the function specified by the fp
class member function pointer. To see how this is done, check out the demo project. - The
InOrderHighToLow
function is used to iterate over every node in the tree, and calls the function specified by the fp
class member function pointer. To see how this is done, check out the demo project. - The
Balance
function has already been described above. - The
Search
function returns true
if found, and false
if not found. If the target
is found, found
is populated with a value. If the target
was not found, found
contains NULL
. - The
DeleteData
function simply assigns the passed parameter to the delete_data
variable. - The
Remove
function is similar to Search
, but deletes a node from the tree.
Potential enhancements
- Could be made thread safe. This would allow the balance function to be run by a worker thread.
- Could add calculation to determine if re-balancing the tree is preferable. This is why the count variables are in the node.
History