Balancing a Binary Search Tree (BST)

Question

I'm trying to make a balance_bst(bstNode root) function, but i'm struggling with the implementation.

I'm implementing the function as a template function, since my bstNode class is a template class.

Here is (some of) my code:

template<class Item, class  Key>
class bstNode{
public:
    //Constructor
    bstNode(const Item& init_data = Item(), const Key& init_key = Key(), bstNode<Item, Key>* l_child = NULL, bstNode<Item, Key>* r_child = NULL){
        data_field = init_data;
        key_field = init_key;
        l_ptr = l_child;
        r_ptr = r_child;
    }
    //Destructor
    ~bstNode(){
        data_field = 0;
        key_field = 0;
        l_ptr = r_ptr = NULL;
    }
    //Basic Member Functions
    bstNode<Item, Key>*& left( )   {                    return l_ptr;       }           //returns left child pointer by reference
    bstNode<Item, Key>*& right( )  {                    return r_ptr;       }           //returns right child pointer by reference
    bstNode<Item, Key>* left( ) const   {               return l_ptr;       }       //returns left child pointer by reference
    bstNode<Item, Key>* right( ) const  {               return r_ptr;       }       //returns right child pointer by reference
    const Item& data() const{                           return data_field;  }           //returns reference to data_field
    const Key& key()const {                             return key_field;   }
    Item& data() {                                      return data_field;  }           //returns reference to data_field
    Key& key() {                                        return key_field;   }
    void set_data(const Item& new_data){            data_field = new_data;      }       //sets data_field to new_data
    void set_key(const Key& new_key){               key_field = new_key;        }       //sets key_field to new_key
    void set_left(bstNode* new_left){               l_ptr = new_left;           }       //sets left child pointer to new_left
    void set_right(bstNode* new_right){             r_ptr = new_right;          }       //sets right child pointer to new_right

private:
    bstNode<Item, Key>  *l_ptr,     //pointer to left child node 
                        *r_ptr;     //pointer to right child node
    Item    data_field;
    Key     key_field;
};

template<class Item, class Key>
void balance_bst(bstNode<Item, Key>*& root){                //unfinished

    std::vector< bstNode<Item, Key>* > nodes;
    sorter(root, nodes);
    size_t i = nodes.size()/2;                      //size() divided by 2 will yield
                                                    //index of middle element of vector for 
                                                    //odd-isized arrays and the greater of the 
                                                    //middle two elements for an even-sized array

    while(i>=0){
        root->set_key(nodes[i]->key());                             
        root->set_data(nodes[i]->data());
         //.....MORE CODE HERE: recursive call??

    }


}

template<class Item, class Key>
void sorter(bstNode<Item, Key>*& root, std::vector<bstNode<Item, Key>* >& tree_nodes){
    if(root == NULL)
        return;
    sorter(root->left(), tree_nodes);
    tree_nodes.push_back(root);
    sorter(root->right(), tree_nodes); 
}

I've been messing with the actual balance_bst function, and think that recursion is the obvious solution but i can't seem to wrap my head around this one...

sorter basically inserts the elements of a BST into a vector using an inorder processing algorithm. So as long as "root" is a pointer to the root of a binary search tree(ie all key values of a nodes left subtree are less than the key value of the nodes and all key values of the nodes right subtree are greater than the nodes) then the nodes inserted into the vector will be sorter in an ascending manner.

Then, to create a balanced tree, i insert the node at the center of the vector at the root of the tree, and then should be able to recursively insert the left and right children nodes which would then be at the middle of the left half of the vector and the middle of the right half of the vector.

Note: i understand that this is using integer division and that say, 7/2 = 3, which would be the index of the middle element of an array of size 7. And for even-sized arrays, the algorithm implemented above will find the index of the greater of the two elements in the middle of the vector.

Anyway, any suggestions or observations are welcomed and encouraged! Thanks in advance.

Edit: What I am asking is how do I implement a function to balance a binary search tree? (A balanced BST is one that has the minimum depth it can given the number of nodes.)

Answer 1

A balanced binary search tree is also known as an AVL tree .

This wikipedia link has a good explanation on solving the balancing problem.

I found the easiest way to balance the tree is during insertion. Here is a recursive insert with helper functions (for the various rotate cases) and an AVLNode class.

        bool avl_insert(AVLNode*& subRoot, const int &newData, bool &taller)
        {
            bool result = true;
            if(!subRoot){
                subRoot = new AVLNode(newData);
                taller = true;
            }
            else if(newData == subRoot->getData()){
                result = false;
                taller = false;
            }
            else if(newData < subRoot->getData()){
                result = avl_insert(subRoot->getLeft(), newData, taller);
                if(taller)
                    switch(subRoot->getBalance()){
                    case -1:
                        left_balance(subRoot);
                        taller = false;
                        break;
                    case 0:
                        subRoot->setBalance(-1);
                        break;
                    case 1:
                        subRoot->setBalance(0);
                        taller = false;
                        break;
                    }
            }
            else{
                result = avl_insert(subRoot->getRight(), newData, taller);
                if(taller)
                    switch(subRoot->getBalance()){
                    case -1:
                        subRoot->setBalance(0);
                        taller = false;
                        break;
                    case 0:
                        subRoot->setBalance(1);
                        break;
                    case 1:
                        right_balance(subRoot);
                        taller = false;
                        break;
                    }
            }
            return result;
        }

Helper Functions

        void right_balance(AVLNode *&subRoot)
        {
            AVLNode *&right_tree = subRoot->getRight();
            switch(right_tree->getBalance()){
            case 1:
                subRoot->setBalance(0);
                right_tree->setBalance(0);
                rotate_left(subRoot); break;
            case 0:
                cout<<"WARNING: program error in right_balance"<<endl; break;
            case -1:
                AVLNode *subTree = right_tree->getLeft();
                switch(subTree->getBalance()){
                    case 0:
                        subRoot->setBalance(0);
                        right_tree->setBalance(0);break;
                    case -1:
                        subRoot->setBalance(0);
                        right_tree->setBalance(1); break;
                    case 1:
                        subRoot->setBalance(-1);
                        right_tree->setBalance(0);break;
                }
                subTree->setBalance(0);
                rotate_right(right_tree);
                rotate_left(subRoot); break;
            }
        }
        void left_balance(AVLNode *&subRoot)
        {
            AVLNode *&left_tree = subRoot->getLeft();
            switch(left_tree->getBalance()){
            case -1:
                subRoot->setBalance(0);
                left_tree->setBalance(0);
                rotate_right(subRoot); break;
            case 0:
                cout<<"WARNING: program error in left_balance"<<endl; break;
            case 1:
                AVLNode *subTree = left_tree->getRight();
                switch(subTree->getBalance()){
                    case 0:
                        subRoot->setBalance(0);
                        left_tree->setBalance(0);break;
                    case -1:
                        subRoot->setBalance(0);
                        left_tree->setBalance(1); break;
                    case 1:
                        subRoot->setBalance(-1);
                        left_tree->setBalance(0);break;
                }
                subTree->setBalance(0);
                rotate_left(left_tree);
                rotate_right(subRoot); break;
            }
        }

    void rotate_left(AVLNode *&subRoot)
    {
        if(subRoot == NULL || subRoot->getRight() == NULL)
            cout<<"WARNING: program error detected in rotate_left"<<endl;
        else{
            AVLNode *right_tree = subRoot->getRight();
            subRoot->setRight(right_tree->getLeft());
            right_tree->setLeft(subRoot);
            subRoot = right_tree;
        }
    }
    void rotate_right(AVLNode *&subRoot)
    {
        if(subRoot == NULL || subRoot->getLeft() == NULL)
            cout<<"WARNING: program error detected in rotate_left"<<endl;
        else{
            AVLNode *left_tree = subRoot->getLeft();
            subRoot->setLeft(left_tree->getRight());
            left_tree->setRight(subRoot);
            subRoot = left_tree;
        }
    }

AVLNode class

class AVLNode
{
  public:
        AVLNode()
        {
            previous = NULL;
            next = NULL;
        }
        AVLNode(int newData){
            data = newData;
            previous = NULL;
            balance=0;
            next = NULL;
        }
        ~AVLNode(){}
        void setBalance(int b){balance = b;}
        int getBalance(){return balance;}
        void setRight(AVLNode* newNext){next = newNext;}
        void setLeft(AVLNode* newPrevious){previous = newPrevious;}
        AVLNode* getRight() const{return next;}
        AVLNode* getLeft() const{return previous;}
        AVLNode*& getRight(){return next;}
        AVLNode*& getLeft(){return previous;}
        int getData() const{return data;}
        int& getData(){return data;}
        void setData(int newData){data = newData;}
        void setHeight(int newHeight){ height = newHeight;}
        int getHeight(){return height;}
  private:
        AVLNode* next;
        AVLNode* previous;
        int balance;
        int height;
        int data;
};

Hope this helps!