У меня есть код, который является реализацией дерева AVL.Он поддерживает как удалить, так и вставить.Однако, как только я отправляю задание, я получаю не полное очко.Тестовые случаи, которые доступны для работы отлично, но я продолжаю получать 6/10 тестовых случаев (эти 10 не доступны для меня), как только я отправляю.Поэтому я хотел бы попросить вас пройтись по коду и найти несколько возможных ошибок.Большое спасибо!
Я пробовал разные типы дерева AVL, рекомендуемые в интернете.Никто из них не помог
class TreeNode(object):
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
self.height = 1
# AVL tree class which supports the
# Insert operation
class AVL_Tree(object):
# Recursive function to insert key in
# subtree rooted with node and returns
# new root of subtree.
def insert(self, root, key, value):
# Step 1 - Perform normal BST
if not root:
return TreeNode(key, value)
elif key < root.key:
root.left = self.insert(root.left, key, value)
else:
root.right = self.insert(root.right, key, value)
# Step 2 - Update the height of the
# ancestor node
root.height = 1 + max(self.getHeight(root.left),
self.getHeight(root.right))
# Step 3 - Get the balance factor
balance = self.getBalance(root)
# Step 4 - If the node is unbalanced,
# then try out the 4 cases
# Case 1 - Left Left
if balance > 1 and key < root.left.key:
return self.rightRotate(root)
# Case 2 - Right Right
if balance < -1 and key > root.right.key:
return self.leftRotate(root)
# Case 3 - Left Right
if balance > 1 and key > root.left.key:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
# Case 4 - Right Left
if balance < -1 and key < root.right.key:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
# Recursive function to delete a node with
# given key from subtree with given root.
# It returns the root of the modified subtree.
def delete(self, root, key):
# Step 1 - Perform standard BST delete
if not root:
return root
elif key < root.key:
root.left = self.delete(root.left, key)
elif key > root.key:
root.right = self.delete(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = self.getMinValueNode(root.right)
root.key = temp.key
root.right = self.delete(root.right, temp.key)
# If the tree has only one node,
# simply return it
if root is None:
return root
# Step 2 - Update the height of the
# ancestor node
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
# Step 3 - Get the balance factor
balance = self.getBalance(root)
# Step 4 - If the node is unbalanced,
# then try out the 4 cases
# Case 1 - Left Left
if balance > 1 and self.getBalance(root.left) >= 0:
return self.rightRotate(root)
# Case 2 - Right Right
if balance < -1 and self.getBalance(root.right) <= 0:
return self.leftRotate(root)
# Case 3 - Left Right
if balance > 1 and self.getBalance(root.left) < 0:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
# Case 4 - Right Left
if balance < -1 and self.getBalance(root.right) > 0:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
def leftRotate(self, z):
y = z.right
T2 = y.left
# Perform rotation
y.left = z
z.right = T2
# Update heights
z.height = 1 + max(self.getHeight(z.left),
self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left),
self.getHeight(y.right))
# Return the new root
return y
def rightRotate(self, z):
y = z.left
T3 = y.right
# Perform rotation
y.right = z
z.left = T3
# Update heights
z.height = 1 + max(self.getHeight(z.left),
self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left),
self.getHeight(y.right))
# Return the new root
return y
def getHeight(self, root):
if not root:
return 0
return root.height
def getMinValueNode(self, root):
if root is None or root.left is None:
return root
return self.getMinValueNode(root.left)
def getBalance(self, root):
if not root:
return 0
return self.getHeight(root.left) - self.getHeight(root.right)
def preOrder(self, root):
if not root:
return
pre_temp.append(root.value)
self.preOrder(root.left)
self.preOrder(root.right)
return pre_temp
def inOrder(self, root):
if not root:
return
self.inOrder(root.left)
in_temp.append(root.value)
self.inOrder(root.right)
return in_temp
# Driver program to test the above function
treeAVL = AVL_Tree()
root = None
while True:
line = input()
if line.split(" ")[0] == "insert":
root = treeAVL.insert(root, line.split(" ")[1], line.split(" ")[2])
elif line.split(" ")[0] == "remove":
root = treeAVL.delete(root, line.split(" ")[1])
elif line == "quit":
break
inOrder = ""
preOrder = ""
pre_temp = []
in_temp = []
for i in treeAVL.inOrder(root):
inOrder += i + ' '
print(inOrder.strip() + '\n')
for i in treeAVL.preOrder(root):
preOrder += i + ' '
print(preOrder.strip() + '\n')
Полагаю, проблема в операции удаления.Однако я не могу его найти.