为什么在删除单个子节点的情况下parent.right=self.right不足以删除节点

Question

我正在实现删除 BST（二叉搜索树）中的节点，这是我的代码

class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        if self is None:
            self = BST(value)
        if value < self.value:
            if self.left is not None:
                self.left.insert(value)
            else: 
                self.left = BST(value)
        if value >= self.value:
            if self.right is not None:
                self.right.insert(value)
            else: 
                self.right = BST(value)
        return self

    def contains(self, value):
        if self == None:
            return False
        if self.value == value:
            return True
        if value < self.value:
            if self.left is not None:
                return self.left.contains(value)
        if value > self.value:
            if self.right is not None:
                return self.right.contains(value)
        return False

   def remove(self, value, parent=None):
        if self is None:
            return self
        elif value < self.value:
            if self.left is not None:
                self.left.remove(value,self)
        elif value > self.value:
            if self.right is not None:
                self.right.remove(value,self)
        elif value == self.value:
            if self.right is None and self.left is None:
                if parent is None:
                    pass
                else:
                    if parent.left == self:
                        parent.left = None
                    if parent.right == self:
                        parent.right = None
            elif self.right is None:
                if parent is None:
                    self = self.left
                else:
                    if parent.left == self:
                        parent.left = self.left
                    if parent.right == self:
                        parent.right = self.left
            elif self.left is None:
                if parent is None:
                    self = self.right
                else:
                    if parent.left == self:
                        parent.left = self.right
                    if parent.right == self:
                        parent.right = self.right
            elif self.right is not None and self.left is not None:
                sub = self.right.minguy()
                self.value = sub
                self.right.remove(sub,self)
                pass
        return self

    def minguy(self):
        while (self.left is not None):
            self = self.left
        return self.value

考虑 1->2->3->4 的情况，我们必须删除 1。为什么简单地 self = self.right 不能完成删除工作？我缺少什么？任何帮助表示赞赏

我期望 2 是根，1 不存在，期望 2->3->4

具体是这段代码

        elif self.left is None:
            if parent is None:
                self = self.right
            else:
                if parent.left == self:
                    parent.left = self.right
                if parent.right == self:
                    parent.right = self.right

import program
import unittest


BST = program.BST


class TestProgram(unittest.TestCase):
    def test_case_1(self):
        root = BST(1)
        root.insert(2)
        root.insert(3)
        root.insert(4)
        root.remove(1)

        self.assertTrue(not root.contains(1))
        self.assertTrue(root.value == 2)

        self.assertTrue(root.contains(3))

Answer 1

为什么简单地

self = self.right

不能完成移除工作？

这确实是问题核心的陈述。

self

是本地名称，因此

self =

只为该本地名称分配一些内容。名称分配永远不会改变你的树。要改变树，您需要分配给attributes，而不是names。

快速解决方案

在特殊情况下，您需要删除根节点（并且没有要更改其

parent

或

left

属性的

right

节点），并且该根只有一个子节点，您必须意识到这一点您无法更改呼叫者的

root

姓名所指的内容。无论你做什么，调用者的

root

仍然会引用原始根节点。所以你必须更新根节点的属性。

至少有两种方法可以做到这一点：

• 要么当节点只有右子节点时也应用

  minguy

  逻辑，并且当节点只有左子节点时执行“镜像”操作（即实现

  maxguy

  ），或者...

• 覆盖根的all属性（

  left

  、

  right

  和

  value

  ），使其成为其唯一子节点的副本。该子节点因此断开连接，因此被删除，而不是根节点。

这是您需要更改实施第二个想法的内容：

首先添加一个辅助方法以从另一个节点获取副本：

    def copy_from(self, other):
        self.value = other.value
        self.left = other.left
        self.right = other.right

然后替换这个：

self = self.left

...与：

self.copy_from(self.left)

并替换：

self = self.right

...与：

self.copy_from(self.right)

这将解决您的问题。

备注

• 您有测试

  self

  是否为

  None

  的代码，但是当您的方法作为方法调用时，这种情况永远不会发生。我想测试套件不会以其他方式调用这些函数。

• elif self.right is not None and self.left is not None:

  ——这是在所有先前条件之后剩下的唯一情况，所以这可能只是一个

  else:

• 处理节点时，无需显式与

  None

  进行比较。你可以做

  if self.left:

  和

  if not self.left:

  ，...等等

• 如果允许

  remove

  返回一个节点，那么你可以不使用

  parent

  参数来实现，从而简化了代码：

      def remove(self, value):
          if value < self.value:
              if self.left:
                  self.left = self.left.remove(value)
          elif value > self.value:
              if self.right:
                  self.right = self.right.remove(value)
          elif value == self.value:
              if not self.right and not self.left:
                  return None
              elif not self.right or not self.left:
                  self.copy_from(self.left or self.right)
              else:
                  self.value = self.right.minguy()
                  self.right = self.right.remove(self.value)
          return self
  

• 关于代码挑战，我必须说这是一个低劣的挑战。它说“你不能从单节点树中删除值”。这当然是无稽之谈，其灵感来自于对如何实现树的有限愿景。它们迫使您进行某种实现，其中必须立即用一个值初始化树，这是因为它们在节点的概念和树的概念之间没有区别。然而，还是有区别的。空树的概念是存在的，而且我们确实没有充分的理由不能表示一棵空树，或者为此创建一棵空树。

  实现树的更好方法是区分节点和树的概念。两者都值得一堂课。但它不适用于他们准备的那种测试，因此他们实施了较差的设计。