Self-balancing binary tree

• Download source files - 3.76 KB
• Download demo project - 6.68 KB

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;            // points to a node that contains a value less than this node
    SNode* right;           // points to a node that contains a value greater than this node
    T* data;                // points to the data
    unsigned left_count;    // count of how many nodes are hanging off of the left pointer
    unsigned right_count;   // count of how many nodes are hanging off of the right pointer

    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

• 2006/10/15 - Release 1.