英文:
How to remove the smallest element in a Binary Search Tree in python?
问题
使用递归，我被要求创建一个用于在Python中移除BST的最小元素的方法。我不能使用已经实现的 remove 函数。我尝试了几次使用类似的代码，甚至复制和编辑 remove 函数，但最小的节点并没有被移除。
有谁可以帮助我？
请注意，原始树没有 self.parent 节点，只有 self.elem、self.right 和 self.left。我已经尝试了几种方法。不过，我将展示我不明白为什么这段代码不起作用的部分。
# this method is used for removing the smallest value in the tree
def removeSmallest(self):
return self._removeSmallest(self._root)
def _removeSmallest(self, node):
if node is None:
return 0
while node.left is not None:
node = node.left
return node
根据我的 remove 函数的代码，它使用了返回的 node 来删除那个节点，我不明白为什么这不起作用。请注意，我已经实现了一个用于找到最小元素的代码（它有效）。感谢帮助。
英文:
Using recursion, I am asked to create a method for removing the smallest element of a BST in Python. I cannot use the already implemented function remove. Have tried several times with similar codes, even copying and editing the remove function. However, the smallest node it is not removed.
Can anyone help me with this?
Knowing that the original tree has no self.parent node, just self.elem, self.right and self.left I have try several things. However, I will show the one that I don't understand why the code is not working.
# this method is used for removing the smallest value in the tree
def removeSmallest(self):
return self._removeSmallest(self._root)
def _removeSmallest(self, node):
if node is None:
return 0
while node.left is not None:
node = node.left
return node
Following the code of my remove function, which used the return node in order to delete that node, I don't understand why this doesn't work. Notice that I have implemented a code for knowing the minimum element (that works). Thanks for the help.
答案1
得分: 0
一些问题：
-
不建议使用
return 0：最好在没有要删除的内容时返回None。这在递归调用中可能会有用（继续阅读） -
当你的
while循环结束时，你位于必须删除的节点，但之后你仍然需要设置父节点的left属性，而此时你已经失去了对该节点的引用。你可以通过递归来解决这个问题。 -
你的代码中没有提供修改
_root引用的方法。然而，很可能树的根节点具有最小的值（当它没有左子节点时）。
你可以使用你提到的返回节点实例的想法，但不要返回需要删除的节点，而是应该被移动到其位置（如果有的话）或返回 None 的节点。然后函数的 调用者 可以使用返回的节点实例将其附加到仍然具有父节点的节点上。
以下是如何实现的代码：
def removeSmallest(self):
if self._root:
self._root = self._removeSmallest(self._root)
def _removeSmallest(self, node):
if node.left:
node.left = self._removeSmallest(node.left)
return node
else:
return node.right
英文:
A few issues:
-
return 0is not advised: it is better to returnNonewhen there is nothing to delete. This can be useful in recursive calls (read on) -
When your
whileloop finishes, you are at the node that must be deleted, but you then need to still set theleftattribute of the parent, while you have lost the reference to that node. You can solve this with recursion. -
There is no provision in your code to alter the
_rootreference. Yet, it could well be that the root of the tree has the smallest value (when it has noleftchild.
You could use the idea you had to return a node instance, but don't return the node that needs to be deleted, but the node that should moved upwards to take its place (if any) or None. Then the caller of the function can use the returned node instance to attach it to the parent node that it still has.
Here is how it can work:
def removeSmallest(self):
if self._root:
self._root = self._removeSmallest(self._root)
def _removeSmallest(self, node):
if node.left:
node.left = self._removeSmallest(node.left)
return node
else:
return node.right
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论