2

Granville Barnettの「DataStructuresandAlgorithms」のBSTアルゴリズムに従おうとしていますが、以下で説明するノード削除アルゴリズムがわかりません。

セクション3.3（p。22）

BSTからノードを削除するのはかなり簡単で、次の4つのケースを考慮する必要があります。

  1. 削除する値はリーフノードです。また
  2. 削除する値には右側のサブツリーがありますが、左側のサブツリーはありません。また
  3. 削除する値には左側のサブツリーがありますが、右側のサブツリーはありません。また
  4. 削除する値には、左と右の両方のサブツリーがあります。この場合、左のサブツリーで最大の値を昇格させます。

図3.2（p。22）

    23
   /  \
  14   31
 /
7
 \
  9
  • ケース＃1はノード9を指します。
  • ケース＃2はノード7を指しています。
  • ケース＃3はノード14を指しています。
  • ケース＃4はノード23を指しています。

上記の＃4のテキストは、23を削除すると、14をルートに昇格させ、31を正しい子にすることを意味すると解釈します。

  14
 /  \
7   31
 \
  9

...しかし、ケース＃4の本のアルゴリズム（23ページから）は私を悩ませます（私はここでJavaで書き直しました）：

1 boolean remove(T value) {
2   // ...
3
4   // case #4
5   Node largestValueNode = nodeToRemove.left;
6   while (largestValueNode.right != null) {
7       // find the largest value in the left subtree of nodeToRemove
8       largestValueNode = largestValueNode.right;
9   }
10  
11  // delete the right child of largestValueNode's parent
12  findParent(largestValueNode.value).right = null;
13  nodeToRemove.value = largestValueNode.value;
14  
15  count--;
16  return true; // successful
17}

アルゴリズムに従うと、largestValueNodeはノード14なので、その親はノード23になります。なぜアルゴリズムは親の正しい子を無効にするのですか？

largestValueNode13行目がの値を削除するノードにコピーするのはなぜですか？

11〜13行目は次のようになると思います。

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

編集：

この本のアルゴリズムには確かにバグがあります。修正は以下のとおりです。

1 boolean remove(T value) {
2   // ...
3
4   // case #4
5   Node largestValueNode = nodeToRemove.left;
6   while (largestValueNode.right != null) {
7       // find the largest value in the left subtree of nodeToRemove
8       largestValueNode = largestValueNode.right;
9   }
10  
11  Node p = findParent(largestValueNode.value);
12  if (p != null) {
13      if (nodeToRemove == p)
14          nodeToRemove.left = largestValueNode.left;
15      else
16          p.right = largestValueNode.left;
17  }
18  nodeToRemove.value = largestValueNode.value;
19  
20  count--;
21  return true; // successful
22}
4

4 に答える 4

3

あなたがこれをするなら

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行目でlargestValueNodeの値を削除するノードにコピーするのはなぜですか？」と答えます。

を削除します。largestValueNodeその前に、その値をに保存します。nodeToRemove

于 2012-07-08T00:01:58.440 に答える
1

この特定の例では、本のアルゴリズムが間違っているようです（Javaに完全に翻訳したと仮定します:)）。それはあなたが言ったことをやっていますが、それはその場合に正しいです：

ここで、nodeToRemove = 23であり、BST 14には右の子15があります。本のアルゴリズムはここで23を15に置き換え、14の右の子をnullに設定します。この場合、アルゴリズムは失敗します。

于 2012-07-08T00:10:09.053 に答える
0

次の行を注意深く見てください。

largestValueNode.right = nodeToRemove.right;

この行がどの14ようにこのように見えるかに注意してください（孫を無視します）：

  14
 /  \
7   31

しかし、これはまさに望ましいことです！14現在は右の子としてを持っているため、の右の子になることは31正しくありません。したがって、クリーンアップのために、の右の子はNULLに設定されます。311515

于 2012-07-08T00:17:34.720 に答える
0

元のコードが間違っていることを知っておくとよいでしょう-私はそれに数時間を費やしたばかりで、何かが足りないとずっと考えていました。ルート要素が渡された場合は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();
} */
}
于 2014-02-15T21:58:13.677 に答える