Почему ни один из этих методов BST не работает?

Question

Хорошо, поэтому в моем двоичном дереве поиска я создал кучу методов, но сейчас я тестирую 2 из них. Один из них вставляет элемент в дерево:

public void insert(String word) { //calls the insert method 
    root=insertItem(root, word); 
} 


protected TreeNode insertItem(TreeNode r, String word) { //inserts an item x into the tree 
    if(r==null){ 
     r = new TreeNode(new WordRefs(word)); 
     r.left = null; 
     r.right = null; 
    } 
    else if(word.compareTo(r.item.getWord()) < 0){ 
     r.left = insertItem(r.left, word); 
    } else if (word.compareTo(r.item.getWord()) > 0){ 
     r.left = insertItem(r.right, word); 
    } 
    return r; 
} 

Другой удаляет элемент:

public void delete(String word) { //calls the delete method 
    root = deleteItem(root, word); 
} 


protected TreeNode deleteItem(TreeNode r, String word) { //deletes an item x from the BST 
    if (r == null){ 
     return r; 
    } 
    if(word.compareTo(r.item.getWord()) < 0){ 
     r.left = deleteItem(r.left, word); 
    } else if (word.compareTo(r.item.getWord()) > 0){ 
     r.right = deleteItem(r.right, word); 
    } else if(r.left != null && r.right != null){ 
     return deleteItem(r, word); 
     } 
    return r; 
} 

А вот код, который проверяет эти методы

public static void main(String args[]) { //the tests are in the main method 
    BSTRefBased t; 
    AbstractBinaryTree tt; 
    int i; 
    boolean result; 
    String message; 

    message = "Test 1: inserting 'word1' -- "; //tests the insert method first 
    t = new BSTRefBased(); 
    try { 
     t.insert("word1"); 
     result = t.getRootItem().getWord().equals("word1"); 
    } catch (Exception e) { 
     result = false; 
    } 
    System.out.println(message + (result ? "passed" : "FAILED")); 

    message = "Test 2: inserting 'word1', 'word2', 'word3' -- "; 
    t = new BSTRefBased(); 
    try { 
     t.insert("word1"); 
     t.insert("word2"); 
     t.insert("word3"); 
     result = t.getRootItem().getWord().equals("word1"); 
     tt = t.detachLeftSubtree(); 
     result &= tt.getRootItem().getWord().equals("word2"); 
     tt = t.detachRightSubtree(); 
     result &= tt.getRootItem().getWord().equals("word3"); 
    } catch (Exception e) { 
     result = false; 
    } 
    System.out.println(message + (result ? "passed" : "FAILED")); 

    message = "Test 3: deleting 'word1' -- "; //it then tests the delete method (note I keep getting failed for this one) 
    t = new BSTRefBased(); 
    try { 
     t.delete("word1"); 
     result = t.getRootItem().getWord().equals(null); 
    } catch (Exception e) { 
     result = false; 
    } 
    System.out.println(message + (result ? "passed" : "FAILED")); 

      message = "Test 4: deleting 'word2' 'word3' -- "; 
    t = new BSTRefBased(); 
    try { 
     t.delete("word2"); 
     t.delete("word3"); 
     result = t.getRootItem().getWord().equals(null); 
     tt = t.detachLeftSubtree(); 
     result &= tt.getRootItem().getWord().equals(null); 
    } catch (Exception e) { 
     result = false; 
    } 
    System.out.println(message + (result ? "passed" : "FAILED")); 
} 

Для моего выхода он говорит, что тест 1 прошел, но тесты 2, 3 и 4 все провалились. Итак, почему тест 2, 3 и 4 не прошел? вот что я хочу, чтобы метод удаления выглядел так:

delete(treeNode ,searchitem) 
targetNode = search(treeNode ,searchItem) 
if targetNode is null 
return 

P = parent node of target Node 

if targetNode has no children 
update ref in P that leads to targetNode 
return 

if targetNode has only one child C update ref in P that leads 
to targetNode by overwriting that ref with C 
(either left- or right-ref in P) 
return 

M = targetNode's inorder successor (i.e., left-most in-order 
successor in targetNode's right subtree) 
m = item in M 
copy m into targetNode's item field 
delete (treeNode, M) 
return 

Answer 1

Ваши тесты (за исключением теста 1) кажутся мне вялыми.

Тест 2 утверждает, что корень BST равен "word1", а левое поддерево "word2", а правое поддерево "word3". Это ... маловероятно.

Так как "word2" и "word3" приходит после"word1", ваши вставки должны производить связанный список, с "word1" в корне, "word2" как его право ребенка (и null левого ребенка), а затем "word3" в качестве правый ребенок "word2". Это не будет проходить тест 2. (я говорю «должен», потому что отдельная ошибка делает дерево еще более странным ... см. Позже в этом ответе.)

Вкратце: если ваш BST не имеет шага повторной балансировки где-то о котором вы не сказали нам, тест 2 неправ.

Тесты 3 и 4 будут никогда пас, потому что они приподнять NullPointerException каждый раз --- но вы не можете видеть его, потому что он пойман и заменяется значением false. Оба теста пытаются удалить одно или несколько слов из пустого дерева --- они не добавляют эти слова в первую очередь. Затем они звонят getRootItem, которые всегда возвращают корень null совершенно нового BST. Наконец, они убивают себя, пытаясь вызвать метод getWord по этой ссылке null.

Это не значит, что ваш BSTRefBased снят с крючка. Я заметил несколько ошибок в этом:

Ваш метод insertItem всегда добавляет к ребенку r.left, никогда r.right (опечатка). Это будет калечить ваш BST, случайно разрушая законное левое поддерево ... иногда.

И, наконец, я не уверен, что deleteItem действительно удалит элемент. Нулевой, менее чем, и больше, чем случаи выглядят нормально, но потом ...

// The "found the word" case... 
} else if(r.left != null && r.right != null){ 
    return deleteItem(r, word); 
} 

Так что, если это TreeNode имеет двое детей, он будет вызывать deleteItem с точно такими же аргументами, которые должны когда вы закончите пространство стека и потерпите крах.

Случаи, в которых есть только один ребенок или ноль детей, не обрабатываются вообще --- r (текущий TreeNode, который должен был быть удален) вместо этого возвращается, а «удаленное» слово остается в дереве ,