英文:
Some nodes not being able to delete in AVL Tree in Python
问题
在删除AVL树中的节点时，只有特定的节点能够成功删除，当尝试删除其他节点时会出现AttributeError错误。以下是修复代码的建议：
首先，你的代码中存在一些 HTML 实体字符，如 "<" 和 ">"，这些应该替换为 "<" 和 ">"，以使代码正常运行。
其次，你在 delete_data 方法中的代码可能会导致错误，因为在 Python 中，无法将根节点设为 None，而应该返回新的根节点。下面是修改后的 delete_data 方法：
def delete_data(self, root_node, data):
if not root_node:
return root_node
if data < root_node.data:
root_node.left = self.delete_data(root_node.left, data)
elif data > root_node.data:
root_node.right = self.delete_data(root_node.right, data)
else:
if not root_node.left:
return root_node.right
elif not root_node.right:
return root_node.left
temp = self.get_min(root_node.right)
root_node.data = temp.data
root_node.right = self.delete_data(root_node.right, temp.data)
root_node.height = 1 + max(self.get_height(root_node.left), self.get_height(root_node.right))
balance = self.get_balance(root_node)
# Left - Left condition
if balance > 1 and self.get_balance(root_node.left) >= 0:
return self.rotate_right(root_node)
# Left - Right condition
if balance > 1 and self.get_balance(root_node.left) < 0:
root_node.left = self.rotate_left(root_node.left)
return self.rotate_right(root_node)
# Right - Right condition
if balance < -1 and self.get_balance(root_node.right) <= 0:
return self.rotate_left(root_node)
# Right - Left condition
if balance < -1 and self.get_balance(root_node.right) > 0:
root_node.right = self.rotate_right(root_node.right)
return self.rotate_left(root_node)
return root_node
以上是修复 delete_data 方法的建议，这应该可以解决你遇到的 AttributeError 问题。希望这对你有帮助！如果你还有其他问题，请随时提出。
英文:
When deleting nodes from my AVL Tree, only certain nodes are able to get deleted and when I delete those other nodes, I get AttributeError.
from collections import deque
class AVL_Tree:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1
def levelOrder_Traversal(self, root_node):
if not root_node:
return
else:
q = deque()
q.append(root_node)
while len(q) > 0:
node = q.popleft()
print(node.data)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
def get_height(self, root_node):
if not root_node:
return 0
else: return root_node.height
def get_balance(self, root_node):
if not root_node:
return 0
else:
return self.get_height(root_node.left) - self.get_height(root_node.right)
def rotate_right(self, node):
new_root = node.left
node.left = new_root.right
new_root.right = node
node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
new_root.height = 1 + max(self.get_height(new_root.left), self.get_height(new_root.right))
return new_root
def rotate_left(self, node):
new_root = node.right
node.right = new_root.left
new_root.left = node
node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
new_root.height = 1 + max(self.get_height(new_root.left), self.get_height(new_root.right))
return new_root
def insert_data(self, root_node, new_data):
if not root_node:
return AVL_Tree(new_data)
elif new_data < root_node.data:
root_node.left = self.insert_data(root_node.left, new_data)
else:
root_node.right = self.insert_data(root_node.right, new_data)
root_node.height = 1 + max(self.get_height(root_node.left), self.get_height(root_node.right))
balance = self.get_balance(root_node)
# left - left condition
if balance > 1 and new_data < root_node.left.data:
return self.rotate_right(root_node)
# left - right condition
if balance > 1 and new_data > root_node.left.data:
root_node.left = self.rotate_left(root_node.left)
return self.rotate_right(root_node)
# right - right condition
if balance < -1 and new_data > root_node.right.data:
return self.rotate_left(root_node)
# right - left condition
if balance < -1 and new_data < root_node.right.data:
root_node.right = self.rotate_right(root_node.right)
return self.rotate_left(root_node)
return root_node
def get_min(self, root_node):
current = root_node
while current:
current = current.left
return current
def delete_data(self, root_node, data):
if not root_node:
return root_node
if data < root_node.data:
root_node.left = self.delete_data(root_node.left, data)
elif data > root_node.data:
root_node.right = self.delete_data(root_node.right, data)
else:
if not root_node.left:
temp = root_node.right
root_node = None
return temp
elif not root_node.right:
temp = root_node.left
root_node = None
return temp
temp = self.get_min(root_node.right)
root_node.data = temp.data
root_node.right = self.delete_data(root_node.right, temp.data)
root_node.height = 1 + max(self.get_height(root_node.left), self.get_height(root_node.right))
balance = self.get_balance(root_node)
# Left - Left condition
if balance > 1 and self.get_balance(root_node.left) >= 0:
return self.rotate_right(root_node)
# Left - Right condition
if balance > 1 and self.get_balance(root_node.left) < 0:
root_node.left = self.rotate_left(root_node.left)
return self.rotate_right(root_node)
# Right - Right condition
if balance < -1 and self.get_balance(root_node.right) <= 0:
return self.rotate_left(root_node)
# Right - Left condition
if balance < -1 and self.get_balance(root_node.right) > 0:
root_node.right = self.rotate_right(root_node.right)
return self.rotate_left(root_node)
return root_node
avl = AVL_Tree(30)
avl = avl.insert_data(avl, 25)
avl = avl.insert_data(avl, 35)
avl = avl.insert_data(avl, 20)
avl = avl.insert_data(avl, 15)
avl = avl.insert_data(avl, 5)
avl = avl.insert_data(avl, 10)
avl = avl.insert_data(avl, 50)
avl = avl.insert_data(avl, 60)
avl = avl.insert_data(avl, 70)
avl = avl.insert_data(avl, 65)
print("AVL Tree before deletion:")
avl.levelOrder_Traversal(avl)
print("\nAVL Tree after deleting data:")
avl = avl.delete_data(avl, 30)
avl.levelOrder_Traversal(avl)
In those nodes [ 20, 10, 50, 5, 15, 30, 65, 25, 35, 60, 70 ],
[ 20, 10, 50, 30, 65 ] ---> these five nodes raise AttributeError when I try to delete them.
I am self-studying data structures so I have no mentors or teachers to ask when I have problems. I tried chatgpt and google but I can't find answer for specific questions like this. So, I'm here asking for how I should fix my code.
I'd really appreciate if you guys can help me out. Thanks a lot!!!
答案1
得分: 1
问题出在你的get_min方法上：它返回了你要查找的节点的左子节点，但是它是空的！你可以非常简单地修复它：
def get_min(self, root_node):
current = root_node
while current.left:
current = current.left
return current
通过这个修复，30节点将被正确删除，并且生成的树的遍历是正确的：
20 , 10 50, 5 15 35 65, - - - - 25 - 60 70
（-添加以更好地看到树的结构）
英文:
The problem comes for your get_min method: it returns the left child of the node you seek, which is None! You can fix it very simply:
def get_min(self, root_node):
current = root_node
while current.left:
current = current.left
return current
With this fix, the 30 node is correctly deleted, and the traversal of the resulting tree is correct:
20 , 10 50, 5 15 35 65, - - - - 25 - 60 70
(- added to better see the tree structure)
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论