向 BST 添加元素时的 StackOverflow java

Question

private Node put(Node x, Float longitude, Float latitude, String place, String address) {
    if (x == null)
        return new Node(longitude, latitude, place, address, 1);
    int cmpX = longitude.compareTo(x.longitude);
    int cmpY = latitude.compareTo(x.latitude);
    if (cmpX < 0 | (cmpX == 0 && cmpY < 0)) {
        if (x.left == null) { x.left = new Node(longitude, latitude, place, address, x.N);}
        else{x.left = put(x.left, longitude, latitude, place, address);}
    } else if (cmpX >= 0) {
        if (x.right == null) {  x.right = new Node(longitude, latitude, place, address, x.N);}
        else{x.right = put(x.right, longitude, latitude, place, address);}
    }
    x.N = 1 + size(x.left) + size(x.right);
    return x;
}

我有这段代码，我试图用它插入到 BST 中，它适用于前 3000 个左右的元素，然后才导致 Whosebug 错误。我该如何防止这种情况发生？

Answer 1

您遇到 WhosebugError 的原因是您按已排序的顺序插入了项目。让我们看看在这种情况下会发生什么。我将使用整数，即使您有更复杂的对象，为了简单地了解会发生什么。

插入1后：

Root(1)

插入2后：

Root(1)
    \
     (2)

插入3后：

Root(1)
    \
     (2)
      \
       (3)

插入n后：

Root(1)
    \
     (2)
      \
       ...
        \
         (n)

您将 put 实现为递归方法。因此，当你添加了 3000 个元素，并且你试图添加第 3001 个元素时，你需要重复 3000 次，现在调用堆栈上有 3000 个 put 副本，关于你说的地方它溢出了。

您可以将 put 转换为迭代方法，使用 while 循环而不是递归。这将消除 WhosebugError，但它不会解决问题的根源（可以这么说）——您的 BST 看起来像一个链表。

您可以随机提交元素。它可能看起来像这样：

    Root(1123)
     /        \
   (799)       (2800)
   /  \       /     \
 (64) (999) (1599)   (2901)

它可能没有得到适当的平衡，但很可能它不会退化为按排序顺序插入的链表情况。

当一个分支与另一个分支相比太大时，您可以对特定节点执行旋转。如果你喜欢冒险，你可以实现一个 red-black tree，一个使用旋转来保持树平衡的 BST "enough"。

向 BST 添加元素时的 StackOverflow java

StackOverflow while adding elements to a BST java

java

stack-overflow

binary-search-tree