Как работает этот алгоритм удаления узла BST?

если ты сделаешь это

11  if (largestValueNode != null)
12      largestValueNode.right = nodeToRemove.right;
13  nodeToRemove.right = null;

вы не рассматриваете случай, когда у 14 может быть правильный ребенок. Например:

     23
    / \
   14  31
  / \
 7   15
  \
   9

Ваше решение при удалении 23 должно быть

     15
    / \
   14  31
  / 
 7  
  \
   9

Итак, вы устанавливаете для правого дочернего элемента исходного родителя 15 14 значение null. Это то, что делает первый код.

Изменить: обращение к вашему комментарию

С вашим решением вы получите

     23
    / 
   14  
  / \
 7   15
  \   \
   9   31

Кроме того, исходный код также неверен; попробуйте что-нибудь вроде этого:

if(nodeToRemove == findParent(largestValueNode.value))
   nodeToRemove.left = largestValueNode.left
else
   findParent(largestValueNode.value).right = largestValueNode.left
nodeToRemove.value = largestValueNode.value

Также для ответа: «Почему строка 13 копирует значение самого большогоValueNode в удаляемый узел?»

Мы удаляем largestValueNode, а перед этим сохраняем его значение в nodeToRemove

Похоже, алгоритм книги неверен для этого конкретного примера (при условии, что вы отлично перевели на Java :)). Он делает то, что вы упомянули, но это правильно для случая:

где nodeToRemove = 23, а в вашем BST 14 был правый дочерний элемент 15. Алгоритм книги заменит 23 здесь 15 и установит для правого дочернего элемента 14 значение null. В этом случае ваш алгоритм не сработает.

Внимательно посмотрите на строку:

largestValueNode.right = nodeToRemove.right;

Обратите внимание, как эта строка заставляет 14 выглядеть следующим образом (без учета внуков):

  14
 /  \
7   31

Но это именно то, что нужно! Поскольку 14 теперь имеет 31 в качестве своего правого дочернего элемента, для 31 больше не правильно быть правым дочерним элементом 15, поэтому для очистки правый дочерний элемент 15 устанавливается в NULL.

Приятно знать, что исходный код неверен - я только что потратил на это несколько часов и все время думал, что мне что-то не хватает. Возникает проблема NPE, если корневой элемент передан, и в любом случае удаление корневого элемента не учитывается.

Вот моя реализация Java, которая, вероятно, нуждается в некоторой оптимизации - предложения приветствуются. O (n log n) худший случай. Тесты ниже.

public boolean remove(final T value0) {
    BinarySearchTreeNode<T> target = findNode(value0);

        // Node DNE
        if (target == null) {
            return false;
        }

        // Both children populated, no need for parent
        if (target.right != null && target.left != null) {
            BinarySearchTreeNode<T> max = maxChild(target.left);
            findParent(max.value).right = null;
            target.value = max.value;
        }
        // Root element targeted, parent DNE
        else if (target == root) {
            if (target.right == null && target.left == null) {
                root = null;
            }
            else if (target.right == null) {
                root = target.left;
            }
        else {
            root = target.right;
        }
    }
    // Non-root, single-child node - find if L or R child, update parent reference.
    else {
        BinarySearchTreeNode<T> parent = findParent(value0);

        if (target.right == null && target.left != null) {
            if (target.value.compareTo(parent.value) < 0) {
                parent.left = target.left;
            }
            else {
                parent.right = target.left;
            }
        }
        else if (target.right != null && target.left == null) {
            if (target.value.compareTo(parent.value) < 0) {
                parent.left = target.right;
            }
            else {
                parent.right = target.right;
            }
        }
    }       

    return true;
}

Модульные тесты (все проходят, очевидно):

package BinarySearchTreeTests;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;

import org.junit.Before;
import org.junit.Test;

public class Remove {
    BinarySearchTree<Integer> tree;

@Before
public void setUp() {
    tree = new BinarySearchTree<Integer>();
}

@Test
public void fromEmptyTree() {
    assertFalse(tree.remove(8));
}

@Test
public void fromTreeWithOnlyRootNode() {
    tree.add(10);
    assertTrue(tree.remove(10));
    assertNull(tree.root);
}

@Test
public void nonexistentElement() {
    tree.add(10);
    assertFalse(tree.remove(8));
}

/**
 *     N
 * 10--|
 *     |  6
 *     5--|
 *        3
 */
@Test
public void nodeWithNoRightChildren() {
    tree.add(10);
    tree.add(5);
    tree.add(6);
    tree.add(3);
    tree.remove(10);
    assertEquals(tree.root.value, Integer.valueOf(5));
    assertEquals(tree.root.left.value, Integer.valueOf(3));
    assertEquals(tree.root.right.value, Integer.valueOf(6));
}

/**
 *         17
 *     15--|
 *     |   13
 * 10--|
 *     N
 */
@Test
public void nodeWithNoLeftChildren() {
    tree.add(10);
    tree.add(15);
    tree.add(17);
    tree.add(13);
    tree.remove(10);
    assertEquals(tree.root.value, Integer.valueOf(15));
    assertEquals(tree.root.left.value, Integer.valueOf(13));
    assertEquals(tree.root.right.value, Integer.valueOf(17));
}

/**
 *           19
 *        17-|
 *        |  16
 *     15-|
 *     |  |  14
 *     |  13-|
 *     |     12
 * 10--|
 *     N
 */       
@Test
public void nodeWithLeftAndRightChildren() {
    tree.add(10);
    tree.add(15);
    tree.add(17);
    tree.add(13);
    tree.add(19);
    tree.add(16);
    tree.add(14);
    tree.add(12);

    tree.remove(15);
    assertEquals(tree.root.right.value, Integer.valueOf(14));
    assertNull(tree.root.right.left.right);
}

/**
 *           18
 *        15-|
 *        |  [ALWAYS EMPTY]
 *     15-|
 *     |  |  13
 *     |  12-|
 *     |     11
 * 10--|
 *     N
 * 
@Test
public void removeDuplicate() {
    Above diagram shows duplicate cases are already tested implicitly.
    fail();
} */
}