在Python中的AVL树中，有些节点无法删除。

huangapple
go评论89阅读模式
英文:

Some nodes not being able to delete in AVL Tree in Python

问题

在删除AVL树中的节点时，只有特定的节点能够成功删除，当尝试删除其他节点时会出现AttributeError错误。以下是修复代码的建议：

首先，你的代码中存在一些 HTML 实体字符，如 "<" 和 ">"，这些应该替换为 "<" 和 ">"，以使代码正常运行。

其次，你在 delete_data 方法中的代码可能会导致错误，因为在 Python 中，无法将根节点设为 None，而应该返回新的根节点。下面是修改后的 delete_data 方法：

  1. def delete_data(self, root_node, data):
  2.     if not root_node:
  3.         return root_node
  5.     if data < root_node.data:
  6.         root_node.left = self.delete_data(root_node.left, data)
  7.     elif data > root_node.data:
  8.         root_node.right = self.delete_data(root_node.right, data)
  9.     else:
  10.         if not root_node.left:
  11.             return root_node.right
  12.         elif not root_node.right:
  13.             return root_node.left
  15.         temp = self.get_min(root_node.right)
  16.         root_node.data = temp.data
  17.         root_node.right = self.delete_data(root_node.right, temp.data)
  19.     root_node.height = 1 + max(self.get_height(root_node.left), self.get_height(root_node.right))
  20.     balance = self.get_balance(root_node)
  22.     # Left - Left condition
  23.     if balance > 1 and self.get_balance(root_node.left) >= 0:
  24.         return self.rotate_right(root_node)
  26.     # Left - Right condition
  27.     if balance > 1 and self.get_balance(root_node.left) < 0:
  28.         root_node.left = self.rotate_left(root_node.left)
  29.         return self.rotate_right(root_node)
  31.     # Right - Right condition
  32.     if balance < -1 and self.get_balance(root_node.right) <= 0:
  33.         return self.rotate_left(root_node)
  35.     # Right - Left condition
  36.     if balance < -1 and self.get_balance(root_node.right) > 0:
  37.         root_node.right = self.rotate_right(root_node.right)
  38.         return self.rotate_left(root_node)
  40.     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.

  1. from collections import deque
  3. class AVL_Tree:
  4.     def __init__(self, data):
  5.         self.data = data
  6.         self.left = None
  7.         self.right = None
  8.         self.height = 1
  10.     def levelOrder_Traversal(self, root_node):
  11.         if not root_node:
  12.             return
  13.         else:
  14.             q = deque()
  15.             q.append(root_node)
  16.             while len(q) &gt; 0:
  17.                 node = q.popleft()
  18.                 print(node.data)
  20.                 if node.left:
  21.                     q.append(node.left)
  22.                 if node.right:
  23.                     q.append(node.right)
  25.     def get_height(self, root_node):
  26.         if not root_node:
  27.             return 0
  28.         else: return root_node.height
  30.     def get_balance(self, root_node):
  31.         if not root_node:
  32.             return 0
  33.         else:
  34.             return self.get_height(root_node.left) - self.get_height(root_node.right)
  36.     def rotate_right(self, node):
  37.         new_root = node.left
  38.         node.left = new_root.right
  39.         new_root.right = node
  41.         node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
  42.         new_root.height = 1 + max(self.get_height(new_root.left), self.get_height(new_root.right))
  44.         return new_root
  46.     def rotate_left(self, node):
  47.         new_root = node.right
  48.         node.right = new_root.left
  49.         new_root.left = node
  51.         node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))
  52.         new_root.height = 1 + max(self.get_height(new_root.left), self.get_height(new_root.right))
  54.         return new_root
  56.     def insert_data(self, root_node, new_data):
  57.         if not root_node:
  58.             return AVL_Tree(new_data)
  59.         elif new_data &lt; root_node.data:
  60.             root_node.left = self.insert_data(root_node.left, new_data)
  61.         else:
  62.             root_node.right = self.insert_data(root_node.right, new_data)
  64.         root_node.height = 1 + max(self.get_height(root_node.left), self.get_height(root_node.right))
  65.         balance = self.get_balance(root_node)
  67.         # left - left condition
  68.         if balance &gt; 1 and new_data &lt; root_node.left.data:
  69.             return self.rotate_right(root_node)
  70.         
  71.         # left - right condition
  72.         if balance &gt; 1 and new_data &gt; root_node.left.data:
  73.             root_node.left = self.rotate_left(root_node.left)
  74.             return self.rotate_right(root_node)
  75.         
  76.         # right - right condition
  77.         if balance &lt; -1 and new_data &gt; root_node.right.data:
  78.             return self.rotate_left(root_node)
  79.         
  80.         # right - left condition
  81.         if balance &lt; -1 and new_data &lt; root_node.right.data:
  82.             root_node.right = self.rotate_right(root_node.right)
  83.             return self.rotate_left(root_node)
  84.         
  85.         return root_node
  87.     def get_min(self, root_node):
  88.         current = root_node
  89.         while current:
  90.             current = current.left
  91.         return current
  92.     
  93.     def delete_data(self, root_node, data):
  94.         if not root_node:
  95.             return root_node
  97.         if data &lt; root_node.data:
  98.             root_node.left = self.delete_data(root_node.left, data)
  99.         elif data &gt; root_node.data:
  100.             root_node.right = self.delete_data(root_node.right, data)
  101.         else:
  102.             if not root_node.left:
  103.                 temp = root_node.right
  104.                 root_node = None
  105.                 return temp
  106.             elif not root_node.right:
  107.                 temp = root_node.left
  108.                 root_node = None
  109.                 return temp
  111.             temp = self.get_min(root_node.right)
  112.             root_node.data = temp.data
  113.             root_node.right = self.delete_data(root_node.right, temp.data)
  115.         root_node.height = 1 + max(self.get_height(root_node.left), self.get_height(root_node.right))
  116.         balance = self.get_balance(root_node)
  118.         # Left - Left condition
  119.         if balance &gt; 1 and self.get_balance(root_node.left) &gt;= 0:
  120.             return self.rotate_right(root_node)
  122.         # Left - Right condition
  123.         if balance &gt; 1 and self.get_balance(root_node.left) &lt; 0:
  124.             root_node.left = self.rotate_left(root_node.left)
  125.             return self.rotate_right(root_node)
  127.         # Right - Right condition
  128.         if balance &lt; -1 and self.get_balance(root_node.right) &lt;= 0:
  129.             return self.rotate_left(root_node)
  131.         # Right - Left condition
  132.         if balance &lt; -1 and self.get_balance(root_node.right) &gt; 0:
  133.             root_node.right = self.rotate_right(root_node.right)
  134.             return self.rotate_left(root_node)
  136.         return root_node
  137.     
  139. avl = AVL_Tree(30)
  141. avl = avl.insert_data(avl, 25)
  142. avl = avl.insert_data(avl, 35)
  143. avl = avl.insert_data(avl, 20)
  144. avl = avl.insert_data(avl, 15)
  145. avl = avl.insert_data(avl, 5)
  146. avl = avl.insert_data(avl, 10)
  147. avl = avl.insert_data(avl, 50)
  148. avl = avl.insert_data(avl, 60)
  149. avl = avl.insert_data(avl, 70)
  150. avl = avl.insert_data(avl, 65)
  152. print(&quot;AVL Tree before deletion:&quot;)
  153. avl.levelOrder_Traversal(avl)
  155. print(&quot;\nAVL Tree after deleting data:&quot;)
  156. avl = avl.delete_data(avl, 30)
  157. 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方法上：它返回了你要查找的节点的左子节点，但是它是空的！你可以非常简单地修复它：

  1. def get_min(self, root_node):
  2.     current = root_node
  3.     while current.left:
  4.         current = current.left
  5.     return current

通过这个修复，30节点将被正确删除，并且生成的树的遍历是正确的：

  1. 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:

  1. def get_min(self, root_node):
  2.     current = root_node
  3.     while current.left:
  4.         current = current.left
  5.     return current

With this fix, the 30 node is correctly deleted, and the traversal of the resulting tree is correct:

  1. 20 , 10 50, 5 15 35 65,  - - - - 25 - 60 70

(- added to better see the tree structure)

huangapple
  • 本文由 发表于 2023年7月20日 21:08:04
  • 转载请务必保留本文链接：https://go.coder-hub.com/76730248.html
  • avl-tree
  • data-structures
  • python
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定