Устранение неполадок в BST в Java

Question

Я работаю с текстовыми файлами, которые имеют длинные списки слов и вставляют их в двоичное дерево. Один текстовый файл, который у меня есть, - это список несортированных слов, и он отлично вписывается в BST. Но тот же список слов в отсортированной форме дает мне проблемы. Я продолжаю получать StackOverflowError из моей функции вставки.

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); 
} 

Моя теория заключается в том, что, поскольку она в порядке, она будет только вставлять вправо, заставляя ее как-то переполняться. Если у кого-нибудь есть идеи, как это исправить, было бы замечательно!

Answer 1

Когда вы подаете свой BST отсортированный список, все элементы будут вставлены на одной стороне (либо влево или вправо), в зависимости от порядка сортировки. Это приводит к тому, что ваш BST становится очень высоким и неуравновешенным, что вызывает очень глубокую рекурсию, что в конечном итоге приведет к StackOverflowError.

Это хорошо известно о BST в целом. При перетасованных значениях BST будет относительно сбалансированным, причем все ветви имеют схожие высоты. С отсортированными значениями дерево становится несбалансированным и эффективно работает как связанный список. Для того чтобы BST был эффективным, вам нужно держать его сбалансированным.

Одним из способов сохранения сбалансированного BST является использование одного из self-balancing implementations, например AVL tree или red-black tree. Ложное обходное решение заключается в вставке значений, перетасованных. Однако последнее не гарантирует сбалансированности BST. В худшем случае значения могут быть полностью отсортированы после перетасовки.