## 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