Monday, 25 March 2013

Algorithm of Sorted Array to Red-Black Tree: A deeper look

Introduction:


For those who have seen my earlier post on: http://physicsmathscomputers.blogspot.com/2012/10/sorted-array-to-red-black-tree.html , you must have seen that the algorithm that puts the elements of a sorted array into a red-black tree has not been explained. That is because, at that time I did not think about giving a deeper explanation in that article. Now I realized the importance of giving an explanation of that algorithm. This post will concentrate on that explanation.


Explanation of the code that converts the sorted array to a red-black tree:

(Note: Those who are familiar with Java programming language will find it easier to study the code.)

Vision:


Suppose here is our sorted array of integers:
{ -77 , -54 , -43 , -11 , -3 , 0 , 13 , 49 , 235 }
This array has 9 elements. The middle element is element at 5th position. The value of 5th element is -3. Let us mark it out. Like this:
{ -77 , -54 , -43 , -11 , -3 , 0 , 13 , 49 , 235 }
Now the number marked in green, is the root element of the red-black tree. The sub-array marked in yellow will used for forming the left sub-tree. The sub-array marked in blue will be used for forming right sub-tree.


-3
(middle element)

-77 , -54 , -43 , -11
(left sub-tree)

0 , 13 , 49 , 235
(right sub-tree)

Let us look at the left sub-tree: -77 , -54 , -43 , -11
There are 4 elements in this array. There are 2 elements in the middle. Those 2 elements are: -54 , -43
In the algorithm used in the link given above, the middle element chosen here would be: -54 . Like this:
 -77 , -54 , -43 , -11

-3

-54
-77
-43 , -11

0 , 13 , 49 , 235

Using the similar operation on right sub-tree {-43 , -11}, we set -11 as right child-node of -54 . Like this:

-3

-54
-77

-43


-11

0 , 13 , 49 , 235

When the right sub-tree goes through similar operation, the tree looks like this:

-3

-54
-77

-43


-11


13
0

49


235


A better view of the above tree will be:




-3





-54




13


-77

-43


0

49




11




235
The nodes of the will connect as shown below:


Code (in Java):

The code in Java has been implemented with the help of recursion. But before giving the code, I must explain what is going to happen in that code with this input.

If there are 9 elements in an array, then their indices are between 0 to 8 in java. That is:
The 1st element in array is 0(zero)th element in java array,
The 2nd element in array is 1st element in java array,
The 3rd element in array is 2nd element in java array,
and so on.

The middle element between 1st and 9th is 5th element. The middle element between 0-th and 8th element is 4th element. This is how we get it: (1+9) / 2 is 5 , (0+8) / 2 is 4.
But (0+3) / 2 is 1½, and there is no 1½th element in any array. There is a 1st element and a 2nd element, but no 1½th element.
The answer to this problem lies in the way integer division is handled in Java. In Java, when division between 2 integers is a fraction, then the result is only the quotient of the division. For example: (a) if 3/2 is 1.5, then in Java the resultant integer is 1 , (b) if 10/3 is 3.33... then the resultant integer is the quotient 3.
Hence (0+3)/2 is 1 in Java. So the middle element between 0th and 3rd element is 1st element. Consequently, the 0th element is root of the left-subtree (and hence the left child) of the 1st element, and the 2nd & 3rd element are going to be the elements of the right-subtree. And now the root of the right-subtree is the 2nd element [because: (2+3)/2=5/2=2.5, and highest integer less than 2.5 is 2. i.e. the quotient of 5/2 is 2].

(Note: There is a normal practice that attributes of a class are private & accessed through getter and setter methods. But this code is written just for a cleaner explanation of concepts. Hence the attributes are public, and no getters & setters to take the focus away.)

/*
file: Node.java
*/
public class Node
{   public int key;
    public Node right,left;
    @Override
    public String toString()
    {   return "[ key: " + key + ", left: " + left + ", right: " + right + "]";
    }
}

/*
file: Tree.java
*/
public class Tree
{   public Node root;
    public Tree(int[]sortedArray)
    {   root = formLocalRoot(sortedArray,0,sortedArray.length-1);
    }
    public Node formLocalRoot(int[]array,int fromIndex,int toIndex)
    {   if(fromIndex>toIndex)
            return null;
        int middleIndex = (fromIndex+toIndex) / 2;
        Node localRoot = new Node();
        localRoot.key = array[middleIndex];
        localRoot.right = formLocalRoot(array,middleIndex+1,toIndex);
        localRoot.left = formLocalRoot(array,fromIndex,middleIndex-1);
        return localRoot;
    }
}

/*
file: TreeTest.java
*/
public class TreeTest
{   public static void main(String[]arguments)
    {   int[]intArray = new int[arguments.length];
        for(int index=0 ; index < intArray.length ; ++index)
           intArray[index] = Integer.parseInt(arguments[index]);
        IntegerArrays.bubbleSort(intArray);
        Tree tree = new Tree(intArray);
        System.out.println(tree.root);
    }
}

/*
file: IntegerArrays.java
*/
public class IntegerArrays
{   public static void bubbleSort(int a[])
    {   for(int i = 0; i < a.length ; ++i )
            for(int j = 1; j < (a.length-i) ; ++j )
                if(a[j-1] > a[j])
                    swap(a,j-1,j);
    }
    public static void swap(int[]a,int i,int j)
    {   int

        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
 



This is how we test / run it on the command line:
command_prompt> javac TreeTest.java
command_prompt> java TreeTest 13 -3 -77 49 -11 235 0 -54 -43


Appendix:

More conventional versions of files Node.java & Tree.java


/*
file: Node.java
*/
public class Node
{   private int key;
    private Node right,left;
    public Node(int key)
    {   this.key = key;
    }
    public Node(Node left, int key, Node right)
    {   this.left = left;
        this.key = key;
        this.right = right;
    }
    public int getKey()
    {   return key;
    }
    public Node getRight()
    {   return right;
    }
    public Node getLeft()
    {   return left;
    }
    public void setKey(int key)
    {   this.key = key;
    }
    public void setRight(Node right)
    {   this.right = right;
    }
    public void setLeft(Node left)
    {   this.left = left;
    }
    @Override
    public String toString()
    {   return "[ key: " + key + ", left: " + left + ", right: " + right + "]";
    }
}

/*
file: Tree.java
*/
public class Tree
{   public Node root;
    public Tree(int[]sortedArray)
    {   root = formLocalRoot(sortedArray,0,sortedArray.length-1);
    }
    public Node formLocalRoot(int[]array,int fromIndex,int toIndex)
    {   if(fromIndex>toIndex)
            return null;
        int middleIndex = (fromIndex+toIndex) / 2;
        return new Node(
                formLocalRoot(array,fromIndex,middleIndex-1),
                array[middleIndex],
                formLocalRoot(array,middleIndex+1,toIndex)
                );
    }
}



{Note: Often there is a debate whether there should be a setKey method or not. When the nodes need rotations, some people use mutable key. Otherwise key is always immutable. Even for nodes that need rotations, mutable key can be avoided by using an Entry<Key,Value> class. This program has no value object in Node class (only key object) since this blog-post is only for explaining concepts related to key of the node. But the blog post at http://physicsmathscomputers.blogspot.com/2012/10/sorted-array-to-red-black-tree.html has a Node with both key and value. I prefer using immutable key, and declare key as private final . I do this, as in my codes, a key is often tied to the hash-code. So if you prefer the same just remove the setKey method in the above code.}

[Any feedback/suggestion is welcome.]

Saturday, 13 October 2012

Sorted Array to Red-Black Tree

(Note: Red-Black Tree is a Balanced Binary Search Tree)

Your teachers must have told you this about searching in an array: If you have a sorted array, then one of the most efficient way to find position of any element in that array is binary search.

I say: Fine, then why not just convert that array to a Red-Black Tree ? I find Red-Black Tree as a better option, as in binary search, you have to calculate the midpoint in every iteration/recursive-call during search.

Before you see the code, I must add: if the size of your array is N, then this code will generate N number of objects of Node class. Add to that, in each of these objects there are going to be 4 variables of 32bits each [Or on a 64 bit machine: 2 variables of 32 bit (the 2 integers) & 2 variables of 64 bit (the 2 object references)].
/*
 * Programming language: Java
 */

class RedBlackTree
{
  static class Node
  {
    int key;
    int value;
    Node left;
    Node right;
    Node(int key,int value)
    {
      this.key = key;
      this.value = value;
    }
  }

  Node root;

  public RedBlackTree(int[]sorted_integers)
  {
    root = arrayToRedBlackTreeRoot(sorted_integers,0,sorted_integers.length-1);
  }

  static Node arrayToRedBlackTreeRoot(int[]integers,int i,int j)
  {
    if(i>j)
      return null;
    int x=(j+i)/2;
    Node local_root=new Node(integers[x],x);
    if(i<j)
    {
      local_root.left = arrayToRedBlackTreeRoot(integers,i,x-1);
      local_root.right = arrayToRedBlackTreeRoot(integers,x+1,j);
    }
    return local_root;
  }

}


The code written above, is only to get you started. An actual application where you may have to write a similar code can be different, and you have to adjust parts of this code to suit your requirement. Here is one such example:
There are 2 arrays. One array contains phone/mobile numbers, and the other array contains names of owners of each number. eg: if number[4]=9876543210 and name[4]="John Ray", then John Ray's number is 9876543210. You are asked to write a program that finds the name of the person when you have that person's number. For that first make following changes/additions in the above code:
  1. Change type of integers and sorted_array to long[]
  2. Change type of key to long
  3. Add a function named find in the class RedBlackTree
  4.   /*
       * Programming language: Java
       */
      public int find(long key)
      {
        Node node=root;
        while(node!=null)
        {
          if(node.key==key)
            return node.value;
          else if(node.key<key)
            node=node.right;
          else if(node.key>key)
            node=node.left;
        }
        return -1;
      }
    
  5. Write the folllowing in your main() function:
  /*
   * Programming Language: Java
   */
  long[]numbers=new long[10];
  String[]names=new String[10];
  // Home Work: Write code to initialize both arrays from any input.

  // bubble sort starts here: (you can choose your favourite algorithm)
  for(int i=0 ; i<numbers.length ; ++i)
    for(int j=1,n=numbers.length-i; j<n ; ++j )
      if(numbers[j-1]>numbers[j])
      {
        long temp_number=numbers[j-1];
        numbers[j-1]=numbers[j];
        numbers[j]=temp_number;
        String temp_name=names[j-1];
        names[j-1]=names[j];
        names[j]=temp_name;
      }
  RedBlackTree tree=new RedBlackTree(numbers);
  long number_x = 9876543210L;// Home Work: Read this number from input.
  int found=tree.find(number_x);
  System.out.println("The number: "+number_x+", belongs to "+(found==-1?"nobody":names[found]));
Though the above written code can work to give you a fair result, this may not be the most efficient way to write a program.
This is where the concept of MAP comes in. In C++, STL has map.h for it. In Java programming language an implementation of java.util.Map will do. But what change in above code will do it for us? The answer is: Instead of puting index of names in value, put the name itself as value. Thats it! So finally, we have a code that looks like this:
/**
 * Programming Language: Java
 * @author Abhishek
 */
class RedBlackTree {

    static class Node {

        long key;
        String value;
        Node left;
        Node right;

        Node(long key, String value) {
            this.key = key;
            this.value = value;
        }
    }
    Node root;

    public RedBlackTree(long[] numbers,String[]names) {
        root = arrayToRedBlackTreeRoot(names,numbers, 0, numbers.length - 1);
    }

    static Node arrayToRedBlackTreeRoot(String[]names,long[] numbers, int i, int j) {
        if (i > j) {
            return null;
        }
        int x = (j + i) / 2;
        Node local_root = new Node(numbers[x], names[x]);
        if (i < j) {
            local_root.left = arrayToRedBlackTreeRoot(names,numbers, i, x - 1);
            local_root.right = arrayToRedBlackTreeRoot(names,numbers, x + 1, j);
        }
        return local_root;
    }

    public String find(long key) {
        Node node = root;
        while (node != null) {
            if (node.key == key) {
                return node.value;
            } else if (node.key < key) {
                node = node.right;
            } else if (node.key > key) {
                node = node.left;
            }
        }
        return "nobody";
    }
}

public class NameNumber {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        long[] numbers = new long[10];
        String[] names = new String[10];
        // Home Work: Write code to initialize both arrays from any input.(file/console)

        // bubble sort starts here: (you can choose your favourite algorithm)
        for (int i = 0; i < numbers.length; ++i) {
            for (int j = 1, n = numbers.length - i; j < n; ++j) {
                if (numbers[j - 1] > numbers[j]) {
                    long temp_number = numbers[j - 1];
                    numbers[j - 1] = numbers[j];
                    numbers[j] = temp_number;
                    String temp_name = names[j - 1];
                    names[j - 1] = names[j];
                    names[j] = temp_name;
                }
            }
        }
        RedBlackTree tree = new RedBlackTree(numbers,names);
        long number_x = 9876543210L;// Home Work: Read this number from input.
        System.out.println("The number: " + number_x + ", belongs to " + tree.find(number_x));

    }
}
 
You can also replace the statement return "nobody" with return null in the code above. Also try thinking of some programming cases where a number-to-object map can be replaced with this code. Like: where you may have used java.util.HashMap<Long,String>(in Java).

Wednesday, 10 October 2012

Zero Factorial is One

Ever looked for a simple explanation for: why 0!=1 ?

I am sure your teachers may have explained you through this:
 n! = (n-1)!n
 hence, 1! = 0!1
 dividing both sides by 1, 1! / 1 = 0!1 / 1
 hence 1 = 0!

But here I am going to explain in a different way.

Look at this set: {a,b,c}. It has 3 elements: a , b , and c . Now arrange all these elements in different ways, and let us see how many different arrangements are possible.

 Arrangement 1: {a,b,c}
 Arrangement 2: {b,c,a}
 Arrangement 3: {c,a,b}
 Arrangement 4: {a,c,b}
 Arrangement 5: {c,b,a}
 Arrangement 6: {b,a,c}
So with a set of 3 elements, 6 arrangements are possible. So we have 3! = 6.


Similarly this set: {a,b}, with 2 elements has 2 possible arrangements: {a,b} and {b,a}. That makes 2!=2.
Similarly this set: {a}, with 1 element has 1 possible arrangement: {a}. That makes 1!=1.

Now look at this set, it has no element: {}.
In how many ways can you arrange it's elements ? The answer is, there is only 1 possible arrangement: {}.
So that brings us to this result: 0!=1


Average Without Overflow

Puzzle:

There are 10 numbers, each has values between 0 to 99. Write computer program to find the average of those 10 numbers, such that the total must never exceed 99 (at any point during or after iteration).

Answer:

/*
 * First Approach
 * Programming language: Java
 */
int[]number=new int[10];
// initialize number
int absolute_average=0,sum_of_remainders=0;
for(int i = 0 ; i < 10 ; ++i)
{ absolute_average+=number[i]/10;
  sum_of_remainders+=number[i]%10;
  if(sum_of_remainders>10)
  { absolute_average+=sum_of_remainders/10;
    /* or better:
    absolute_average+=1;
    (as sum_of_remainders cannot be more than 18 with this if-block in place.)
    */
    sum_of_remainders%=10;
  }
}
float average=absolute_average+(sum_of_remainders/10.0F);
// or :
//float average=((float)absolute_average)+(((float)sum_of_remainders)/10);

/*
 * Alternate Approach
 * Programming language: Java
 */
byte[]number=new byte[10];
// initialize number
double average=0.0;
for(int i = number.length ; --i > -1 ; )
  average+=number[i]/10.0;


Reason:

(x[1]+x[2]+.....+x[n])/n = (x[1]/n)+(x[2]/n)+.....+(x[n]/n)

Need for this puzzle:

Programming in similar way can be useful in preventing bit-overflow in a computer program.
More Explanation:
For example, int in Java can store a value between Integer.MIN_VALUE and Integer.MAX_VALUE, and any attempt to assign a number out of those bounds (which can happen during addition, subtraction, or multiplication) will result in bit-overflow and loss of precision. So is with byte(between Byte.MIN_VALUE and Byte.MAX_VALUE), short(between Short.MIN_VALUE and Short.MAX_VALUE), and long(between Long.MIN_VALUE and Long.MAX_VALUE).