产品
数据结构与算法
用AVL树实现字典类型
# ---- 用AVL树实现字典类型 ----
# 用AVL树来实现字典类型，使得其put/get/in/del操作均达到对数性能
# 采用如下的类定义，至少实现下列的方法
# key至少支持整数、浮点数、字符串
# 请调用hash(key)来作为AVL树的节点key
# 【注意】涉及到输出的__str__, keys, values这些方法的输出次序是AVL树中序遍历次序
# 也就是按照hash(key)来排序的，这个跟Python 3.7中的dict输出次序不一样。
# 请在此编写你的代码
# hash函数
from struct import pack
from hashlib import md5
def hash(key):
if isinstance(key, str):
return md5(key.encode()).hexdigest()
if isinstance(key, int):
return md5(pack('d', key)).hexdigest()
if isinstance(key, float):
return md5(pack('f', key)).hexdigest()
# 第一部分：树节点类
class TreeNode:
"""
二叉树节点
请自行完成节点内部的实现，并实现给出的接口
"""
def __init__(self, key, val = None, leftChild = None, rightChild = None, parent = None): # 初始化方法
self.key = hash(key)
self.orikey = key
self.payload = val
self.leftChild = leftChild
self.rightChild = rightChild
self.parent = parent
self.balanceFactor = 0
def getLeft(self): # 获取左子树 (不存在时返回None)
return self.leftChild
def getRight(self): # 获取右子树 (不存在时返回None)
return self.rightChild
hasLeftChild = getLeft
hasRightChild = getRight
def isLeftChild(self):
return self.parent and \
self.parent.leftChild == self
def isRightChild(self):
return self.parent and \
self.parent.rightChild == self
def isRoot(self):
return not self.parent
def isLeaf(self):
return not (self.rightChild or self.leftChild)
def hasAnyChildren(self):
return self.rightChild or self.leftChild
def hasBothChildren(self):
return self.rightChild and self.leftChild
def replaceNodeData(self, key, val, lc, rc):
self.key = hash(key)
self.orikey = key
self.payload = val
self.leftChild = lc
self.rightChild = rc
if self.hasLeftChild():
self.leftChild.parent = self
if self.hasRightChild():
self.rightChild.parent = self
def replaceNodeValue(self, key, val):
self.key = hash(key)
self.orikey = key
self.payload = val
def __iter__(self):
# 中序遍历
if self:
if self.hasLeftChild():
# 递归调用
for elem in self.leftChild:
yield elem
yield self.orikey
if self.hasRightChild():
for elem in self.rightChild:
yield elem
def findSuccessor(self):
# 默认有右子树
if self.hasRightChild():
succ = self.rightChild.findMin()
return succ
def findMin(self):
current = self
while current.hasLeftChild():
current = current.leftChild
return current
def spliceOut(self):
# 摘除后继
if self.isLeaf():
if self.isLeftChild():
self.parent.leftChild = None
# 还是需要保留self是右子节点的情况！！！
else:
self.parent.rightChild = None
elif self.hasAnyChildren():
# 更新链接
if self.isLeftChild():
self.parent.leftChild = self.rightChild
else:
self.parent.rightChild = self.rightChild
self.rightChild.parent = self.parent
# 第二部分：AVL树类
class avlTree():
def __init__(self):
self.root = None
self.size = 0
def __len__(self):
return self.size
def __iter__(self):
if self.root:
return iter(self.root)
return iter([])
def __str__(self):
output = ', '.join([f'{repr(key)}: {repr(self[key])}' for key in self])
return f'{{{output}}}'
def put(self, key, val):
if self.root:
self._put(key, val, self.root)
else:
self.root = TreeNode(key, val)
self.size += 1
__setitem__ = put
def _put(self, orikey, val, currentNode):
key = hash(orikey)
if key < currentNode.key:
if currentNode.hasLeftChild():
# 进递归
self._put(orikey, val, currentNode.leftChild)
else:
# 递归结束条件
currentNode.leftChild = \
TreeNode(orikey, val, parent = currentNode)
self.updateBalance(currentNode.leftChild)
elif key > currentNode.key:
if currentNode.hasRightChild():
self._put(orikey, val, currentNode.rightChild)
else:
currentNode.rightChild = \
TreeNode(orikey, val, parent = currentNode)
self.updateBalance(currentNode.rightChild)
else:
currentNode.replaceNodeValue(orikey, val)
def updateBalance(self, node):
if node.balanceFactor > 1 or node.balanceFactor < -1:
self.rebalance(node)
return
if node.parent != None:
if node.isLeftChild():
node.parent.balanceFactor += 1
elif node.isRightChild():
node.parent.balanceFactor -= 1
if node.parent.balanceFactor != 0:
self.updateBalance(node.parent)
def rebalance(self, node):
# 右重需要左旋
if node.balanceFactor < 0:
# 右子节点左重，先右旋
if node.rightChild.balanceFactor > 0:
self.rotateRight(node.rightChild)
self.rotateLeft(node)
else:
self.rotateLeft(node)
elif node.balanceFactor > 0:
# 完全类似
if node.leftChild.balanceFactor < 0:
self.rotateLeft(node.leftChild)
self.rotateRight(node)
else:
self.rotateRight(node)
def rotateLeft(self, rotRoot):
newRoot = rotRoot.rightChild
# 保证BST性质
rotRoot.rightChild = newRoot.leftChild
if newRoot.leftChild != None:
newRoot.leftChild.parent = rotRoot
newRoot.parent = rotRoot.parent
if rotRoot.isRoot():
self.root = newRoot
else:
# 将rotRoot原父节点链接到newRoot
if rotRoot.isLeftChild():
rotRoot.parent.leftChild = newRoot
else:
rotRoot.parent.rightChild = newRoot
newRoot.leftChild = rotRoot
rotRoot.parent = newRoot
rotRoot.balanceFactor += \
(1 - min(newRoot.balanceFactor, 0))
newRoot.balanceFactor += \
(1 + max(rotRoot.balanceFactor, 0))
def rotateRight(self, rotRoot):
newRoot = rotRoot.leftChild
# 保证BST性质
rotRoot.leftChild = newRoot.rightChild
if newRoot.rightChild != None:
newRoot.rightChild.parent = rotRoot
newRoot.parent = rotRoot.parent
if rotRoot.isRoot():
self.root = newRoot
else:
# 将rotRoot原父节点链接到newRoot
if rotRoot.isLeftChild():
rotRoot.parent.leftChild = newRoot
else:
rotRoot.parent.rightChild = newRoot
newRoot.rightChild = rotRoot
rotRoot.parent = newRoot
rotRoot.balanceFactor -= \
(1 + max(newRoot.balanceFactor, 0))
newRoot.balanceFactor -= \
(1 - min(rotRoot.balanceFactor, 0))
def get(self, key):
return self._get(key, self.root).payload
__getitem__ = get
def _get(self, orikey, currentNode):
key = hash(orikey)
if not currentNode:
# key在AVL树中不存在的话，请raise KeyError
raise KeyError
elif key == currentNode.key:
return currentNode
elif key < currentNode.key:
return self._get(orikey, currentNode.leftChild)
else:
return self._get(orikey, currentNode.rightChild)
def __contains__(self, key):
try:
v = self[key]
except KeyError:
return False
return True
def delete(self, orikey):
key = hash(orikey)
# 去掉节点后不为空树，则调用remove
if self.size > 1:
nodeToRemove = self._get(orikey, self.root)
if nodeToRemove:
self.remove(nodeToRemove)
self.size -= 1
else:
raise KeyError
# 去掉节点后变为空树
elif self.size == 1 and self.root.key == key:
self.root = None
self.size = 0
else:
raise KeyError
__delitem__ = delete
def remove(self, currentNode):
if currentNode.isLeaf():
if currentNode.isLeftChild():
currentNode.parent.leftChild = None
currentNode.parent.balanceFactor -= 1
elif currentNode.isRightChild():
currentNode.parent.rightChild = None
currentNode.parent.balanceFactor += 1
self.updateBalanceRemove(currentNode.parent)
elif currentNode.hasBothChildren():
# 后继在右子节点的左下角
succ = currentNode.findSuccessor()
if succ.isLeftChild():
succ.parent.balanceFactor -= 1
else:
succ.parent.balanceFactor += 1
# 摘除后继
succ.spliceOut()
# 当前节点更改数据
currentNode.replaceNodeValue(succ.orikey, succ.payload)
self.updateBalanceRemove(succ.parent)
# 代码长，但其实简单
else:
# 删除只有一个子节点的内部节点
if currentNode.hasLeftChild():
if currentNode.isLeftChild():
# 直接删除，链接更新
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.leftChild
currentNode.parent.balanceFactor -= 1
elif currentNode.isRightChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.leftChild
currentNode.parent.balanceFactor += 1
else:
# 是根节点
currentNode.leftChild.parent = None
self.root = currentNode.leftChild
else:
# 只有一个右子节点的情形
if currentNode.isLeftChild():
# 直接删除，链接更新
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.rightChild
currentNode.parent.balanceFactor -= 1
elif currentNode.isRightChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.rightChild
currentNode.parent.balanceFactor += 1
else:
# 是根节点
currentNode.rightChild.parent = None
self.root = currentNode.rightChild
if currentNode.parent:
self.updateBalanceRemove(currentNode.parent)
def updateBalanceRemove(self, node):
if node.balanceFactor > 1 or node.balanceFactor < -1:
self.rebalance(node)
node = node.parent
# newRoot平衡因子为0，要继续平衡(画图)
if node.balanceFactor == 0 and node.parent:
if node.isLeftChild():
node.parent.balanceFactor -= 1
elif node.isRightChild():
node.parent.balanceFactor += 1
self.updateBalanceRemove(node.parent)
# debug
# put没问题
# delete？
# 第三部分：mydict类（以AVL树为内部实现）
class mydict:
"""
以AVL树作为内部实现的字典
"""
def getRoot(self): # 返回内部的AVL树根
return self.avltree.root
def __init__(self): # 创建一个空字典
self.avltree = avlTree()
def __setitem__(self, key, value): # 将key:value保存到字典
# md[key]=value
self.avltree[key] = value
def __getitem__(self, key): # 从字典中根据key获取value
# v = md[key]
# key在字典中不存在的话，请raise KeyError
return self.avltree[key]
def __delitem__(self, key): # 删除字典中的key
# del md[key]
# key在字典中不存在的话，请raise KeyError
del self.avltree[key]
def __len__(self): # 获取字典的长度
# l = len(md)
return len(self.avltree)
def __contains__(self, key): # 判断字典中是否存在key
# k in md
return key in self.avltree
def clear(self): # 清除字典
self.avltree = avlTree()
def __str__(self): # 输出字符串形式，参照内置dict类型，输出按照AVL树中序遍历次序
# 格式类似：{'name': 'sessdsa', 'hello': 'world'}
return str(self.avltree)
__repr__ = __str__
def keys(self): # 返回所有的key，类型是列表，按照AVL树中序遍历次序
return [i for i in self.avltree]
def values(self): # 返回所有的value，类型是列表，按照AVL树中序遍历次序
return [self.avltree[key] for key in self.avltree]
# 代码结束
#mydict=dict
# 检验
print("========= AVL树实现字典 =========")
md = mydict()
md['hello'] = 'world'
md['name'] = 'sessdsa'
print(md) # {'name': 'sessdsa', 'hello': 'world'}
for f in range(1000):
md[f**0.5] = f
for i in range(1000, 2000):
md[i] = i**2
print(len(md)) # 2002
print(md[2.0]) # 4
print(md[1000]) # 1000000
print(md['hello']) # world
print(20.0 in md) # True
print(99 in md) # False
del md['hello']
print('hello' in md) # False
for i in range(1000, 2000):
del md[i]
print(len(md)) # 1001
for f in range(1000):
del md[f**0.5]
print(len(md)) # 1
print(md.keys()) # ['name']
print(md.values()) # ['sessdsa']
for a in md.keys():
print(md[a]) # sessdsa
md.clear()
print(md) # {}免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删
155-2731-8020
