在 BST Python 中删除节点 [英] Deleting node in BST Python
问题描述
这是一种在 Python 中为 BST 实现添加和删除功能的可能方法.它有点类似于我在 C++ 中对 BST 的想法.从删除代码中可以明显看出，我想删除一个节点，但由于 C++ 中存在 Python 中缺少按引用传递而无法执行此操作.除了 del currNode 之外，有什么好的替代方法可以删除节点(这不起作用).我还有一个问题要澄清我关于 Python 中按引用传递的想法，当使用 add 函数添加一个节点时，它保持附加"状态.到根节点，当 add 被递归调用时.然而，当一个节点被删除时，它并没有被分离".从根节点.为什么会这样?
this is a possible way to implement add and delete functions for a BST in Python. It somewhat resembles my ideas of BST in C++. As evident by the code for deleting, I want to delete a node, which I cannot do due to lack of pass by reference in Python as it is present in C++. What is a good alternative way to delete a node apart from del currNode(this does not work). I have one more question to clarify my idea about pass by reference in Python, when a node is being using added using add function, it remains "attached" to the root node, when add is being called recursively. However, when a node is being deleted, it is not being "detached" from the root node. Why is this so?
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()
推荐答案
节点结构与插入
我们从一个简单的node结构开始，但是注意left和right属性可以在构造的时候设置->
We start with a simple node structure, but notice the left and right properties can be set at the time of construction -
# btree.py
class node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
递归是一种函数式遗产，因此将其与函数式风格结合使用会产生最佳效果.这意味着避免诸如突变、变量重新分配和其他副作用之类的事情.注意 add 如何总是构造一个 新 节点而不是改变旧节点.这就是我们设计 node 在构造时接受所有属性的原因 -
Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutation, variable reassignment, and other side effects. Notice how add always constructs a new node rather than mutating an old one. This is the reason we designed node to accept all properties at time of construction -
# 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函数-
After we add some nodes, we need a way to visualize the tree. Below we write an inorder traversal and a to_str function -
# 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)))
btree 对象接口
请注意，我们并没有通过将它们与类纠缠在一起而使上面的普通函数过于复杂.我们现在可以定义一个 btree 面向对象的接口，它简单地包装了普通函数 -
Notice we did not over-complicate our plain functions above by entangling them with a class. We can now define a btree object-oriented interface which simply wraps the plain functions -
# 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 作为它自己的模块.这定义了抽象障碍，并允许我们扩展、修改和重用功能，而不会将它们与程序的其他区域纠缠在一起.让我们看看到目前为止我们的树是如何工作的 -
Notice we also wrote btree.py as its own module. This defines a barrier of abstraction and allows us to expand, modify, and reuse features without tangling them with other areas of your program. Let's see how our tree works so far -
# 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 -
We'll continue working like this, defining plain function that work directly on node objects. Next up, minimum and 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 接口仅提供我们普通函数的包装器 -
The btree interface provides only a wrapper of our plain functions -
# 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 -
We can test minimum and maximum now -
# 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
从可迭代对象插入
链接 .add().add().add() 有点冗长.提供一个 add_iter 函数允许我们从另一个可迭代对象插入任意数量的值.我们现在引入它是因为我们也将在即将到来的 remove 函数中重用它 -
Chaining .add().add().add() is a bit verbose. Providing an add_iter function allows us to insert any number of values from another iterable. We introduce it now because we're about to reuse it in the upcoming remove function too -
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 函数类似，执行 t.data 与要删除的值 q 的比较.您会注意到我们在这里使用 add_iter 来组合要删除的节点的 left 和 right 分支.我们可以在这里为我们的树重用 inorder 迭代器，但是 preorder 将使树更平衡一些.那是完全不同的话题，所以我们现在不讨论 -
We now move onto the remove function. It works similarly to the add function, performing a t.data comparison with the value to remove, q. You'll notice we use add_iter here to combine the left and right branches of the node to be deleted. We could reuse inorder iterator for our tree here, but preorder will keep the tree a bit more balanced. That's a different topic entirely, so we won't get into that now -
# 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 的实际效果 -
Let's see remove in action now -
# 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模块
这是我们在这个答案的过程中构建的完整模块 -
Here's the completed module we built over the course of this answer -
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 模块有一个 双 接口.我们可以像演示的那样以传统的面向对象方式使用它，或者我们可以使用更实用的方法来使用它 -
One understated advantage of the approach above is that we have a dual interface for our btree module. We can use it in the traditional object-oriented way as demonstrated, or we can use it using a more functional approach -
# 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've written extensively about the techniques used in this answer. Follow the links to see them used in other contexts with additional explanation provided -
这篇关于在 BST Python 中删除节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
