Реализация метода add для двоичного дерева поиска

Question

Мой партнер и я реализуем двоичное дерево поиска для структур данных & Алгоритмы. Мы сталкиваемся с проблемами с нашим методом add. Этот код показан ниже:

public class BinarySearchTree<Type extends Comparable<? super Type>> implements SortedSet<Type> 
{ 


BinaryNode<Type> thisRoot; 

/** 
* Constructor for this BinarySearchTree 
*/ 
public BinarySearchTree() 
{ 
    thisRoot = null; 
} 

/** 
* Adds the specified item to this BinarySearchTree, if it is 
* not already contained in this BinarySearchTree. 
* 
* @param Type item 
* 
* @return boolean 
*/ 
public boolean add(Type item) { 

    // If the specified item is null, throw an exception. 
    if(item == null) 
     throw new NullPointerException(); 

    // Otherwise, add the item. 
    return addItem(item, thisRoot); 

} 

private boolean addItem(Type item, BinaryNode<Type> thisRoot) 
{ 
    // Base case - check if thisRoot is null. If it is null, 
    // we have reached the base case where the item is not contained 
    // in this BinarySearchTree. Insert the item. 
    if(thisRoot == null) 
    { 
     thisRoot = new BinaryNode<Type>(item); 
     return true; 
    } 

    // Reduction step - recursively call the helper method until the 
    // specified item is found or added. 

    // If the item is less than the data in thisNode, then go to 
    // the left in this BinarySearchTree. 
    if(item.compareTo(thisRoot.getData()) < 0) 
     return addItem(item, thisRoot.getLeft()); 

    // If the item is greater than the data in thisNode, then go 
    // to the right in this BinarySearchTree. 
    else if (item.compareTo(thisRoot.getData()) > 0) 
     return addItem(item, thisRoot.getRight()); 
    else 
     // Item is already contained in this BinarySearchTree. 
     return false; 

} 

В нашем тестовом примере мы не получаем ожидаемого результата. Сначала мы создали пустой BinarySearchTree и вызвали метод , добавив. Отсюда мы передали метод Integer (10) в метод. После этого необходимо было вызвать метод рекурсивного метода addItem. thisRoot теперь должен ссылаться на null (поскольку мы создали пустой BinarySearchTree), и поэтому thisRoot теперь должен ссылаться на новый объект BinaryNode. Однако 10 не содержится в BST после вызова метода. thisRoot все еще указывает на null. Если у кого-то есть какие-либо предложения или соображения относительно того, почему это может быть, мы будем очень благодарны.

Answer 1

Внутри метода addItemthisRoot является локальной переменной (связанной со вторым аргументом метода). Сброс его не изменяет ничего, кроме внутри метода. Вы должны назначить new BinaryNode<Type>(item), который вы создаете либо с помощью указателя слева, либо справа от существующего узла.

(Если я размытости, это потому, что я не хочу, чтобы дать ответ прочь.)

Answer 2

Хорошая статья о BST на сайте унив Стэнфорде: http://cslibrary.stanford.edu/110/BinaryTrees.html#s1