Daily Archives: January 27, 2015

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. }

Find the sequence in an array with largest sum

Problem: For any given input of numbers, find the maximum sum in a range (x, y| x<=y), the sum is defined as (A[i]+ A[i+1] + … + A[j]) where x<=i<=j<=y.
This problem can be solved by greedy algotithm:

  1. public class LargestSequence {
  2.     public static void main(String[] args) {
  3.         int[] arr = { -3, -4, 3, 2, 5, -6, 3, 5, 1, -3, -2, -90, 10 };
  4.         Interval result = findLargestSequence(arr);
  5.         System.out.println(result);
  6.     }
  7.     /*
  8.      * For any given input of numbers, find the maximum sum in a range (x, y| x<=y),
  9.      * the sum is defined as (A[i]+ A[i+1] + … + A[j]) where x<=i<=j<=y.
  10.      * @param the input array. element in array can be either posivie or negative.
  11.      */
  12.     public static Interval findLargestSequence(int[] arr) {
  13.         if (arr == null || arr.length == 0) {
  14.             return null;
  15.         }
  16.         Interval curr_interval = new Interval(0, 0);
  17.         Interval max_interval = new Interval(0, 0);
  18.         int max_sum = arr[0];
  19.         int curr_sum = arr[0];
  20.         for (int i = 1; i < arr.length; i++) {
  21.             curr_sum += arr[i];
  22.             curr_interval.y = i;
  23.             if (curr_sum > max_sum) {
  24.                 max_sum = curr_sum;
  25.                 max_interval.x = curr_interval.x;
  26.                 max_interval.y = curr_interval.y;
  27.             }
  28.             if (curr_sum < 0) {
  29.                 curr_interval.x = i + 1;
  30.                 curr_sum = 0;
  31.             }
  32.         }
  33.         return max_interval;
  34.     }
  35.     static class Interval {
  36.         int x;
  37.         int y;
  38.         int max_sum;
  39.         Interval(int x, int y) {
  40.             this.x = x;
  41.             this.y = y;
  42.         }
  43.         @Override
  44.         public String toString() {
  45.             return “(” + this.x + “, ” + this.y + “)”;
  46.         }
  47.     }
  48. }

Find range in BST

This is a practice for Tree. The idea is to find all results in a certain range in BST.

  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import util.Tree;
  4. public class FindRangeInBst {
  5.     public static void main(String[] args) {
  6.         Tree bst = Tree.getBst();
  7.         List<Tree> result = new ArrayList<Tree>();
  8.         findRangeInBst(bst, 11, 16, result);
  9.         System.out.println(result.toString());
  10.     }
  11.     public static void findRangeInBst(Tree tree, int min, int max,
  12.             List<Tree> result) {
  13.         if (tree == null) {
  14.             return;
  15.         }
  16.         if (tree.value >= min && tree.value <= max) {
  17.             result.add(tree);
  18.             findRangeInBst(tree.left, min, max, result);
  19.             findRangeInBst(tree.right, min, max, result);
  20.         } else if (tree.value < min) {
  21.             findRangeInBst(tree.right, min, max, result);
  22.         } else {
  23.             findRangeInBst(tree.left, min, max, result);
  24.         }
  25.     }
  26. }