使用递归从二叉搜索树中删除节点 [英] removing a node from a binary search tree using recursion
问题描述
我正在使用以下代码:
import random
from time import time
class BinaryNode:
def __init__(self, value = None):
"""Create binary node"""
self.value = value
self.left = None
self.right = None
def add(self, val):
"""Adds a new node to the tree containing this value"""
if val <= self.value:
if self.left:
self.left.add(val)
else:
self.left = BinaryNode(val)
else:
if self.right:
self.right.add(val)
else:
self.right = BinaryNode(val)
def delete(self):
"""
Remove value of self from BinaryTree. Works in conjunction with remove
method in BinaryTree
"""
if self.left == self.right == None:
return None
if self.left == None:
return self.right
if self.right == None:
return self.left
child = self.left
grandchild = child.right
if grandchild:
while grandchild.right:
child = grandchild
grandchild = child.right
self.value = grandchild.value
child.right = grandchild.left
else:
self.left = child.left
self.value = child.value
return self
class BinaryTree:
def __init__(self):
"""Create empty binary tree"""
self.root = None
def add(self, value):
"""Insert value into proper location in Binary Tree"""
if self.root is None:
self.root = BinaryNode(value)
else:
self.root.add(value)
def contains(self, target):
"""Check whether BST contains target value"""
node = self.root
while node:
if target == node.value:
return True
if target < node.value:
node = node.left
else:
node = node.right
return False
def remove(self, value):
"""Remove value from tree"""
if self.root:
self.root = self.removeFromParent(self.root, value)
def removeFromParent(self, parent, value):
"""remove value from tree rooted at parent"""
if parent is None:
return None
if value == parent.value:
return parent.delete()
elif value < parent.value:
parent.left = self.removeFromParent(parent.left, value)
else:
parent.right = self.removeFromParent(parent.right, value)
return parent
可在此处找到:我的问题如下.鉴于我想从中删除节点14:
My problem is as follows. Given I want to remove node 14 from this:
我希望它在左节点树中找到最大值，在这种情况下为13.然后我希望值14的节点现在包含值13，应该从节点树中删除值13的节点.
I expect it to find the largest value in the left nodetree, which in this case is 13. Then I expect that node with value 14 to now contain value 13, and that node with value 13 should be removed from the node tree.
但是，我看不到上面复制的代码是如何做到的.首先，我们将值14传递给remove函数.我们将根节点(8)和值14传递给remove_from_parent函数.由于该值大于父项的值，因此我们递归调用remove_from_parent来传递正确的子项(10)和值14.由于该值再次大于父项的值，因此我们再次调用remove_from_parent传递正确的子项(14).和值14.现在我们有一个相等的匹配项，因此我们调用parent.delete返回左节点(13).因此，现在调用堆栈具有三个递归迭代，在最后一个序列中它返回具有13的节点，在先前序列中它返回具有10的节点，而初始序列它返回具有8的节点.因此，由于初始调用执行了以下操作:@root = remove_from_parent (@root，值)，我假设@root现在是具有值13的节点，毕竟，我们正在执行赋值"="，因此递归中的最后一个调用将覆盖其他节点.但是这里似乎有些问题.因为具有13的节点不是根.值为8的节点是根.我想念什么?
However, I don't see how the code I copied above is doing that. First, we pass value 14 to the remove function. We pass the root node (8) and the value 14 to the remove_from_parent function. Since the value is greater than the parent's value, we call remove_from_parent recursively passing in the right child (10) and the value 14. Since the value is greater than the parent's value again, we call remove_from_parent again passing in the right child (14) and the value 14. Now we have an equal match, so we call parent.delete which returns the left node (13). So now the callstack had three recursive iterations, in the last sequence it returns node with 13, in previous sequence it returns node with 10 and the initial sequence it returned node with 8. So since the initial call did the following: @root = remove_from_parent(@root, value), I assume @root is now the node with value 13, after all, we are doing assignment "=" so the last call in the recursion overwrites the others. But something seems wrong here. Because node with 13 is not the root. Node with value 8 is the root. What am I missing?
推荐答案
在最后一步(到达节点14时)，您将返回"delete"的输出，该输出将要删除的节点替换为一个它的孩子，并返回其父母.这意味着节点10将被返回，并且最终也将返回其自己的父节点(即节点8).
At the very last step (when you come to node 14) you get back the output of "delete" which substitutes the to-be-deleted node with one of its children and returns its parent. That means, the node 10 will be returned, and eventually its own parent as well (i.e. node 8).
更新(仔细看了一些令人困惑的命名之后):删除"的作用是用一个子项(在本例中为13)替换节点值(在您的情况下为14).然后，它返回修改后的节点(13).现在请记住，此调用是从先前的迭代中进行的，返回的结果将只是父节点之一的子代的新值(将返回到先前的调用).最终，您将获得第一个以root开头的呼叫.
UPDATE (after looking closer at a bit confusing naming): what "delete" does is substituting the node value (in your case, 14) with one of the children (in this case, 13). Then it returns back the modified node (13). Now remember that this call was made from the previous iteration, and the returned result will simply be the new value for one of the children of the parent node (which will be returned to the previous call). Eventually you'll get to the first call which started with the root.
(对我而言)命名的混乱来自父母"一词，实际上是节点本身.
The confusion in the naming (for me) comes from the word "parent" which actually means node itself.
更新2:removeFromParent执行以下操作之一:
UPDATE 2: removeFromParent does one of the following things:
-
如果在其上被调用的节点为None，则返回None.
if the node on which it was called, was None, it returns None.
如果在其上被调用的节点具有要删除的值，则它返回删除"的结果，如果该节点没有子节点，则该结果仅将返回None；否则将返回带有值左右移动(节点值替换为分支之一).
if the node on which it was called, had the value to be removed, it returns the result of "delete" which will only return None if that node had no children, otherwise it will return the node with the values shifted around (node value substituted with one of the branches).
否则，它将更改节点的子节点之一并返回该节点.
otherwise, it changes one of the node's children and returns the node.
到达节点10时，将发生以下情况:返回具有修改后的左分支的节点10(它将存储"delete"(即13)返回的结果).其余的只是在冒泡.
When you get to node 10, this is exactly what will happen: it returns node 10, with the modified left branch (which will store the result returned by "delete", i.e. 13). the rest is simply bubbling up.
这篇关于使用递归从二叉搜索树中删除节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
