Order statistic tree

According to wikipedia link, order statistic tree mainly offers 2 following functions:
Select(i) — find the i’th smallest element stored in the tree
Rank(x) – find the rank of element x in the tree, i.e. its index in the sorted list of elements of the tree

In order to find the rank/index, it is important to find the left subtree rank, and right subtree rank. After researching on character of order statistic tree, I conducted the following formula.
Let t_rank be rank of current tree, lr_num be number of left right subtree, r_num be number of right subtree, rr_num be right right subtree.
rank of left sub tree = t_rank – 1 – lr_num
rank of right sub tree = t_rank + r_num – rr_num

This following code is a try for order statistic binary tree. I didn’t write the construction for it, only wrote select and rank function.

1. import util.Tree;
2. public class OrderedStatisticTree {
3.     public static void main(String[] args) {
4.         Tree tree = Tree.getOrderStatisticBinaryTree();
5.         int rank = rank(tree, 17);
6.         System.out.println(rank);
7.         Tree index_tree = index(tree, 10);
8.         System.out.println(index_tree);
9.     }
10.     /*
11.      * Return the rank of value in tree
12.      */
13.     public static int rank(Tree tree, int value) {
14.         if (tree == null) {
15.             return -1;
16.         }
17.         int rank = tree.num;
18.         while(tree!=null){
19.             rank = rank – (tree.right == null ? 0 : tree.right.num);
20.             if (value == tree.value) {
21.                 return rank;
22.             }
23.             if (value < tree.value) {
24.                 rank = rank – 1;
25.                 tree = tree.left;
26.             } else {
27.                 rank = (tree.right == null) ? -1 : rank + tree.right.num;
28.                 tree = tree.right;
29.             }
30.         }
31.         return -1;
32.     }
33.     /*
34.      * Return the tree, which ranks index.
35.      */
36.     public static Tree index(Tree tree, int index) {
37.         if (tree == null) {
38.             return null;
39.         }
40.         int curr_index = tree.num;
41.         while(tree!=null){
42.             curr_index = curr_index – (tree.right == null ? 0 : tree.right.num);
43.             if (curr_index == index) {
44.                 return tree;
45.             }
46.             if (index < curr_index) {
47.                 curr_index = curr_index – 1;
48.                 tree = tree.left;
49.             } else {
50.                 curr_index = (tree.right == null) ? 0 : curr_index + tree.right.num;
51.                 tree = tree.right;
52.             }
53.         }
54.         return null;
55.     }
56. }

Following auxiliary Tree class helps to create a order statistic tree.

1. package util;
2. public class Tree{
3.     public Tree(int value){
4.         this.value = value;
5.     }
6.     public Tree(String value){
7.         this.valueString = value;
8.     }
9.     public Tree(int value, int num){
10.         this.value = value;
11.         this.num = num;
12.     }
13.     public Tree left;
14.     public Tree right;
15.     public int value;
16.     public String valueString;
17.     /*
18.      * This is used for ordered statistics binary tree
19.      * To store the number under tree.
20.      */
21.     public int num;    //
23.     public static Tree getOrderStatisticBinaryTree(){
24.         Tree t15 = new Tree(15, 15);
25.         Tree t10 = new Tree(10, 6);
26.         Tree t20 = new Tree(20, 8);
27.         Tree t8 = new Tree(8, 2);
28.         Tree t13 = new Tree(13, 3);
29.         Tree t17 = new Tree(17, 3);
30.         Tree t23 = new Tree(23, 4);
31.         Tree t7 = new Tree(7, 1);
32.         Tree t11 = new Tree(11, 1);
33.         Tree t14 = new Tree(14, 1);
34.         Tree t16 = new Tree(16, 1);
35.         Tree t18 = new Tree(18, 1);
36.         Tree t22 = new Tree(22, 2);
37.         Tree t24 = new Tree(24, 1);
38.         Tree t21 = new Tree(21, 1);
39.         t15.left = t10; t15.right = t20;
40.         t10.left = t8; t10.right = t13;
41.         t20.left = t17; t20.right = t23;
42.         t8.left = t7;
43.         t13.left = t11; t13.right = t14;
44.         t17.left = t16; t17.right = t18;
45.         t23.left = t22; t23.right = t24;
46.         t22.left = t21;
47.         return t15;
48.     }
50.     @Override
51.     public String toString(){
52.         return String.valueOf(value);
53.     }
54. }