我正在尝试遵循Granville Barnett 的“数据结构和算法”中的 BST 算法,但我不理解它在下面描述的节点删除算法。
第 3.3 节(第 22 页)
从 BST 中删除节点相当简单,需要考虑四种情况:
- 要删除的值是叶节点;或者
- 要删除的值有一个右子树,但没有左子树;或者
- 要删除的值有一个左子树,但没有右子树;或者
- 要删除的值同时具有左子树和右子树,在这种情况下,我们提升左子树中的最大值。
图 3.2(第 22 页)
23
/ \
14 31
/
7
\
9
- 案例 #1 指向节点 9。
- 案例 #2 指向节点 7。
- 案例 #3 指向节点 14。
- 案例 #4 指向节点 23。
我将上面 #4 的文本解释为,当我们删除 23 时,我们将 14 提升为 root 并使 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。为什么该算法会使父节点的右孩子无效?
为什么第 13 行将largestValueNode
' 值复制到要删除的节点中?
我预计第 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}