метод удаления из бинарного дерева не работает
Помогите кто-нибудь найти ошибку в коде, не могу понять почему он не работает. Точнее, после удаления нескольких элементов дерево линкуется неправильно и потом выкидывает NullPointerException(), потому что не может найти элемент (который в дереве точно есть).
// в коде: .next - право, .prev - лево
Алгоритм:
Если дерево T пусто, остановиться;
Иначе сравнить K с ключом X корневого узла n.
Если K>X, рекурсивно удалить K из правого поддерева Т;
Если K<X, рекурсивно удалить K из левого поддерева Т;
Если K=X, то необходимо рассмотреть три случая.
Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла;
Если одного из детей нет, то значения полей ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m;
Если оба ребёнка присутствуют, то найдём узел m, являющийся самым левым узлом правого поддерева с корневым узлом Right(n);
скопируем данные (кроме ссылок на дочерние элементы) из m в n; рекурсивно удалим узел m.
сам код:
public void remove(T t) {
Node<T> curr, replacement;
Node<T> newItem = new Node<T>(t);
lock.lock();
curr = tree;
try {
if (curr.item != null) {
while (curr.compareTo(newItem) != 0) {
if (curr.compareTo(newItem) == 1) {
curr = curr.next;
}
else {
curr = curr.prev;
}
}
if (curr.next == null && curr.prev == null) {
curr = null;
}
else if (curr.next == null) {
curr.item = curr.prev.item;
curr.prev = null;
}
else if (curr.prev == null) {
curr.item = curr.next.item;
curr.next = null;
}
else {
replacement = curr.next;
if (replacement.prev != null && replacement.next != null) {
replacement = replacement.prev;
Node<T> link = curr.next;
while (replacement.prev != null) {
link = replacement;
replacement = replacement.prev;
}
curr.item = replacement.item;
if (replacement.next != null) {
link.prev = replacement.next;
} else {
replacement = null;
}
}
else if (replacement.next != null) {
curr.item = replacement.item;
curr.next = curr.next.next;
} else {
curr.item = replacement.item;
curr.next = null;
}
}
} catch (UnsupportedOperationException e) {
throw new UnsupportedOperationException();
} finally {
lock.unlock();
}
}