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

  /*
   * 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;
  }

4. 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).