Java - StackOverFlowError

Question

为此我需要一些帮助。

首先我有一个 BinarySearchTree 类

import java.util.ArrayList;
import java.util.List;

public class BinarySearchTree<E extends Comparable<? super E>> {

private BSTNode<E> root;
private int size;

// root ==null iff size == 0

public BinarySearchTree() {
    root = null;
    size = 0;
}


public boolean add(E value) {
    int oldSize = size;
    root = addHelper(root, value);
    return oldSize != size;
}

private BSTNode<E> addHelper(BSTNode<E> n, E val) {
    if (n == null) {
        n = new BSTNode<E>(null, val, null);
        size++;
    } else {
        int diff = val.compareTo(n.getData());
        if (diff < 0)
            n.setLeft(addHelper(n.getLeft(), val));
        else if (diff > 0)
            n.setRight(addHelper(n.getRight(), val));
    }
    return n;
}


public boolean remove(E value) {
    int oldSize = size;
    root = removeHelp(root, value);
    return oldSize != size;
}

// helper method for remove
private BSTNode<E> removeHelp(BSTNode<E> n, E val) {
    if (n != null) {
        int diff = val.compareTo(n.getData());
        if (diff < 0)
            n.setLeft(removeHelp(n.getLeft(), val)); // traverse the left
                                                     // side
        else if (diff > 0)
            n.setRight(removeHelp(n.getRight(), val)); // traverse right
                                                       // side
        else // if value is found
        {
            size--;
            if (n.getLeft() == null && n.getRight() == null) // if value
                                                             // contained in
                                                             // leaf, just
                                                             // make nul;
                n = null;
            else if (n.getRight() == null) // single child to left
                n = n.getLeft(); // move the child up to replace removed
                                 // node
            else if (n.getLeft() == null)
                n = n.getRight();
            else // two children, replace value with max of left subtree -
                 // it will not have a right subtree
            {
                n.setData(getMax(n.getLeft()));
                // now remove max of left subtree from its previous position
                n.setLeft(removeHelp(n.getLeft(), n.getData()));
                // add 1 back to size since size will be decremented from
                // this 2nd removal
                size++;
            }

        }
    }
    return n;
}

// helper method to find Max of a subtree
private E getMax(BSTNode<E> n) {
    while (n.getRight() != null)
        n = n.getRight();
    return n.getData();
}


public boolean isPresent(E value) {
    assert value != null : "Precondition failed: value != null";
    if (root == null)
        return false;
    return isPresentHelp(root, value);

}

public boolean isPresentHelp(BSTNode<E> n, E item) {
    if (n == null)
        return false;
    else {
        E temp = n.getData();
        // if item to search is greater than node, traverse right
        if (temp.compareTo(item) < 0)
            return isPresentHelp(n.getRight(), item);
        else if (temp.compareTo(item) > 0)
            return isPresentHelp(n.getLeft(), item);
        else
            return true;
    }
}


public int size() {
    return size;
}


public int height() {
    return heightHelper(root);
}

public int heightHelper(BSTNode<E> n) {
    int tempLeft, tempRight;
    if(n == null) 
        return -1;
    tempLeft = 1 + heightHelper(n.getLeft());
    tempRight = 1 + heightHelper(n.getRight());
    if(tempLeft > tempRight)
        return tempLeft;
    else 
        return tempRight;
}


public List<E> getAll() {
    List<E> result = new ArrayList<E>();
    return getAllHelp(root, result);
}

public List<E> getAllHelp(BSTNode<E> n, List<E> result) {

    if (n != null) {
        // traverse left to lowest value
        getAllHelp(n.getLeft(), result);
        // add to arraylist if it can go left no further (smallest current
        // value)
        result.add(n.getData());
        // traverse right if can't go left anymore
        getAllHelp(n.getRight(), result);

    }
    return result;
}


public E max() {
    return getMax(root);
}


public E min() {
    return getMin(root);
}

private E getMin(BSTNode<E> n) {
    while (n.getLeft() != null)
        n = n.getLeft();
    return n.getData();
}


public boolean iterativeAdd(E data) {
    BSTNode<E> n = root;
    while (n != null) {
        if (n.getData().compareTo(data) > 0) {
            if (n.getLeft() == null) {
                n.setLeft(new BSTNode<E>(data));
                size++;
                return true;
            } else
                n = n.getLeft();
        } else if (n.getData().compareTo(data) < 0) {
            if (n.getRight() == null) {
                n.setRight(new BSTNode<E>(data));
                size++;
                return true;
            } else
                n = n.getRight();
        } else
            return false;
    }
    root = new BSTNode<E>(null, data, null);
    size++;
    return true;
}


public E get(int kth) {
    assert 0 <= kth && kth < size() : "Precondition failed: 0 <= kth < size()";
    // keep track of which index recursive call is on (or the kth element)
    int count[] = { 0 };
    return getHelp(kth, root, count);
}

public E getHelp(int nth, BSTNode<E> n, int[] count) {
    E result = null;
    if (n != null) {
        result = getHelp(nth, n.getLeft(), count);
        if (result == null) {
            if (count[0] == nth) {
                return n.getData();
            } else {
                count[0]++;
                result = getHelp(nth, n.getRight(), count);
            }
        }
    }
    return result;
}


public List<E> getAllLessThan(E value) {
    List<E> result = new ArrayList<E>();
    return getAllLessHelp(root, result, value);
}

public List<E> getAllLessHelp(BSTNode<E> n, List<E> result, E value) {
    if (n != null) {
        getAllLessHelp(n.getLeft(), result, value);
        if (n.getData().compareTo(value) < 0) {
            result.add(n.getData());
        }
        getAllLessHelp(n.getRight(), result, value);
    }
    return result;
}


public List<E> getAllGreaterThan(E value) {
    List<E> result = new ArrayList<E>();
    return getAllGreaterHelp(root, result, value);
}

// returns the BSTNode containing the value
public List<E> getAllGreaterHelp(BSTNode<E> n, List<E> result, E value) {
    if (n != null) {
        if (n.getData().compareTo(value) > 0) {
            getAllGreaterHelp(n.getLeft(), result, value);
            result.add(n.getData());
        }
        getAllGreaterHelp(n.getRight(), result, value);
    }
    return result;
}

public int numNodesAtDepth(int d) {
    return numNodesHelp(d, root, 0);
}

public int numNodesHelp(int d, BSTNode<E> n, int count) {
    count = 0;
    if (n != null) {
        if (d == 0)
            count++;
        else {
            count += numNodesHelp(d - 1, n.getLeft(), count);
            count += numNodesHelp(d - 1, n.getRight(), count);
        }
    }
    return count;
}


public void printTree() {
    printTree(root, "");
}

private void printTree(BSTNode<E> n, String spaces) {
    if (n != null) {
        printTree(n.getRight(), spaces + "  ");
        System.out.println(spaces + n.getData());
        printTree(n.getLeft(), spaces + "  ");
    }
}


private static class BSTNode<E extends Comparable<? super E>> {
    private E data;
    private BSTNode<E> left;
    private BSTNode<E> right;

    public BSTNode() {
        this(null);
    }

    public BSTNode(E initValue) {
        this(null, initValue, null);
    }

    public BSTNode(BSTNode<E> initLeft, E initValue, BSTNode<E> initRight) {
        data = initValue;
        left = initLeft;
        right = initRight;
    }

    public E getData() {
        return data;
    }

    public BSTNode<E> getLeft() {
        return left;
    }

    public BSTNode<E> getRight() {
        return right;
    }

    public void setData(E theNewValue) {
        data = theNewValue;
    }

    public void setLeft(BSTNode<E> theNewLeft) {
        left = theNewLeft;
    }

    public void setRight(BSTNode<E> theNewRight) {
        right = theNewRight;
    }
}
}

和测试类

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.TreeSet;

public class BSTTester {

public static void main(String[] args) {
    // do the experiment
    experiment_1();
    experiment_2();
    experiment_3();
}

private static void experiment_1() {
    Random r = new Random();
    Stopwatch s = new Stopwatch();

    for (int n = 1000; n <= 1024000; n *= 2) {
        double avgTime = 0;
        int avgHeight = 0;
        int avgSize = 0;
        for (int index = 0; index < 10; index++) {
            BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
            s.start();
            for (int i = 0; i < n; i++) {
                b.add(r.nextInt());
            }
            s.stop();
            avgTime += s.time();
            avgHeight += b.height();
            avgSize += b.size();
        }
        System.out.println("Random: It took an average of " + avgTime / 10 + " seconds to add "
                        + n + " items to the BST.");
        System.out.println("Random: The tree has a height of " + avgHeight / 10
                        + " rows when it has " + n + " items.");
        System.out.println("Random: The tree has a size of " + avgSize / 10 + " items when "
                        + n + " supposed to be added");
        System.out.println(" ");
    }
}

private static void experiment_2() {
    Random r = new Random();
    Stopwatch s = new Stopwatch();

    for (int n = 1000; n <= 1024000; n *= 2) {
        double avgTime = 0;
        int avgSize = 0;
        for (int index = 0; index < 10; index++) {
            TreeSet<Integer> t = new TreeSet<Integer>();
            s.start();
            for (int i = 0; i < n; i++) {
                t.add(r.nextInt());
            }
            s.stop();
            avgTime += s.time();
            avgSize += t.size();
        }
        System.out.println("In Order TreeSet: It took an average of " + avgTime / 10
                        + " seconds to add " + n + " items to the BST.");
        System.out.println("In Order TreeSet: The tree has a size of " + avgSize / 10
                        + " items when " + n + " supposed to be added.");
        System.out.println(" ");
    }
}

private static void experiment_3() {
    Stopwatch s = new Stopwatch();

    for (int n = 1000; n <= 1024000; n *= 2) {
        double avgTime = 0;
        int avgHeight = 0;
        int avgSize = 0;
        for (int index = 0; index < 10; index++) {
            BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
            s.start();
            for (int i = 0; i < n; i++) {
                b.iterativeAdd(i);
            }
            s.stop();
            avgTime += s.time();
            avgHeight += b.height();
            avgSize += b.size();
        }
        System.out.println("In Order: It took an average of " + avgTime / 10
                        + " seconds to add " + n + " items to the BST.");
        System.out.println("In Order: The tree has a height of " + avgHeight / 10
                        + " rows when it has " + n + " items.");
        System.out.println("In Order: The tree has a size of " + avgSize / 10 + " items when "
                        + n + " supposed to be added.");
        System.out.println(" ");
    }
}

private static void showTestResults(boolean passed, int testNum) {
    if (passed)
        System.out.println("test " + testNum + " passed.");
    else
        System.out.println("test " + testNum + " failed.");
}
}

所以基本上实验1就是往二叉搜索树中加入N个随机数，记录所花的时间，树的高度，树的大小。实验 2 做同样的事情但是使用 java TreeSet实验三是将N个排序后的数加入到二叉搜索树中

N = 2,000、4,000、8,000、16,000、32,000、64,000、128,00、256,000、512,000 和 1,024,000

事实是，exp1 和 exp2 运行良好。但是当 exp3 运行时，我在添加大约 32000 个项目时得到 StackOverflowError。 height方法对exp1,exp2很好，不知道为什么会导致exp3出错。当我在 exp3 中使用 add 方法而不是 iterativeAdd 方法时也是如此。 add 方法也会导致 StackOverflowError

http://i.imgur.com/DQ42OiI.jpg

任何帮助/解释将不胜感激。谢谢

实验的秒表类

/**
 A class to measure time elapsed.
*/

public class Stopwatch
{
    private long startTime;
    private long stopTime;

    public static final double NANOS_PER_SEC = 1000000000.0;

    /**
     start the stop watch.
    */
    public void start(){
        startTime = System.nanoTime();
    }

    /**
     stop the stop watch.
    */
    public void stop()
    {   stopTime = System.nanoTime();   }

    /**
    elapsed time in seconds.
    @return the time recorded on the stopwatch in seconds
    */
    public double time()
    {   return (stopTime - startTime) / NANOS_PER_SEC;  }

    public String toString(){
        return "elapsed time: " + time() + " seconds.";
    }

    /**
    elapsed time in nanoseconds.
    @return the time recorded on the stopwatch in nanoseconds
    */
    public long timeInNanoseconds()
    {   return (stopTime - startTime);  }
}

好的。感谢大家的帮助。我真的很感激。你们回答的真快:)

Answer 1

您的树根本不平衡，已经退化为链表。由于您是按顺序添加的，它会一直添加到右侧，并且由于没有尝试平衡，因此节点将只包含正确的子节点。

要修复，请查看一些 balancing algorithms或以不同的顺序添加以使其平衡。不平衡的树效率低下并且会减慢您的算法，因为查找和插入将在 O(n) 而不是 O(log n) 时间内发生。