Programming - C Advanced Trees

    In this Post we will take a look at more Advanced Tree Structures. We already talked about an basic Binary Tree using C Language here. Today, we will expand that Code to create an AVL Tree and we will also take a look at how an Red-Black and 2-3 Tree works. We use all of them to prevent having an unbalanced tree that has a bad average access time. So, without further do, let's get started!

Quick Recap:

    In our Binary Tree Post we defined our Tree as a struct that contains Data and two pointers to the left and right Item, like this:

typedef struct TNode{
    //DATA
    struct TNode *left;
    struct TNode *right;
}TNode;

    

    The AVL Trees will use the exact same schema, cause they are Binary Trees that have some kind of sorting that self-balances the Tree, so that the average access time is minimum.


Our new TreeNode used in AVL Trees we will use the same basic Code:

TNode *nn;
nn = (TNode*)malloc(sizeof(TNode));
// for every Data Variable we do
nn->val = val;
// we set the pointers to NULL
nn->left = NULL;
nn->right = NULL;


And we will search, print and find the successor in the same exact way we did in an Basic Binary Tree like this:

TNode* search(TNode *root, int val){
 // if empty or found at root
 if(root == NULL || root->val == val){
     // return root
     return root;
 }
 // if smaller
 else if(val < root->val){
     // call function again for left side
     return search(root->left, val);
 }
 // if greater
 else if(val > root->val){
     // call function again for right side
     return search(root->right, val);
 }
}


void preorder(TNode *root){
     if(root == NULL) return;
     printf("%d ", root->val);
     if(root->left != NULL)inorder(root->left);
     if(root->right != NULL)inorder(root->right);
}


void inorder(TNode *root){
     if(root == NULL) return;
     if(root->left != NULL)inorder(root->left);
     printf("%d ", root->val);
     if(root->right != NULL)inorder(root->right);
}


void postorder(TNode *root){
     if(root == NULL) return;
     if(root->left != NULL)inorder(root->left);
     if(root->right != NULL)inorder(root->right);
     printf("%d ", root->val);
}


TNode* successor(TNode *node){
 TNode *cur;
 // set cur to point to our node
 cur = node;
 // find the most left child
 while(cur->left != NULL){
     // set cur to left pointer
     cur = cur->left;
 }
 // it returns the most left child
 return cur;
}

 

   Things will change in the process of Insertion and Deletion, cause we will have to make sure that some Conditions are met and if they don't we will have to "fix" our Tree using some Rotation functions! 

AVL Trees:

    An AVL Tree is an self-balancing binary search Tree, where the heights of the 2 sub Trees of any Node differ by at most one. This way our Tree will never become an Left or Right-Only Child Tree, but the Tree will use Rotation functions that will bring the Tree back in balance if it is not. So, our Tree Node struct will now contain also a height variable to make things easier. 

The Code looks like this:

typedef struct TNode{
 int val;
 int height;
 struct TNode *left;
 struct TNode *right;
}TNode;

    We will use an function that returns the height of an TNode or 0 if it doesn't exist so that we can find the maximum height (using an max function) of the 2 childs of a specific Node. Afterwards, using an balance function that calculates the difference we can check if our Tree is out of balance.

The Code looks like this:

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


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


int getBalance(TNode *N){
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}


    To insert a new Node or delete an existing on in the Tree we do it the same way we did in normal Binary Trees and afterwards we check if our Tree lost it's balance. Then we would have to re-balance it using Rotations. 

There are 4 Rotation Cases that can happen. Those are (and can be solved using):

  • Left-Left Case (right rotation)
  • Left-Right Case (left and then right rotation)
  • Right-Right Case (left rotation)
  • Right-Left Case (right and then left rotation)

So, we have to write a Code that rotates a Node right and one that rotates a Node left.

TNode *rightRotate(TNode *y){
    TNode *x = y->left;
    TNode *z = x->right;
    // Perform rotation
    x->right = y;
    y->left = z;
    // 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;
}


TNode *leftRotate(TNode *x){
    TNode *y = x->right;
    TNode *z = y->left;
    // Perform rotation
    y->left = x;
    x->right = z;
    //  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;
}


So, our Insertion and Deletion Functions now look like this:

TNode* insert(TNode *node, int val){
 // normal BST insertion
 TNode *nn;
 nn = (TNode*)malloc(sizeof(TNode));
 // for every Data Variable we do
 nn->val = val;
 // height of nn is initialized as 1
 nn->height = 1;
 // we set the pointers to NULL
 nn->left = NULL;
 nn->right = NULL;
 // check if tree is empty
 if(node == NULL){
     // return nn as our new node or
     // because of recursion it will set
     // the nn were it belongs in the tree
     return nn;
 }
 if(val < node->val){
     // call function again for left side
     node->left = insert(node->left, val);
 }
 else if(val > node->val){
     // call function again for right side
     node->right = insert(node->right, val);
 }
 else{ // equal (don't insert)
     return node;     
 }
 // update height
 node->height = 1 + max(height(node->left),
                           height(node->right));
    // get the balance factor    
 int balance = getBalance(node);
  // Left Left Case
    if (balance > 1 && val < node->left->val)
        return rightRotate(node);
    // Right Right Case
    if (balance < -1 && val > node->right->val)
        return leftRotate(node);
    // Left Right Case
    if (balance > 1 && val > node->left->val){
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }
    // Right Left Case
    if (balance < -1 && val < node->right->val){
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    // return unchanged
    return node; 
}


TNode* delete(TNode *node, int val){
 // standard BST deletion
 // check if tree is empty
 if(node == NULL){
     printf("Not found!\n");
     return node;
 }
 if(val < node->val){
     // call function again for left side
     node->left = delete(node->left, val);
 }
 else if(val > node->val){
     // call function again for right side
     node->right = delete(node->right, val);
 }
 else{ // when val was found (cases)
     // has left and right child
     if(node->left != NULL && node->right != NULL){
         // find successor
         TNode *s = successor(node->right);
         // set value of Node to be deleted to successor's value
         node->val = s->val;
         // delete successor
         node->right = delete(node->right, s->val);
     }
     // has only left child
     else if(node->left != NULL){
         // set node to it's child
         node = node->left;
     }
     // has only right child
     else if(node->right != NULL){
         // set node to it's child
         node = node->right;
     }
     // has no child
     else{
         // simply set node to be deleted to NULL
         node = NULL;
     }
 }   
 // if empty simply return
 if (node == NULL)
     return node;
 // update height
 node->height = 1 + max(height(node->left),
                           height(node->right));
    // get the balance factor    
 int balance = getBalance(node);
  // Left Left Case
    if (balance > 1 && val < node->left->val)
        return rightRotate(node);
    // Right Right Case
    if (balance < -1 && val > node->right->val)
        return leftRotate(node);
    // Left Right Case
    if (balance > 1 && val > node->left->val){
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }
    // Right Left Case
    if (balance < -1 && val < node->right->val){
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    // return unchanged
    return node; 
}


Red-Black Trees:

    Red-Black Trees use a similar concept. When inserting and deleting frequently the rotations in AVL Trees cost time and that is when Red-Black Trees become useful. Some Basic Conditions are that:

  • Every Node is Red or Black colored (variable color)
  • The Root is Black always
  • There can't be to Adjacent Red Nodes (Red Node can't have Red Parent or Child)
  • Every path from the root to a NULL node must have the same number of black nodes. 

Using this concept the Tree remains balanced, because of the recoloring and the rotation of the Nodes.

    Now, let's take a look at the recoloring and rotation process. When inserting or deleting we do it the exact same way we did in normal binary Trees and afterwards we will first try to recolor our Nodes and if it doesn't solve the problem we afterwards rotate (that's why we save rotations). The new Node inserted is always Red and the algorithms depend upon the color of the uncle of this newly inserted Node. If the uncle is red we do recoloring and if the uncle is black we do rotations and/or recoloring. 

So, we have this Cases:

  • If the newly inserted Node is the root (first Node inserted) we change it's color to black
  • If parent and uncle are Red we change the color of parent and uncle to black, color of grandparent to red and continue on by setting the grandparent's  grandparent to red and his grandparent to red and so on..
  • If parent is red and uncle black we we do the same 4 Cases of AVL Trees (RR, RL, LR, LL)

The first 2 do recoloring and the last one is for rotations. So, the rotations are the exact same we had in AVL Trees, but we also have colors and have to check the Colors, cause they could prevent rotations and we would only need recoloring.

    Writing this Code in C is pretty difficult, cause it will contain parent Nodes and stuff, so it is preferable to write it in an Object-Oriented Language like C++, C# or even Java. We also only talked about inserting, removing, rotating, recoloring and all that stuff directly with pseudocode on a Tree graphically in my University. We don't did any specific language implementation. I searched a little bit and I found this website that explains red-black trees pretty well in C++. If you are interested take a look.


2-3 Trees:

    A 2-3 Tree is a Tree where each Node has 2 children and one data element (2-Node) or 3 children and two data elements (3-Node). So, we now don't have left and right only, but also a center child sometimes. This Trees are also balanced cause the left, center and right subtree contain close to the same amount of data.

A 2-3 Tree has this Properties:

  • Every Node is a 2-Node or 3-Node
  • All leaves are at the same level
  • All data is kept in sorted order

    We don't did any Language Implementation in our University. But, we learned how to do function like insert, delete, search on an 2-3 Tree using pseudocode and doing those functions by hand on a Tree graphically (the same way we did it in Red-Black Trees). It again is much easier to create such Code in an language that is Object-Oriented like C++. I Found a pdf Online that explains it using pseudocode. You can use this pseudocode to implement it in any language you like. Here the link.

    

    This was the end of today's Post. I only wanted to explain the AVL Trees using C Code, cause they are also much easier then the other 2. We only had to expand our Code a little to set it up for AVL Trees and I think it's preferable to use an AVL Tree instead of an normal BST, to keep the Tree balanced and the access time fast. I wanted to explain the concept of the other 2, cause it is interesting to know that there are such things and if someone wants to implement something difficult in a specific language for practice an Red-Black or 2-3 Tree is something worth looking for.

Hope you enjoyed it! 

Thanks :)

H2
H3
H4
3 columns
2 columns
1 column
Join the conversation now