在BST Python中删除节点

Question

这是在Python中为BST实现添加和删除函数的一种可能方法。它有点类似于我在C++中对BST的想法。正如删除代码一样，我想删除一个节点，因为在C++中缺少Python的引用，所以我不能这么做。除了del currNode（这不起作用）之外，删除节点的另一种好方法是什么。我还有一个问题要澄清我在Python中关于引用传递的想法，当使用add函数添加节点时，当递归调用add时，它仍然“附加”到根节点。但是，当删除节点时，它不会与根节点“分离”。为什么会这样

class node(object):
    def __init__(self, data = None):
        self.data = data
        self.left = None
        self.right = None

class bst(object):
    def __init__(self):
        self.root = None
    
    def add(self, value):
        
        def _add(self, currNode, value):
            if value < currNode.data:
                if currNode.left == None:
                    currNode.left = node(value)
                else:
                    _add(self, currNode.left, value)

            elif value > currNode.data:
                if currNode.right == None:
                    currNode.right = node(value)
                else:
                    _add(self, currNode.right, value)
        
            else:
                print("Duplicate found")

        
        if self.root == None:
            self.root = node(value)
        else:
            _add(self, self.root, value)


    def printBST(self):
        def _printBST(self, currNode):
            if currNode!= None:
                _printBST(self, currNode.left)
                print(currNode.data, end = " ")
                _printBST(self, currNode.right)
        
        if self.root != None:
            _printBST(self,self.root)
    

    def minBST(self,currNode):
        def _minBST(self, currNode):
            if currNode.left == None:
                return currNode.data
            else: return _minBST(self, currNode.left)
        
        if currNode != None:
            return _minBST(self, currNode)
        else:
            return -10000
    
    def deleteValue(self, val):
        
        def deleteNode(self, currNode, value):
            if currNode == None: 
                return
            elif value > currNode.data:
                return deleteNode(self, currNode.right, value)
            elif value < currNode.data:
                return deleteNode(self, currNode.left, value)
            else:
                if currNode.left == None and currNode.right == None:
                    #del currNode
                    currNode.data = None

                elif currNode.right == None:
                    currNode.data = None
                    #The address of currNode does not change
                    #as it happens in C++
                    #currNode = currNode.left

                elif currNode.left == None:
                    currNode.data = None
                    #The address of currNode does not change
                    #currNode = currNode.right
            
                else:
                    minV = self.minBST(currNode.right)
                    currNode.data = minV
                    return deleteNode(self, currNode.right, minV)

        deleteNode(self, self.root, val)
    


if __name__ == '__main__':
    b = bst()
    b.add(50)
    b.add(60)
    b.add(40)
    b.add(30)
    b.add(45)
    b.add(55)
    b.add(100)
    b.printBST()
    b.deleteValue(100)
    print("")
    b.printBST()
 

Answer 1

节点结构和插入

我们从一个简单的node结构开始，但是请注意left和right属性可以在构造时设置-

# btree.py

class node:
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left = left
    self.right = right

递归是一种函数遗产，因此将其与函数风格结合使用会产生最好的结果。这意味着避免突变、变量重新分配和其他副作用。注意add总是构造一个新的节点，而不是变异一个旧节点。这就是我们设计node在施工时接受所有财产的原因-

# btree.py (continued)

def add(t, q):
  if not t:
    return node(q)
  elif q < t.data:
    return node(t.data, add(t.left, q), t.right)
  elif q > t.data:
    return node(t.data, t.left, add(t.right, q))
  else:
    return node(q, t.left, t.right)

顺序遍历和字符串转换

在我们创建了一些节点之后，我们需要一种可视化树的方法。下面我们编写一个inorder遍历和一个to_str函数-

# btree.py (continued)

def inorder(t):
  if not t: return
  yield from inorder(t.left)
  yield t.data
  yield from inorder(t.right)


def to_str(t):
  return "->".join(map(str,inorder(t)))

b树对象接口

请注意，我们并没有将上面的普通函数与类纠缠在一起，从而使其过于复杂。我们现在可以定义一个btree面向对象接口，它只包装普通函数-

# btree.py (continued)

class btree:
  def __init__(self, t=None): self.t = t
  def __str__(self): return to_str(self.t)
  def add(self, q): return btree(add(self.t, q))
  def inorder(self): return inorder(self.t)

注意，我们还编写了btree.py作为它自己的模块。这定义了一个抽象的障碍，并允许我们扩展、修改和重用特性，而不会将它们与程序的其他区域纠缠在一起。让我们看看到目前为止我们的树是如何工作的-

# main.py

from btree import btree

t = btree().add(50).add(60).add(40).add(30).add(45).add(55).add(100)

print(str(t))
# 30->40->45->50->55->60->100

最小值和最大值

我们将继续这样工作，定义直接作用于node对象的普通函数。接下来，minimum和maximum-

# btree.py (continued)

from math import inf

def minimum(t, r=inf):
  if not t:
    return r
  elif t.data < r:
    return min(minimum(t.left, t.data), minimum(t.right, t.data))
  else:
    return min(minimum(t.left, r), minimum(t.right, r))

def maximum(t, r=-inf):
  if not t:
    return r
  elif t.data > r:
    return max(maximum(t.left, t.data), maximum(t.right, t.data))
  else:
    return max(maximum(t.left, r), maximum(t.right, r))

btree接口只提供普通函数的包装器-

# btree.py (continued)

class btree:
  def __init__():       # ...
  def __str__():        # ...
  def add():            # ...
  def inorder():        # ...
  def maximum(self): return maximum(self.t)
  def minimum(self): return minimum(self.t)

我们现在可以测试minimum和maximum

# main.py

from btree import btree

t = btree().add(50).add(60).add(40).add(30).add(45).add(55).add(100)

print(str(t))
# 30->40->45->50->55->60->100

print(t.minimum(), t.maximum())     # <-
# 30 100

从iterable插入

链接.add().add().add()有点冗长。提供add_iter函数允许我们从另一个iterable插入任意数量的值。我们现在介绍它是因为我们也将在即将到来的remove函数中重用它-

def add_iter(t, it):
  for q in it:
    t = add(t, q)
  return t

#main.py

from btree import btree

t = btree().add_iter([50, 60, 40, 30, 45, 55, 100])   # <-

print(str(t))
# 30->40->45->50->55->60->100

print(t.minimum(), t.maximum())
# 30 100

节点删除和前序遍历

现在我们转到remove函数。它的工作原理类似于add函数，与要删除的值q执行t.data比较。您会注意到，我们在这里使用add_iter组合要删除的节点的left和right分支。我们可以在这里为我们的树重用inorder迭代器，但是preorder将使树更加平衡。这是一个完全不同的话题，所以我们现在不讨论-

# btree.py (continued)

def remove(t, q):
  if not t:
    return t
  elif q < t.data:
    return node(t.data, remove(t.left, q), t.right)
  elif q > t.data:
    return node(t.data, t.left, remove(t.right, q))
  else:
    return add_iter(t.left, preorder(t.right))

def preorder(t):
  if not t: return
  yield t.data
  yield from preorder(t.left)
  yield from preorder(t.right)

别忘了扩展btree接口-

# btree.py (continued)

class btree:
  def __init__():       # ...
  def __str__():        # ...
  def add():            # ...
  def inorder():        # ...
  def maximum():        # ...
  def minimum():        # ...
  def add_iter(self, it): return btree(add_iter(self.t, it))
  def remove(self, q): return btree(remove(self.t, q))
  def preorder(self): return preorder(self.t)

让我们看看remove现在的行动-

# main.py

from btree import btree

t = btree().add_iter([50, 60, 40, 30, 45, 55, 100])

print(str(t))
# 30->40->45->50->55->60->100

print(t.minimum(), t.maximum())
# 30 100

t = t.remove(30).remove(50).remove(100)      # <-

print(str(t))
# 40->45->55->60

print(t.minimum(), t.maximum())
# 40 60

完成的btree模块

这是我们在回答这个问题的过程中构建的完整模块-

from math import inf

class node:
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left = left
    self.right = right

def add(t, q):
  if not t:
    return node(q)
  elif q < t.data:
    return node(t.data, add(t.left, q), t.right)
  elif q > t.data:
    return node(t.data, t.left, add(t.right, q))
  else:
    return node(q, t.left, t.right)

def add_iter(t, it):
  for q in it:
    t = add(t, q)
  return t

def maximum(t, r=-inf):
  if not t:
    return r
  elif t.data > r:
    return max(maximum(t.left, t.data), maximum(t.right, t.data))
  else:
    return max(maximum(t.left, r), maximum(t.right, r))

def minimum(t, r=inf):
  if not t:
    return r
  elif t.data < r:
    return min(minimum(t.left, t.data), minimum(t.right, t.data))
  else:
    return min(minimum(t.left, r), minimum(t.right, r))

def inorder(t):
  if not t: return
  yield from inorder(t.left)
  yield t.data
  yield from inorder(t.right)

def preorder(t):
  if not t: return
  yield t.data
  yield from preorder(t.left)
  yield from preorder(t.right)

def remove(t, q):
  if not t:
    return t
  elif q < t.data:
    return node(t.data, remove(t.left, q), t.right)
  elif q > t.data:
    return node(t.data, t.left, remove(t.right, q))
  else:
    return add_iter(t.left, preorder(t.right))

def to_str(t):
  return "->".join(map(str,inorder(t)))

class btree:
  def __init__(self, t=None): self.t = t
  def __str__(self): return to_str(self.t)
  def add(self, q): return btree(add(self.t, q))
  def add_iter(self, it): return btree(add_iter(self.t, it))
  def maximum(self): return maximum(self.t)
  def minimum(self): return minimum(self.t)
  def inorder(self): return inorder(self.t)
  def preorder(self): return preorder(self.t)
  def remove(self, q): return btree(remove(self.t, q))

吃你的蛋糕，也吃它

上述方法的一个被低估的优点是，我们的btree模块有一个双接口。我们可以用传统的面向对象的方式来使用它，或我们可以用一种更功能化的方法来使用它-

# main.py

from btree import add_iter, remove, to_str, minimum, maximum

t = add_iter(None, [50, 60, 40, 30, 45, 55, 100])

print(to_str(t))
# 30->40->45->50->55->60->100

print(minimum(t), maximum(t))
# 30 100

t = remove(remove(remove(t, 30), 50), 100)

print(to_str(t))
# 40->45->55->60

print(minimum(t), maximum(t))
# 40 60

额外阅读

我已经写了大量关于这个答案中使用的技巧的文章。按照链接查看它们在其他上下文中的使用，并提供其他解释-

• I want to reverse the stack but i dont know how to use recursion for reversing this… How can i reverse the stack without using Recursion

• Finding all maze solutions with Python

• Return middle node of linked list with recursion

• How do i recursively find a size of subtree based on any given node? (BST)

Answer 2

您可以重新分配父节点并让垃圾收集器收集子节点，而不是使用del删除节点

在deleteNode中，返回新的子节点，而不是删除节点。将返回的值分配给父级

def deleteNode(self, currNode, value):
    if not currNode: 
        return currNode
    elif value < currNode.data:
        return deleteNode(self, currNode.left, value)
    elif value > currNode.data:
        return deleteNode(self, currNode.right, value)

    else: 
        if not currNode.right:
            return currNode.left

        if not currNode.left:
            return currNode.right

        temp_val = currNode.right
        mini_val = temp_val.val
        while temp_val.left:
            temp_val = temp_val.left
            mini_val = temp_val.val
        currNode.right = deleteNode(currNode.right,currNode.val)
    return currNode