Binary Search Tree and AVLTree Issue

Question

I am making Binary Search Tree and AVL Tree for an assignment.

I am having problem when I try to add 1,000,000 elements to Binary Search Tree but I can add key-> value pairs to AVL Tree.(There is no problem with AVLTree)

If I Balance Binary Search Tree , there would be NO difference with AVL Tree ??(What is the point if I balance binary search tree it becomes a AVLTree?)

I'm getting error from Binary Search Tree after 15,000 elements inserted: Exception in thread "main" java.lang.StackOverflowError

Project Definition:
Using these tests and the code created for naive binary search trees, compare the performance of AVL trees and naive binary search trees for both the time of search, insert and delete and for tree balance on long sequences. You should run tests with up to 1000000 elements in your trees.

public class BinaryTreeExample {

    public static void main(String[] args) {
        new BinaryTreeExample().run();
    }

    static class Node

    {

        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public void run() {
        Node rootnode = new Node(25);

        insert3(rootnode, 50_000);

        for (int i = 0; i < 150_000; i++)
            insert3(rootnode, i);
        System.out.println("Bittaaa");
        // System.out.println(getNodesCount(rootnode));

    }

    protected int getNodesCount(Node root) {

        if (root != null) {
            int counter = 1;
            counter += getNodesCount(root.left);
            counter += getNodesCount(root.right);
            return counter;
        } else
            return 0;

    }

    void insert3(Node node, int value) {
        if (value < node.value) {
            if (node.left == null)
                node.left = new Node(value);
            else
                insert3(node.left, value);
        } else {
            if (node.right == null)
                node.right = new Node(value);
            else
                insert3(node.right, value);
        }
    }


    public void printInOrder(Node node) {
        if (node != null) {
            printInOrder(node.left);
            System.out.println("  Traversed " + node.value);
            printInOrder(node.right);
        }
    }
}

This is very similar to [this question you just asked](http://stackoverflow.com/questions/21139851/cant-add-1-000-000-elements-to-binary-search-tree-in-java), except a lot more confusing. And the answers and comments there do actually address a large part of this question. — Bernhard Barker, Jan 15 '14 at 16:33
The insert function you have there isn't iterative at all. [Here's an iterative insert function](http://stackoverflow.com/a/8384366/1711796) (it's C#, but I'm pretty sure the code looks identical, except for expected name changes, in this case). — Bernhard Barker, Jan 15 '14 at 16:37

Łukasz Kidziński · Accepted Answer · 2014-01-17T07:15:34.143

The StackOverflowError comes from the fact that you implemented your insert recursively. In this case if you add elements 1,2,3,....,15000 your tree will have level 15000 and your recursion will overflow your stack. Implement it imperatively and you won't get StackOverflowError. It should be something like

void insert (Node node, int value) {
    while (true) {
        if (value < node.value) {
            if (node.left == null){
                node.left = new Node(value);
                break;
            }
            else
                node = node.left;
        }
        else {
            if (node.right == null){
                node.right = new Node(value);
                break;
            }
            else
                node = node.right;
        }
    }
}

But the whole approach is not optimal. The behavior above is not the one you expect from the BST. You would like to have level log(15000) instead of 15000. You will achieve this by using a balanced structure. It will still be BST tree but with additional constraint that the level is of order O(log n). So once you are done with BST definitely try AVL :)

i changed insert method type recursive to iteration but problem still exists — Ertuğrul Çetin, Jan 15 '14 at 16:33

Binary Search Tree and AVLTree Issue

1 Answers1