CODEWITHSUNDEEP
javaalgorithmdata-structuresbinary-search-tree
Boyko Arsov
Boyko Arsov

Reputation: 341

How to balance an existing random binary search tree (BST) using an array (in Java)?

I got the following assignment - I have a certain java code for a binary search tree and I need to add methods to do the following things with it:

  1. Transform the BST into an array that's sorted by BST data keys.
  2. Create a balanced BST from an ordered integer array.
  3. Use 1. and 2. to balance an existing BST (randomly generated and presumably somewhat unbalanced)
  4. Display the BST before and after balancing.

Please guys, help me if you're smarter than me and know how can that be achieved!

Here is the code that I need to work with:

import java.util.*;
class BtreeNode {

    int data;
    BtreeNode L,R;
    static int depth=0;

    public BtreeNode(){
         data = 0; L = null; R=null;
    }
    public BtreeNode(int key){
         this();data = key;
    }
    public String toString()    {
        return  "["+data+"]";
    }



    public static BtreeNode insOrd(BtreeNode roo, int key){
        if(roo==null)return new BtreeNode(key);
        //Не се допуска повторение на ключове
        if(key==roo.data)return roo;
        if(key<roo.data)roo.L=insOrd(roo.L,key);
        else roo.R=insOrd(roo.R,key);
        return roo;
    }

    public static BtreeNode generate(int length) {
        BtreeNode start = null;
        Random rn = new Random();
        for(int i = 0; i < length; i++){
            start = insOrd(start,rn.nextInt(10000));
        }
        return start;
    }

    public static void spc(int n){
        for(int i=0;i<n;i++)System.out.print(" ");
    }

    public static void print(BtreeNode roo){
        if(roo!=null){
            depth++;
            print(roo.R);
            spc(depth);System.out.println(roo);
            print(roo.L);
            depth--;
        }
    }

    public static BtreeNode find(BtreeNode roo, int key){
        BtreeNode r=null;
        if(roo==null)return r;
        if(roo.data==key)r= roo;
        if(key>roo.data)r= find(roo.R,key);
        if(key<roo.data)r= find(roo.L,key);
        return r;
    }
};

public class Main {

        public static void main(String[] args){
            int N;
            Scanner sc = new Scanner(System.in);
            System.out.print("Enter the number if tree items:");
            N=sc.nextInt();
            BtreeNode c = BtreeNode.generate(N);
            BtreeNode.print(c);
        /*
            System.out.println("This tree has "+
                    BtreeNode.weight(c)+" nodes and "+
                    BtreeNode.height(c)+" levels.");
        */
       }
}

UPDATE:

Thank you soooo much guys for your great help, you can't imagine how grateful I am for your advice!!!

I have the whole program working. I am going to post it because somebody might need something like that sometime. 

import java.util.*;
class BtreeNode {

    int data;
    BtreeNode L,R;
    static int depth=0; 

    public BtreeNode(){
         data = 0; L = null; R=null;
    }
    public BtreeNode(int key){
         this();data = key;
    }
    public String toString()    {
        return  "["+data+"]";
    }


    public static ArrayList<BtreeNode> asList(BtreeNode node) {
        ArrayList<BtreeNode> result = new ArrayList<BtreeNode>();
        traverse(node, result);
        Collections.sort(result, new Comparator<BtreeNode>() {
            @Override
            public int compare(BtreeNode arg0, BtreeNode arg1) {
                if (arg0.data < arg1.data)
                    return -1;
                else if (arg0.data > arg1.data)
                    return 1;
                return 0;
            }
        });
        return result;
    }

    private static void traverse(BtreeNode node, ArrayList<BtreeNode> result) {
        if (node.L != null) {
            traverse(node.L, result);
        }
        result.add(node);
        if (node.R != null) {
            traverse(node.R, result);
        }
    }

    public static BtreeNode sortedArrayToBST (ArrayList<BtreeNode> result, int start, int end) {
        if (start > end) return null;
          // same as (start+end)/2, avoids overflow.
          int mid = start + (end - start) / 2;
          BtreeNode node = new BtreeNode(result.get(mid).data);
          node.L = sortedArrayToBST(result, start, mid-1);
          node.R = sortedArrayToBST(result, mid+1, end);

          return node;
        }


    public static BtreeNode insOrd(BtreeNode roo, int key){
        if(roo==null)return new BtreeNode(key);

        if(key==roo.data)return roo;
        if(key<roo.data)roo.L=insOrd(roo.L,key);
        else roo.R=insOrd(roo.R,key);
        return roo;
    }

    public static BtreeNode generate(int length) {
        BtreeNode start = null;
        Random rn = new Random();
        for(int i = 0; i < length; i++){
            start = insOrd(start,rn.nextInt(10000));
        }
        return start;
    }

   public static void spc(int n){
    for(int i=0;i<n;i++)System.out.print(" ");
   }

    public static void print(BtreeNode roo){
        if(roo!=null){
            depth++;
            print(roo.R);
            System.out.print("Level "+depth);
            spc(depth);
            System.out.println(roo);
            print(roo.L);
            depth--;
        }
    }

    public static BtreeNode find(BtreeNode roo, int key){
        BtreeNode r=null;
        if(roo==null)return r;
        if(roo.data==key)r= roo;
        if(key>roo.data)r= find(roo.R,key);
        if(key<roo.data)r= find(roo.L,key);
        return r;
    }
}; 

public class Main {

        public static void main(String[] args){
            int N;
            Scanner sc = new Scanner(System.in);
            System.out.print("Enter the number if tree items:");
            N=sc.nextInt();
            BtreeNode c = BtreeNode.generate(N);
            BtreeNode.print(c);
            System.out.println("********************");
        /*
            System.out.println("This tree has "+
                    BtreeNode.weight(c)+" nodes and "+
                    BtreeNode.height(c)+" levels.");
        */
            ArrayList<BtreeNode> result = BtreeNode.asList(c);
            for (BtreeNode btreeNode : result) {
                System.out.println(btreeNode.data);
            }

        // insert in sorted order
            c = result.get(0);
            for (int i = 1; i < result.size(); i++) {
                BtreeNode.insOrd(c, result.get(i).data);
            }
            BtreeNode.print(c);

            System.out.println("********************");

            BtreeNode d = BtreeNode.generate(N); 
            BtreeNode.print(d);

            System.out.println("********************");

            ArrayList<BtreeNode> result2 = BtreeNode.asList(d);

            for (BtreeNode btreeNode : result2) {
                System.out.println(btreeNode.data);
            }

            System.out.println("********************");

            BtreeNode.print(BtreeNode.sortedArrayToBST(result2, 0, result2.size()-1));
        }
}

Upvotes: 1

Views: 4933

Answers (3)

Martin Gjaldbaek
Martin Gjaldbaek

Reputation: 3015

1) Creating the sorted array can be done with an "inorder tree walk" - it's fairly easily implementable as a recursive function that you start on the root node. It would look something like this:

void addToListInOrder(List<BtreeNode> l) {
    if(L != null) {
        L.addToListInOrder(l);
    }
    list.add(this);
    if(R != null) {
        R.addToListInOrder(l);
    }
}

2) A recursive algorithm would work well here as well: Pick a point in the middle (round up or down if needed) and pick that as the root node. Then subdivide the remaining points in two lists, those before and those after the chosen node, and then call the algorithm recursively on those. Then set the results as the left and right child of the current node. and finally return the node that was chosen. Be sure to handle lists with only a single or a few nodes correctly

3) Do 1 and then 2 on the BST to get a balanced recreation.

4) I've used graphviz for some nice visualizations in the past, but that's probably beyond the scope of your assignment. In it I used an inorder graph walk to create the source file for graphviz

Upvotes: 2

darijan
darijan

Reputation: 9775

Well for the first point you have to have a global array and a traverse method. Traverse method shoould work something like this:

in main method at the end add this:

ArrayList<BtreeNode> result = BtreeNode.asList(c);
    for (BtreeNode btreeNode : result) {
        System.out.println(btreeNode.data);
    }

// insert in sorted order
    c = result.get(0);
    for (int i = 1; i < result.size(); i++) {
        c.insOrd(c, result.get(i).data);
    }
    BtreeNode.print(c);

add this methods to BtreeNode class:

public static ArrayList<BtreeNode> asList(BtreeNode node) {
    ArrayList<BtreeNode> result = new ArrayList<BtreeNode>();
    traverse(node, result);
    Collections.sort(result, new Comparator<BtreeNode>() {
        @Override
        public int compare(BtreeNode arg0, BtreeNode arg1) {
            if (arg0.data < arg1.data)
                return -1;
            else if (arg0.data > arg1.data)
                return 1;
            return 0;
        }
    });
    return result;
}

private static void traverse(BtreeNode node, ArrayList<BtreeNode> result) {
    if (node.L != null) {
        traverse(node.L, result);
    }
    result.add(node);
    if (node.R != null) {
        traverse(node.R, result);
    }
}

Upvotes: 2

Zhivko Draganov
Zhivko Draganov

Reputation: 1253

Just check http://www.roseindia.net/java/java-get-example/java-binary-tree-code.shtml For all of these operation you should use reqursion with end check for current node if it hasn't got more childs.

Upvotes: -1

Related Questions