0

I have an Array of Strings that are in order A-Z. I was wondering the best way to go about sorting them for a balanced binary search tree. My initial thought is to split the array up into the first half and the second half and then sort them individually.

Shouldn't I be able to use a recursive way to keep splitting it in half to get the next Node for the tree? I just can't wrap my head around it right now and thought I would ask if any one had any ideas. to lead me in the right direction or provide some examples. Thanks!

i am using my own BinaryTree Class and BinaryTreeNode Class. EDIT:

public class BinaryTree {
private BinaryTreeNode root;

public void insert(String text) {

root = insertNode(root, text); 

}

private BinaryTreeNode insertNode(BinaryTreeNode curNode, String text) {
if (curNode == null) {
    BinaryTreeNode newNode = new BinaryTreeNode(text);
    //newNode.value = text;
    return newNode;
} else {
    if (text.compareTo(curNode.value) < 0 ) {
        //left child
        //use of recursion to properly place Node
        curNode.left = insertNode(curNode.left, text);
        return curNode;
    }

        else {

        //right
        //use of recursion to properly place Node
        curNode.right = insertNode(curNode.right, text);
        return curNode;
    }
}

}

public BinaryTreeNode getRoot() {
return root;
}

 public void setRoot(BinaryTreeNode root) {
this.root = root;
 }
 }

would this be considered a Self balancing binary search tree?

Improve this question

2 Answers 2

Reset to default
1

Your tree doesn't seem to be self balancing. A self-balancing BST will take steps, after an insertion, or after a number of insertions, to ensure that it is (roughly) balanced.

If you only add the elements once and use the tree just for reads, you have your sorted array and then proceed as follows: select the element in the middle. create a root with it as key, and then recursively add the elements to its left (the smaller elements) as the left subtree of your root, and the elements to its right as the right subtree, respectively. You should end up with a BST that's more or less balanced. Example code:

public class BinaryTree {

    /* ... */


    //each recursive call receives a pair of bounds for the part of the 
    //array it has to process: left and right
    public static BinaryTreeNode nodeFromSortedArray(String[]a,
                                           int left, int right){

        if (right<left) return null;

        if (right==left)
            return new BinaryTreeNode(a[left]);

        int mid = (left+right)/2;

        //create node from middle element
        BinaryTreeNode n = new BinaryTreeNode(a[mid]);

        //recursively add elements to the left as its right subtree
        n.left = nodeFromSortedArray(a, left, mid-1);

        //recursively add elements to the right as its right subtree
        n.right = nodeFromSortedArray(a, mid+1, right);

        return n;
    }

    public static BinaryTree fromSortedArray(String[]a){
        BinaryTree bt = new BinaryTree();
        bt.setRoot(nodeFromSortedArray(a,0,a.length-1));
        return bt;
    }

    /* ... */
}

However, in this case, you could simply keep your elements in the sorted array, and use binary search to index into it, instead of a tree. The complexity should be the same, O(logn), but you need less references to store the whole thing, and cache performance should be better.

If you need to have a mutable tree, and want to make it efficient, you'd probably need to make it self-balanced, case in which the order in which you add your elements to it doesn't matter.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

thanks Vlad, I really don't need a self balancing tree as I load up the array from a file. I understand what your saying. To select the middle of the array as the root. But I am getting confused at recursively going through the left or right side. Do I need to keep dividing by 2 to keep getting correct values to be added for left side in the recursive function? This is the only part I am stuck on. I learn best from example. Thanks!
Thanks, I need to study more on recursion. I understand better now though through your example.
I am glad to help. Recursion is indeed a valuable technique, and I think you'll be able to find plenty of documentation on the topic. You can start with something simple like the Fibonacci sequence which, although slow using recursion, can help you understand. You can even trace the code by hand and figure out the calls and returns.
Hey Vlad, just had a quick question. In using the above recursive algortithm I noticed that some particular Nodes are in incorrect spots to be searched and come up as null. For example: if root node = "mark" and its left child = "cat" somehow the right child for "cat" is "bull". In my find algorithm I use the CompareTo method to check if the word to be found is > 0 < 0 to traverse the tree and check the correct child. But "bull" will never be found because it is in the incorrect spot. Any ideas? I am not sure how to approach it.
If you show me the array that you passed to fromSortedArray, I could try it myself and find out what went wrong.
|
0

If you have a binary search tree that is self-balancing it is quite probably counter-productive to pre-sort the array. The algorithm for optimally adding sorted data to a balanced tree is quite different from the algorithm for adding unordered data.

However there is nothing 'self-balancing' about the code you posted. It is just an ordinary binary tree insertion algorithm.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.