麻煩在Java中插入到BST中

我正在處理文本文件，這些文件有很長的單詞列表並將它們插入二進制樹中。我擁有的一個文本文件是未排序的單詞列表，並且它完美地插入BST。但是排序形式完全相同的單詞列表給我帶來麻煩。我不斷從我的插入函數中得到一個StackOverflowError。麻煩在Java中插入到BST中

private TreeNode insert(TreeNode iter, String item) { 
    if (iter == null) { 
     iter = new TreeNode(item); 
    } else { 
     if (item.compareTo(iter.item) < 0) { 
     iter.left = insert(iter.left, item); 
     } else { 
     iter.right = insert(iter.right, item); 
     } 
    } 
    return(iter); 
}

我的理論是，因爲它是爲了它只會調用插入權利，導致它以某種方式溢出。如果有人有任何想法如何解決這個問題，這將是美好的！

來源

2014-09-12 Tyler

當你給BST一個排序列表時，根據排序順序，所有元素將被插入同一側（全部左側或全部右側）。這會導致您的BST變得非常高且不平衡，導致非常深的遞歸，最終導致StackOverflowError。

這是衆所周知的一般BSTs。隨着洗牌價值，BST將相對平衡，所有分支具有相似的高度。使用排序後的值，樹會變得不平衡，並且有效地用作鏈接列表。爲了讓BST高效，你需要保持平衡。

保持BST平衡的一種方法是使用self-balancing implementations之一，如AVL tree或red-black tree。一個懶惰的解決方法是插入洗牌的值。然而，後者並不能保證BST會保持平衡。在最糟糕的極端情況下，這些值可能會在洗牌後完全排序。

來源

2014-09-12 22:27:09 janos

麻煩在Java中插入到BST中

回答

相關問題