Thursday, June 30, 2016

Pretty Printing of a Tree Data Structures [AVL tree example]

To debug a tree data structure, one usually constructs a set of test cases and use a pen and a piece of paper to draw and trace the tree data structure content at different steps of operations (insertion, deletion, ...). Everyone who has been doing this knows well that this is a tedious task, especially when the tree is big and data structure operations are complex.

This is why I'm introducing a nice tree printing (visualization) member function for you in C++. The function is generic, and you can easily modify it to work with any other tree data structures. The output from such function is as shown in the two examples below (enlarge the images to see them better; first one is for an AVL tree and second example is for 2-3 alike tree):



The function name is "printTree". I've integrated it with an AVL tree implementation that is adapted from Prof. Florin Balasa graduate class of advance algorithms. There are three source code files: "AvlTree.h", "AvlTree.cc", and "Application.cc". To compile with GNU compiler, simply run: "g++ Application.cc".

=====================================================
File AvlTree.h :
=====================================================
#ifndef  AVLTREE_H
#define  AVLTREE_H

#include <cstdlib>
#include <iostream>
using namespace std;

#define KEY_SPACE 10 //The maximum spaces needed to draw a key value like: 6,8,10,20,... (Including all the node braces)

//   Template classes for a node and for an AVL tree

template <class Obj>  class AvlTree;
template <class Obj>
class AvlNode {
    // Data members: the key, two pointers, and the height
    Obj key;       
    AvlNode *left, *right;
    int height;
    AvlNode(const Obj& ob = Obj(), AvlNode *= NULL, AvlNode *= NULL, int h = 0): key(ob), left(l), right(r), height(h) { }
    friend class AvlTree<Obj>;
};

template <class Obj>
class AvlTree {
        AvlNode<Obj>*  root;
    private:
        void makeEmpty(AvlNode<Obj>*& t) const;
        void rotateLeft(AvlNode<Obj>* & k1);
        void rotateRight(AvlNode<Obj>* & k2);
        void rotateLeftRight(AvlNode<Obj>* & k3);
        void rotateRightLeft(AvlNode<Obj>* & k1);
        AvlNode<Obj>* copyTree(AvlNode<Obj>* t) const;  
        void insert(const Obj& x, AvlNode<Obj>* & t);
        int height(AvlNode<Obj>* t) const { return(== NULL) ? -1 : t->height; }
        int max(int a, int b) const { return a>=? a : b; }
   public:
        AvlTree() { root = NULL; }
        AvlTree(const AvlTree& rhs); // The copy constructor
        ~AvlTree() { makeEmpty(root); }


      const AvlTree<Obj>& operator=(const  AvlTree& rhs);
      AvlTree<Obj>& insert(const  Obj& x) { insert(x, root);  return *this; }
      AvlNode<Obj>* find(const  Obj& x) const;
      AvlNode<Obj>* findMin() const;
      AvlNode<Obj>* findMax() const;
      AvlTree<Obj>& remove(const  Obj& x);
      void printTree() const;
};

#include "AvlTree.cc"
#endif
=====================================================
End of File AvlTree.h
=====================================================

=====================================================
File AvlTree.cc :
=====================================================
#include <stack>
#include <vector>  /* Needed in printTree */
#include <math.h>  /* pow and log10 functions needed in printTree */
#include <iomanip> /* Needed in printTree */
#include <sstream> /* Needed in printTree */
#include <fstream> /* Needed in printTree */
                   
template <class Obj>
AvlTree<Obj>::AvlTree(const AvlTree& rhs) { // The copy constructor
      root = copyTree(rhs.root);       
}

template <class Obj>
AvlNode<Obj>* AvlTree<Obj>::copyTree(AvlNode<Obj>* t) const {
       return( t == NULL ) ? NULL : new AvlNode<Obj>( t->key, copyTree(t->left), copyTree(t->right), t->height );
}

template <class Obj>
void AvlTree<Obj>::makeEmpty(AvlNode<Obj>*& t) const { // Deletes bottom-up the whole tree
       if( t != NULL ) {
             makeEmpty(t->left);       makeEmpty(t->right);
             delete t;      t = NULL;
      }
}

template <class Obj> 
const AvlTree<Obj>& AvlTree<Obj>::operator=(const AvlTree& rhs) { // The assignment operator
      if( this != &rhs ) {
            makeEmpty(root);
            root = copyTree(rhs.root);
     }
      return *this;
}

template <class Obj>
void AvlTree<Obj>::printTree() const { // d is the depth of the node in the tree
    if( root != NULL ) {
        vector<AvlNode<Obj>*> crtLvlNodes(0); // Stored in stack(no delete is needed)
        vector<AvlNode<Obj>*> nxtLvlNodes(0);
       
        crtLvlNodes.push_back(root);
       
        for ( int lvl=height(root)+1; lvl>0; lvl-- ) {
       
            int count = 2;
            for( int i=2; i<=lvl; i++ )
                count += pow(2,i) + pow(2,i-2)*(KEY_SPACE-4)/2;
           
            // Drawing nodes and horizontal branches
            for( int crtNode=0; crtNode<crtLvlNodes.size(); crtNode++ ) {
                if ( crtNode == 0 ) { // Spaces before first node in a level
                    for(int s = 1; s <= count/2; s++) cout << " ";
                    if (crtLvlNodes[crtNode] != NULL  && crtLvlNodes[crtNode]->left != NULL)
                        for (int s = 1; s <= count-count/2; s++) cout << "_";
                    else
                        for (int s = 1; s <= count-count/2; s++) cout << " ";
                }
                else { // Spaces before each node after the first in a level
                    if (crtLvlNodes[crtNode-1] != NULL  && crtLvlNodes[crtNode-1]->right != NULL)
                        for (int s = 1; s <= count/2+1; s++) cout << "_";
                    else
                        for (int s = 1; s <= count/2+1; s++) cout << " ";
                    for(int s = 1; s <= 2*count-2*(count/2)-2; s++) cout << " ";
                    if (crtLvlNodes[crtNode] != NULL  && crtLvlNodes[crtNode]->left != NULL)
                        for (int s = 1; s <= count/2+1; s++) cout << "_";
                    else
                        for (int s = 1; s <= count/2+1; s++) cout << " ";
                }
               
                if (crtLvlNodes[crtNode] == NULL) {
                    cout << setfill(' ') << setw(KEY_SPACE) << " ";
                    continue;
                }
                else {
                    stringstream s;
                    s << crtLvlNodes[crtNode]->key;
                    if (s.str().length() < (KEY_SPACE-2))
                        for(int i=1; i<=(KEY_SPACE-s.str().length()-2)/2+1; i++)
                            s << " "; // Centralize
                    cout << "(" << setfill(' ') << setw(KEY_SPACE-2) << s.str().substr(0,KEY_SPACE-2) << ")";
                    if ( crtNode == crtLvlNodes.size() - 1 && crtLvlNodes[crtNode]->right != NULL) { // Last node in a row with a right child
                        for (int s = 1; s <= count-count/2; s++) cout << "_";
                    }
                }

                if(crtLvlNodes[crtNode]->left != NULL) nxtLvlNodes.push_back(crtLvlNodes[crtNode]->left);
                else nxtLvlNodes.push_back(NULL);

                if(crtLvlNodes[crtNode]->right != NULL) nxtLvlNodes.push_back(crtLvlNodes[crtNode]->right);
                else nxtLvlNodes.push_back(NULL);
            }
           
            //Drawing slant branches
            if (lvl > 1) {
                cout << endl;
                for( int crtNode=0; crtNode<crtLvlNodes.size(); crtNode++ ) {
                    if ( crtNode == 0 ) { // Spaces before first node in a level
                        for(int s = 1; s <= count/2-1; s++) cout << " ";
                        if (crtLvlNodes[crtNode] != NULL  && crtLvlNodes[crtNode]->left != NULL) cout << "/";
                        else cout << " ";
                        for (int s = 1; s <=count-count/2+2-2; s++) cout << " ";
                    }
                    else { // Spaces before each node after the first in a level
                        for (int s = 1; s <= count/2+1; s++) cout << " ";
                        if (crtLvlNodes[crtNode-1] != NULL  && crtLvlNodes[crtNode-1]->right != NULL) cout << "\\";
                        else cout << " ";
                        for(int s = 1; s <= 2*count-2*(count/2)-2-2; s++) cout << " ";
                        if (crtLvlNodes[crtNode] != NULL  && crtLvlNodes[crtNode]->left != NULL) cout << "/";
                        else cout << " ";
                        for (int s = 1; s <= count/2+1; s++) cout << " ";
                    }
                   
                    if (crtLvlNodes[crtNode] == NULL) {
                        cout << setfill(' ') << setw(KEY_SPACE) << " ";
                        continue;
                    }
                    else {
                        cout << setfill(' ') << setw(KEY_SPACE) << " ";
                        if ( crtNode == crtLvlNodes.size() - 1 && crtLvlNodes[crtNode]->right != NULL) { // Last node in a row with a right child
                            for (int s = 1; s <= count-count/2; s++) cout << " ";
                            cout << "\\";
                        }
                    }
                }
            }
           
            crtLvlNodes = nxtLvlNodes;
            nxtLvlNodes.clear();
            cout << endl;
        }
    }
}

template <class Obj>
AvlNode<Obj>* AvlTree<Obj>::find(const Obj& x) const {
       AvlNode<Obj>* t = root;
       while( t != NULL  && t->key != x )
              t =( x < t->key ) ? t->left : t->right;
       return t;
}
template <class Obj>
AvlNode<Obj>* AvlTree<Obj>::findMin() const {
      AvlNode<Obj>* t = root;
      if( t != NULL )
            while( t->left != NULL ) t = t->left;
      return t;
}
template <class Obj>
AvlNode<Obj>* AvlTree<Obj>::findMax() const {
      AvlNode<Obj>* t = root;
      if( t != NULL )
            while( t->right != NULL ) t = t->right;
      return t;
}

template <class Obj>
void AvlTree<Obj>::rotateLeft(AvlNode<Obj>* & k1) {
        AvlNode<Obj>* k2 = k1->right;
        k1->right = k2->left;       //  attach b to k1
        k2->left = k1;          //  k1 becomes the left child of k2
        k1->height = max(height(k1->left), height(k1->right)) + 1;
        k2->height = max(k1->height, height(k2->right)) + 1;     
        k1 = k2;                //  the root of the subtree is now k2
}

template <class Obj>
void AvlTree<Obj>::rotateRight(AvlNode<Obj>* & k2) {
        AvlNode<Obj>* k1 = k2->left;
        k2->left = k1->right;       //  attach b to k2
        k1->right = k2;             //  k2 becomes the right child of k1
        k2->height = max(height(k2->left), height(k2->right)) + 1;
        k1->height = max(height(k1->left), k2->height) + 1;     
        k2 = k1;                //  the root of the subtree is now k1
}

template <class Obj>
void AvlTree<Obj>::rotateLeftRight(AvlNode<Obj>* & k3) {
        AvlNode<Obj>* k1 = k3->left;            // { rotateLeft(k3->left);
        AvlNode<Obj>* k2 = k1->right;           //     rotateRight(k3); }
        k1->right = k2->left;     k3->left = k2->right;     //   attach b to k1 and g to k3
        k2->left = k1;                 k2->right = k3;        //  k1 and k3 become children of k2
        k1->height = max(height(k1->left) , height(k1->right)) + 1;
        k3->height = max(height(k3->left) , height(k3->right)) + 1;
        k2->height = max(k1->height , k3->height) + 1;
        k3 = k2;                      //  the root of the subtree is now k2
}

template <class Obj>
void AvlTree<Obj>::rotateRightLeft(AvlNode<Obj>* & k1) {
        AvlNode<Obj>* k3 = k1->right;           // { rotateRight(k1->right);
        AvlNode<Obj>* k2 = k3->left;            //     rotateLeft(k1); }
        k1->right = k2->left;     k3->left = k2->right;     //   attach b to k1 and g to k3
        k2->left = k1;                 k2->right = k3;        //  k1 and k3 become children of k2
        k1->height = max(height(k1->left) , height(k1->right)) + 1;
        k3->height = max(height(k3->left) , height(k3->right)) + 1;
        k2->height = max(k1->height , k3->height) + 1;
        k1 = k2;                      //  the root of the subtree is now k2
}

template <class Obj>
void AvlTree<Obj>::insert(const Obj& x, AvlNode<Obj>* & t) {
    if( t == NULL ) t = new AvlNode<Obj>(x);
    else
        if( x < t->key ) {
            insert(x, t->left);
            if( height(t->left) - height(t->right) == 2 )
                if( x < t->left->key ) rotateRight(t);
                else  rotateLeftRight(t);
            else  t->height = max(height(t->left) , height(t->right)) + 1;
        }
        else if( t->key < x ) {
            insert(x, t->right);
            if( height(t->right) - height(t->left) == 2 )
                if( t->right->key < x ) rotateLeft(t);
                else  rotateRightLeft(t);
            else  t->height = max(height(t->left) , height(t->right)) + 1;
        }
        else;    //  duplicate key: nothing to be done !
}

template <class Obj>
AvlTree<Obj>& AvlTree<Obj>::remove(const Obj& x) {
       AvlNode<Obj> *t, *p, *node;
       t = root;  p = NULL;
       stack<AvlNode<Obj> *>  s;    //  stack storing the path to the node to be removed
       while( t != NULL  && t->key != x ) {
             s.push(p=t);
             t =(< t->key) ? t->left : t->right;
      }
       if( t == NULL ) return *this;        //  key not found: nothing to be done !
       if( t->left == NULL  ||  t->right == NULL )  //  node t has at most one child
             if( p != NULL )
                   if( p->left == t )
                          p->left =(t->left != NULL)  ? t->left : t->right;
                   else p->right =(t->left != NULL) ? t->left : t->right;
             else  root =(t->left != NULL) ? t->left : t->right;
       else {                  //  node t has two children
             s.push(node=p=t);     t = t->right;
             while( t->left != NULL ) { s.push(p=t);   t = t->left; }
             node->key = t->key;
             if( p->left == t )  p->left = t->right;
             else p->right = t->right;
      }
      delete t;
     while( !s.empty() ) {
           p = s.top(); s.pop();
           int  dH = height(p->left) - height(p->right);
           if( dH == 2 ) {      //  the subtree rooted by p needs be rebalanced
                 if ( height(p->left->left) >= height(p->left->right) ) rotateRight(p);
                 else  rotateLeftRight(p);
          }
           else if( dH == -2 ) {         //  the subtree rooted by p needs be rebalanced
                        if( height(p->right->right) >= height(p->right->left) ) rotateLeft(p);
                        else rotateRightLeft(p);
                 }
                  else  if ( p->height ==(dH = max(height(p->left) , height(p->right))+1) ) break;
            //  if the subtree rooted by p preserved its height unchanged,
              else { p->height = dH;    continue;  } //  … no need of more rebalancing
           if ( !s.empty() ) {     //  when rotations are applied, the subtree changes its root:
                   t = p;   p = s.top(); //  it becomes the left/right child of the node on top of stack
                   if ( t->key < p->key ) p->left = t;
                   else  p->right = t;
          }
           else { root = p;   break; }    //  in this case, the new subtree root is the new tree root
    }
     return *this;
}
=====================================================
End of File AvlTree.cc
=====================================================

=====================================================
File Application.cc :
=====================================================
#include "AvlTree.h"

int main()
{
    AvlTree<int> *test_tree1 = new AvlTree<int>();
    test_tree1->insert(5).insert(1).insert(3).insert(4).insert(12).insert(1).insert(8).insert(4).insert(2).insert(88).insert(-60).insert(0).insert(91).insert(9999).insert(939).insert(996);
    test_tree1->remove(3).remove(10);

    test_tree1->printTree();
   
    delete test_tree1;
   
    std::cin.ignore(); //Wait Statement: needed if the executable is not opened from command window
    return 0;
}
=====================================================
End of File Application.cc
=====================================================
set "curpath=%cd%"
cd %curpath%
g++ Application.cc
a.exe
Pause

No comments: