У меня вопрос по поводу AVL_TREE. Вот мой код:
class TreeNode:
def __init__(self, key, val=None, left=None, right=None, parent=None, blanceFactor=0):
self.key = hash(key)
self.key_true = key
self.payload = val
self.leftChild = left
self.rightChild = right
self.parent = parent
self.blanceFactor = blanceFactor
def getLeft(self):
return self.leftChild
def getRight(self):
return self.rightChild
def isLeftChild(self):
return self.parent and self.parent.leftChild == self
def isRightChild(self):
return self.parent and self.parent.rightChild == self
def hasAnyChildren(self):
return self.rightChild or self.leftChild
def hasBothChildren(self):
return self.rightChild and self.leftChild
def isLeaf(self):
return not (self.rightChild or self.leftChild)
def isRoot(self):
return not self.parent
def replaceNodeData(self, key, val, leftChild, rightChild):
self.key = key
self.payload = val
self.leftChild = leftChild
self.rightChild = rightChild
if self.getLeft():
self.leftChild.parent = self
if self.getRight():
self.rightChild.parent = self
def __iter__(self):
if self:
if self.getLeft():
for elem in self.leftChild:
yield elem
yield self.key
if self.getRight():
for elem in self.rightChild:
yield elem
class mydict(TreeNode):
def getRoot(self):
return self.root
def __iter__(self):
return self.root.__iter__()
def __init__(self):
self.root = None
self.size = 0
def put(self, key, val):
if self.root:
self._put(key, val, self.root)
else:
self.root = TreeNode(key, val)
self.size += 1
def _put(self, key, val, currentNode):
key_hash = hash(key)
if key_hash < currentNode.key:
if currentNode.getLeft():
self._put(key, val, currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key, val, parent=currentNode)
self.updateBalance(currentNode.leftChild)
else:
if currentNode.getRight():
self._put(key, val, currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key, val, parent=currentNode)
self.updateBalance(currentNode.rightChild)
def __setitem__(self, key, value):
# md[key]=value
self.put(key, value)
def get(self, key):
if self.root:
res = self._get(key, self.root)
if res:
return res.payload
else:
return KeyError("Error, key not in tree")
else:
raise KeyError("Error, tree is None")
def _get(self, key, currentNode):
if not currentNode:
return None
elif currentNode.key == key:
return currentNode
elif key < currentNode.key:
return self._get(key, currentNode.leftChild)
else:
return self._get(key, currentNode.rightChild)
def __getitem__(self, key):
# v = md[key]
key_hash = hash(key)
return self.get(key_hash)
def findSuccessor(self):
succ = None
if self.getRight():
succ = self.rightChild.findMin()
else:
if self.parent:
if self.isLeftChild():
succ = self.parent
else:
self.parent.rightChild = None
succ = self.parent.findSuccessor()
self.parent.rightChild = self
return succ
def findMin(self):
current = self
while current.getLeft():
current = current.leftChild
return current
def spliceOut(self):
if self.isLeaf():
if self.isLeftChild():
self.parent.leftChild = None
else:
self.parent.rightChild = None
elif self.hasAnyChildren():
if self.getLeft():
if self.isLeftChild():
self.parent.leftChild = self.leftChild
else:
self.parent.rightChild = self.leftChild
self.leftChild.parent = self.parent
else:
if self.isLeftChild():
self.parent.leftChild = self.rightChild
else:
self.parent.rightChild = self.rightChild
self.rightChild.parent = self.parent
def remove(self, currentNode):
if currentNode.isLeaf():
if currentNode == currentNode.parent.leftChild:
currentNode.parent.leftChild = None
else:
currentNode.parent.rightChild = None
elif currentNode.hasBothChildren():
succ = currentNode.findSuccessor()
succ.spliceOut()
currentNode.key = succ.key
currentNode.payload = succ.payload
else:
if currentNode.getLeft():
if currentNode.isLeftChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.leftChild
elif currentNode.isRightChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.leftChild
else: # 如果被删除的节点本身是根节点
currentNode.replaceNodeData(currentNode.leftChild.key, currentNode.leftChild.payload,
currentNode.leftChild.leftChild, currentNode.leftChild.rightChild)
else:
if currentNode.isLeftChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.rightChild
elif currentNode.isRightChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.rightChild
else:
currentNode.replaceNodeData(currentNode.rightChild.key, currentNode.rightChild.payload,
currentNode.rightChild.leftChild, currentNode.rightChild.rightChild)
if not self.isAVL():
self.changeToAVL()
def delete(self, key):
if self.size > 1:
nodeToRemove = self._get(key, self.root)
if nodeToRemove:
self.remove(nodeToRemove)
self.size -= 1
else:
raise KeyError("Error, key not in tree")
elif self.size == 1 and self.root.key == key:
self.root = None
self.size -= 1
else:
raise KeyError("Error, key not in tree")
def __delitem__(self, key):
# del md[key]
self.delete(key)
def __len__(self):
# l = len(md)
return self.size
def __contains__(self, key):
# k in md
if self._get(key, self.root):
return True
else:
return False
def clear(self):
self.__init__()
def __str__(self):
if self.root is not None:
start = "{"
for i in self:
key_str = "{}: ".format(i)
val_str = "{}, ".format(self[i])
start += key_str
start += val_str
start = start[:-2]
result = start + "}"
else:
result = "{}"
return result
__repr__ = __str__
def keys(self):
key_list = []
for i in self:
key_list.append(i)
return key_list
def values(self):
val_list = []
for i in self:
val_list.append(self[i])
return val_list
def updateBalance(self, node):
if node.blanceFactor > 1 or node.blanceFactor < -1:
self.rebalance(node)
return
if node.parent != None:
if node.isLeftChild():
node.parent.blanceFactor += 1
elif node.isRightChild():
node.parent.blanceFactor -= 1
if node.parent.blanceFactor != 0:
self.updateBalance(node.parent)
def rebalance(self, node):
if node.blanceFactor < 0:
if node.rightChild.blanceFactor > 0:
self.rotateRight(node.rightChild)
self.rotateLeft(node)
else:
self.rotateLeft(node)
elif node.blanceFactor > 0:
if node.leftChild.blanceFactor < 0:
self.rotateLeft(node.leftChild)
self.rotateRight(node)
else:
self.rotateRight(node)
def rotateRight(self, rotRoot):
newRoot = rotRoot.leftChild
rotRoot.leftChild = newRoot.rightChild
if newRoot.rightChild != None:
newRoot.rightChild.parent = rotRoot
newRoot.parent = rotRoot.parent
if rotRoot.isRoot():
self.root = newRoot
else:
if rotRoot.isLeftChild():
rotRoot.parent.leftChild = newRoot
else:
rotRoot.parent.rightChild = newRoot
newRoot.rightChild = rotRoot
rotRoot.parent = newRoot
rotRoot.blanceFactor = rotRoot.blanceFactor - 1 - \
max(newRoot.blanceFactor, 0)
newRoot.blanceFactor = newRoot.blanceFactor - 1 + \
min(rotRoot.blanceFactor, 0)
def rotateLeft(self, rotRoot):
newRoot = rotRoot.rightChild
rotRoot.rightChild = newRoot.leftChild
if newRoot.leftChild != None:
newRoot.leftChild.parent = rotRoot
newRoot.parent = rotRoot.parent
if rotRoot.isRoot():
self.root = newRoot
else:
if rotRoot.isLeftChild():
rotRoot.parent.leftChild = newRoot
else:
rotRoot.parent.rightChild = newRoot
newRoot.leftChild = rotRoot
rotRoot.parent = newRoot
rotRoot.blanceFactor = rotRoot.blanceFactor + 1 - \
min(newRoot.blanceFactor, 0)
newRoot.blanceFactor = newRoot.blanceFactor + 1 + \
max(rotRoot.blanceFactor, 0)
md = mydict()
md['hello'] = 'world'
md['name'] = 'sessdsa'
print(md) # {'name': 'sessdsa', 'hello': 'world'}
пожалуйста, игнорируйте ключ md, смотрите только мое значение. если я печатаю (md), я могу получить только «Ошибка, ключ не в дереве». Да, ошибка функции "get". Но когда я отлаживал этот код, я обнаружил, что у md нет проблем! Я думаю, это проблема из getitem , но я не имею никакого представления об этом вопросе введите описание изображения здесь