Question

IN C++:

Create sets of 1 Million integer, where no integer is repeated. Insert these numbers to an

(i) AVL tree and

(ii) R-B tree. Compute the time taken to insert all the numbers.

Repeat the experiment 10 times, each time regenerating the set. In a table report

(a) the time taken to complete the insertion

(b) the height of the tree, (c) the black height of the R-B Tree

Answer 1

#include <bits/stdc++.h>
#include<iostream>

#include<cstdlib.h>
using namespace std;

enum Color {RED, BLACK};

struct RedBlackTreeNode
{
   int data;
   bool color;
   RedBlackTreeNode *left, *right, *parent;

   // Constructor
   RedBlackTreeNode(int data)
   {
   this->data = data;
   left = right = parent = NULL;
   this->color = RED;
   }
};

// Class to represent Red-Black Tree
class RBTree
{
private:
   RedBlackTreeNode *root;
protected:
   void rotateLeft(RedBlackTreeNode *&, RedBlackTreeNode *&);
   void rotateRight(RedBlackTreeNode *&, RedBlackTreeNode *&);
   void fixViolation(RedBlackTreeNode *&, RedBlackTreeNode *&);
public:
   // Constructor
   RBTree() { root = NULL; }
   void insert(int n);
   void inorder();
   void levelOrder();
};

// A recursive function to do level order traversal
void inorderHelper(RedBlackTreeNode *root)
{
   if (root == NULL)
       return;

   inorderHelper(root->left);
   cout << root->data << " ";
   inorderHelper(root->right);
}

RedBlackTreeNode* BSTInsert(RedBlackTreeNode* root, RedBlackTreeNode *pt)
{
   /* If the tree is empty, return a new RedBlackTreeNode */
   if (root == NULL)
   return pt;

   /* Otherwise, recur down the tree */
   if (pt->data < root->data)
   {
       root->left = BSTInsert(root->left, pt);
       root->left->parent = root;
   }
   else if (pt->data > root->data)
   {
       root->right = BSTInsert(root->right, pt);
       root->right->parent = root;
   }

   /* return the (unchanged) RedBlackTreeNode pointer */
   return root;
}

// Utility function to do level order traversal
void levelOrderHelper(RedBlackTreeNode *root)
{
   if (root == NULL)
       return;

   std::queue<RedBlackTreeNode *> q;
   q.push(root);

   while (!q.empty())
   {
       RedBlackTreeNode *temp = q.front();
       cout << temp->data << " ";
       q.pop();

       if (temp->left != NULL)
           q.push(temp->left);

       if (temp->right != NULL)
           q.push(temp->right);
   }
}

void RBTree::rotateLeft(RedBlackTreeNode *&root, RedBlackTreeNode *&pt)
{
   RedBlackTreeNode *pt_right = pt->right;

   pt->right = pt_right->left;

   if (pt->right != NULL)
       pt->right->parent = pt;

   pt_right->parent = pt->parent;

   if (pt->parent == NULL)
       root = pt_right;

   else if (pt == pt->parent->left)
       pt->parent->left = pt_right;

   else
       pt->parent->right = pt_right;

   pt_right->left = pt;
   pt->parent = pt_right;
}

void RBTree::rotateRight(RedBlackTreeNode *&root, RedBlackTreeNode *&pt)
{
   RedBlackTreeNode *pt_left = pt->left;

   pt->left = pt_left->right;

   if (pt->left != NULL)
       pt->left->parent = pt;

   pt_left->parent = pt->parent;

   if (pt->parent == NULL)
       root = pt_left;

   else if (pt == pt->parent->left)
       pt->parent->left = pt_left;

   else
       pt->parent->right = pt_left;

   pt_left->right = pt;
   pt->parent = pt_left;
}

// This function fixes violations caused by BST insertion
void RBTree::fixViolation(RedBlackTreeNode *&root, RedBlackTreeNode *&pt)
{
   RedBlackTreeNode *parent_pt = NULL;
   RedBlackTreeNode *grand_parent_pt = NULL;

   while ((pt != root) && (pt->color != BLACK) &&
       (pt->parent->color == RED))
   {

       parent_pt = pt->parent;
       grand_parent_pt = pt->parent->parent;

       /* Case : A
           Parent of pt is left child of Grand-parent of pt */
       if (parent_pt == grand_parent_pt->left)
       {

           RedBlackTreeNode *uncle_pt = grand_parent_pt->right;

           /* Case : 1
           The uncle of pt is also red
           Only Recoloring required */
           if (uncle_pt != NULL && uncle_pt->color == RED)
           {
               grand_parent_pt->color = RED;
               parent_pt->color = BLACK;
               uncle_pt->color = BLACK;
               pt = grand_parent_pt;
           }

           else
           {
               /* Case : 2
               pt is right child of its parent
               Left-rotation required */
               if (pt == parent_pt->right)
               {
                   rotateLeft(root, parent_pt);
                   pt = parent_pt;
                   parent_pt = pt->parent;
               }

               /* Case : 3
               pt is left child of its parent
               Right-rotation required */
               rotateRight(root, grand_parent_pt);
               swap(parent_pt->color, grand_parent_pt->color);
               pt = parent_pt;
           }
       }

       /* Case : B
       Parent of pt is right child of Grand-parent of pt */
       else
       {
           RedBlackTreeNode *uncle_pt = grand_parent_pt->left;

           /* Case : 1
               The uncle of pt is also red
               Only Recoloring required */
           if ((uncle_pt != NULL) && (uncle_pt->color == RED))
           {
               grand_parent_pt->color = RED;
               parent_pt->color = BLACK;
               uncle_pt->color = BLACK;
               pt = grand_parent_pt;
           }
           else
           {
               /* Case : 2
               pt is left child of its parent
               Right-rotation required */
               if (pt == parent_pt->left)
               {
                   rotateRight(root, parent_pt);
                   pt = parent_pt;
                   parent_pt = pt->parent;
               }

               /* Case : 3
               pt is right child of its parent
               Left-rotation required */
               rotateLeft(root, grand_parent_pt);
               swap(parent_pt->color, grand_parent_pt->color);
               pt = parent_pt;
           }
       }
   }

   root->color = BLACK;
}

// Function to insert a new RedBlackTreeNode with given data
void RBTree::insert(int data)
{
   RedBlackTreeNode *pt = new RedBlackTreeNode(data);

   // Do a normal BST insert
   root = BSTInsert(root, pt);

   // fix Red Black Tree violations
   fixViolation(root, pt);
}

// Function to do inorder and level order traversals
void RBTree::inorder()   { inorderHelper(root);}
void RBTree::levelOrder() { levelOrderHelper(root); }

// An AVL tree AvlTreeNode
class AvlTreeNode
{
   public:
   int key;
   AvlTreeNode *left;
   AvlTreeNode *right;
   int height;
};

int max(int a, int b);

int height(AvlTreeNode *N)
{
   if (N == NULL)
       return 0;
   return N->height;
}

int max(int a, int b)
{
   return (a > b)? a : b;
}

AvlTreeNode* newAvlTreeNode(int key)
{
   AvlTreeNode* TreeNode = new AvlTreeNode();
   TreeNode->key = key;
   TreeNode->left = NULL;
   TreeNode->right = NULL;
   TreeNode->height = 1;
   return(TreeNode);
}

// A utility function to right
// rotate subtree rooted with y
// See the diagram given above.
AvlTreeNode *rightRotate(AvlTreeNode *y)
{
   AvlTreeNode *x = y->left;
   AvlTreeNode *T2 = x->right;

   // Perform rotation
   x->right = y;
   y->left = T2;

   // Update heights
   y->height = max(height(y->left),
                   height(y->right)) + 1;
   x->height = max(height(x->left),
                   height(x->right)) + 1;

   // Return new root
   return x;
}

// A utility function to left
// rotate subtree rooted with x
// See the diagram given above.
AvlTreeNode *leftRotate(AvlTreeNode *x)
{
   AvlTreeNode *y = x->right;
   AvlTreeNode *T2 = y->left;

   // Perform rotation
   y->left = x;
   x->right = T2;

   // Update heights
   x->height = max(height(x->left),
                   height(x->right)) + 1;
   y->height = max(height(y->left),
                   height(y->right)) + 1;

   // Return new root
   return y;
}

// Get Balance factor of AvlTreeNode N
int getBalance(AvlTreeNode *N)
{
   if (N == NULL)
       return 0;
   return height(N->left) - height(N->right);
}

// Recursive function to insert a key
// in the subtree rooted with AvlTreeNode and
// returns the new root of the subtree.
AvlTreeNode* insert(AvlTreeNode* AvlTreeNode, int key)
{
   /* 1. Perform the normal BST insertion */
   if (AvlTreeNode == NULL)
       return(newAvlTreeNode(key));

   if (key < AvlTreeNode->key)
       AvlTreeNode->left = insert(AvlTreeNode->left, key);
   else if (key > AvlTreeNode->key)
       AvlTreeNode->right = insert(AvlTreeNode->right, key);
   else // Equal keys are not allowed in BST
       return AvlTreeNode;

   /* 2. Update height of this ancestor AvlTreeNode */
   AvlTreeNode->height = 1 + max(height(AvlTreeNode->left),
                       height(AvlTreeNode->right));

   /* 3. Get the balance factor of this ancestor
       AvlTreeNode to check whether this AvlTreeNode became
       unbalanced */
   int balance = getBalance(AvlTreeNode);

   // If this AvlTreeNode becomes unbalanced, then
   // there are 4 cases

   // Left Left Case
   if (balance > 1 && key < AvlTreeNode->left->key)
       return rightRotate(AvlTreeNode);

   // Right Right Case
   if (balance < -1 && key > AvlTreeNode->right->key)
       return leftRotate(AvlTreeNode);

   // Left Right Case
   if (balance > 1 && key > AvlTreeNode->left->key)
   {
       AvlTreeNode->left = leftRotate(AvlTreeNode->left);
       return rightRotate(AvlTreeNode);
   }

   // Right Left Case
   if (balance < -1 && key < AvlTreeNode->right->key)
   {
       AvlTreeNode->right = rightRotate(AvlTreeNode->right);
       return leftRotate(AvlTreeNode);
   }

   /* return the (unchanged) AvlTreeNode pointer */
   return AvlTreeNode;
}
void preOrder(AvlTreeNode *root)
{
   if(root != NULL)
   {
       cout << root->key << " ";
       preOrder(root->left);
       preOrder(root->right);
   }
}

int main()
{
   RBTree tree;
   AvlTreeNode *root = NULL;
   time_t start,stop;
   double time_taken;
   int arr[10000];
   for(int i=0;i<10000;i++)
       arr[i] = rand()%10000;
    time(&start);

    for(int i=0;i<10000;i++)
       tree.insert(arr[i]);

    // Get ending timepoint
    time(&stop);
    time_taken = double(stop - start);
    cout << "Time taken for inserting in AVL-Tree is : " <<time_taken << setprecision(5);
    cout << " sec " << endl;
    // Get starting timepoint
    time(&start);

    for(int i=0;i<10000;i++)
       root = insert(root,arr[i]);

    // Get ending timepoint
    time(&stop);
    time_taken = double(stop - start);
    cout << "Time taken for inserting in AVL-Tree is : " <<time_taken << setprecision(5);
    cout << " sec " << endl;
    cout<<"Hello";

   return 0;
}

/*Please rate the solution: compile it using c++11*/