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
Using the similar operation on right sub-tree {-43 , -11}, we set -11 as right child-node of -54 . Like this:
When the right sub-tree goes through similar operation, the tree looks like this:
A better view of the above tree will be:
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.]
