Question

1) Please find and share one sorting/searching algorithm. Explain it, and discuss its efficiency

2) Please find and share algorithm about red/black trees. Explain it, give 2 real world usages and discuss its efficiency

3) Please find and share one algorithm about Binary Search Trees. Explain it, and discuss it's efficiency

Answer 1

1. Quick Sort Algorithm:

Quick Sort is one of the best sorting sorting algorithms and is a Divide and Conquer algorithm.

Time Complexity:

The time complexity of Quick Sort is O(n log n) in best case,

O(n log n) in average case and

O(n^2) in the worst case.

It has the best performance in average case mostly and thus it is considered as the fastest algorithm.

In Quick Sort, an element is picked as a pivot the array is partitioned around the given pivot. Pivot selection can be done in many ways:

1. First element as pivot.

2. Last element as pivot.

3. Random element as pivot.

4. Median as pivot.

Suppose we have a given array to sort: {10, 20, 90, 45, 65, 30}

Next comes choosing the pivot point. We have to arrange the array such that all the elements smaller than the pivot are to it’s left and the elements larger than it are to it’s left. We can choose the pivot from any of the choices mentioned above.

For this eg. Let’s choose the last element as pivot i.e 30.

Partition Algorithm (pseudo code):

quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is now
           at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

Pseudo code for partition():

partition (arr[], low, high)
{
    // pivot (Element to be placed at right position)
    pivot = arr[high];  
 
    i = (low - 1)  // Index of smaller element

    for (j = low; j <= high- 1; j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++;    // increment index of smaller element
            swap arr[i] and arr[j]
        }
    }
    swap arr[i + 1] and arr[high])
    return (i + 1)
}

2. Red/Black Tree Algorithm:

A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either red or black. By constraining the way nodes can be colored on any path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.

Every Red/Black Tree satisfies the following properties:

1. Each node is either red or black.

2. Every leaf (NIL) is black.

3. If a node is red then both it’s children are black.

4. Every simple path from node to descendant NULL has the same number of black nodes.

Each node of the tree contain the fields: color, key, left, right, and parent. A red-black tree's node structure would be:

struct RedBlackNode
{ 
int key; 
enum { red, black } color; 
RedBlackNOde *left, *right, *parent; 
};

If a child or the parent of a node does not exist, the corresponding pointer field of the node contains the value NULL. We shall regard these NULL’s as being pointers to external nodes (leaves) of the binary tree.

A red-black tree with n internal nodes has height at most 21g(n + 1).

Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(logn) after every insertion and deletion, then we can guarantee an upper bound of O(logn) for all these operations. The height of a Red-Black tree is always O(logn) where n is the number of nodes in the tree.

Operations on Red/Black Tree:

1.Rotation: A rotation is a local operation in a search tree that preserves in-order traversal key ordering. We change the pointer structure trough rotation, which is a local operation in a search tree that preserves the binary-search-tree property.

Pseudo-code:

left_rotate(T, x) 
y ← x->right x->right← y->left 
y->left->p ← x 
y->p ← x->p 
if      x->p = Null 
then    T->root ← y 
else if x = x->p->left 
then x->p->left ← y 
else x->p->right ← y 
y->left ← x 
x->p ← y

right-rotate(T, x) 
y ← x->left x->left← y->right 
y->right->p ← x 
y->p ← x->p 
If       x->p = Null 
then T->root ← y 
else if  x = x->p->right 
then     x->p->right ← y 
else             x->p->left ← y 
y->right ← x 
x->p ← y

2. Insertion: Insertion begins by adding the node much as binary search tree insertion does and by coloring it red. Whereas in the binary search tree, we always add a leaf, in the red-black tree leaves contain no information, so instead we add a red interior node, with two black leaves, in place of an existing black leaf.

Pseudo Code:

RB-INSERT(T, z)
y ← null 
x ← T->root 
while x ≠ null 
do y ← x 
if z->key < x->key 
then x ← x->left 
else x ← x->right 
z->p ← y 
if y = null 
then T->root ← z 
else if z->key < y->key 
then y->left ← z 
else y->right ← z 
z->left ← null 
z->right ← null 
z->color ← RED 
RB-INSERT-FIXUP(T, z)

Real World Usages of Red/Black Trees:

1. The process scheduler in Linux uses Red Black Trees. The red black trees are a replacement for run queues which had priorities for processes on the queue for the scheduler to pick up from. The Completely Fair Scheduler (CFS) is the name of a process scheduler which was merged into the 2.6.23 release of the Linux kernel. It handles CPU resource allocation for executing processes, and aims to maximize overall CPU utilization while also maximizing interactive performance.

2. They are also used in map, multimap, multiset from C++ STL and java.util.TreeMap , java.util.TreeSet from Java. Besides they are use in K-mean clustering algorithm for reducing time complexity.

3. Binary search Tree: A binary search tree is a tree that can be represented by a linked data structure in which each node is an object. In addition to a key field, each node contains fields left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively. If a child or the parent is missing, the appropriate field contains the value NIL. The root node is the only node in the tree whose parent field is NIL.

The keys in a binary search tree are always stored in such a way as to satisfy the binary-search-tree property:

Let x be a node in a binary search tree. If y is a node in the left subtree of x, then key[y] key[x]. If y is a node in the right subtree of x, then key[x] key[y].

Basic Properties of BST:

1. Search: searches an elemtn in tree.

2. Insert: Inserts element in tree.

3. Pre-order Traversal: Traverses a tree in a pre-order manner.

4. In-order Traversal: Traverses a tree in an in-order manner.

5. Post-order Traversal: Traverses a tree in a post-order manner.

Node Declaration:

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

Search Operation Algorithm:

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
        
   while(current->data != data){
        
      if(current != NULL) {
         printf("%d ",current->data);
                        
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }  //else go to right tree
         else {                
            current = current->rightChild;
         }
                        
         //not found
         if(current == NULL){
            return NULL;
         }
      }                 
   }
   
   return current;
}

Insert Operation Algorithm:

void insert(int data) {
   struct node *temp = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   temp->data = data;
   temp->leftChild = NULL;
   temp->rightChild = NULL;

   if(root == NULL) {
      root = temp;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
                        
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
                                
            if(current == NULL) {
               parent->leftChild = temp;
               return;
            }
         } 
         else {
            current = current->rightChild;
            
            if(current == NULL) {
               parent->rightChild = temp;
               return;
            }
         }
      }            
   }
}

Efficiency: The recursive structure of a BST yields a recursive algorithm. Searching in a BST has O(h) worst-case runtime complexity, where h is the height of the tree. Since s binary search tree with n nodes has a minimum of O(log n) levels, it takes at least O(log n) comparisons to find a particular node.