Generi c бинарное дерево поиска неправильно добавляет новые узлы (Java)

Question

Я пишу двоичное дерево поиска в java с обобщенными c классами, но узлы добавляются неправильно, и я не могу понять, почему.

Вот мой метод вставки ( повторяющийся):

public void insert (E element){
    //iterative insert element to tree

    Node<E> node = new Node<>(element); //create new node for element
    Node<E> current = root;

    if (root == null) root = node; // if no root, new node is the root

    else {
        while (current != null){ //traverse tree to get to correct parent node

            if (element.compareTo(current.data) < 0) { //case 1: node is smaller than current
                if (current.left == null){ 
                    node.parent = current;
                    current.left = node;
                }
                else {
                    current = current.left;
                }
            }
            else if (element.compareTo(current.data) > 0) { //case 2: node is larger than current
                if (current.right == null){
                    node.parent = current;
                    current.right = node;
                }
                else {
                    current = current.right;
                }
            }
            else { //case 3: node already exists
                throw new RuntimeException("Node already exists");
            }
        }
    }
    size++;
}

проблема возникает, когда я запускаю свой тестовый класс. там первый узел добавляется и становится root, но следующая вставка после этого вызывает исключение независимо от значения. Он действует как значение, которое я пытаюсь добавить, уже существует в дереве. Если я закомментирую исключение, тестовый класс не скомпилируется, как если бы он выполнял бесконечный l oop.

Что я здесь не так делаю?

Answer 1

Как бы ток стал нулевым в вашем, пока l oop?

Вы не выйдете из своего времени l oop, даже когда вставляете новый элемент:

if (current.left == null) { 
  node.parent = current;
  current.left = node;
}

На следующей итерации вы присваиваете current только что вставленное значение в current.left:

} else {
  current = current.left;
}

и все же на следующей итерации у вас теперь есть current.data, равный element, что приводит к исключению. Добавьте break; после вставки элемента:

if (current.left == null) { 
  node.parent = current;
  current.left = node;
  break;
}