BinarySearchTree类
class BinarySearchTree:
def __init__(self):
self.root = None
self.size = 0
def length(self):
return self.size
def __len__(self):
return self.size
def height(self):
return self.root.height()
def __iter__(self):
return self.root.__iter__()
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):
# print('BinarySearchTree _put')
if key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key,val,currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key,val,parent=currentNode)
elif key > currentNode.key:
if currentNode.hasRightChild():
self._put(key,val,currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key,val,parent=currentNode)
else:
currentNode.payload = val
self.size-=1
def __setitem__(self, key, value):
self.put(key,value)
def _get(self,key,currentNode):
if not currentNode:
return None
if currentNode.key == key:
return currentNode
elif key < currentNode.key:
return self._get(key,currentNode.leftChild)
else:
return self._get(key,currentNode.rightChild)
def get(self,key):
if self.root:
res = self._get(key,self.root)
if res:
return res.payload
else:
return None
else:
return None
def __getitem__(self, key):
return self.get(key)
def __contains__(self, key):
if self._get(key,self.root):
return True
else:
return False
def remove(self,current_node):
if current_node.isLeaf():
if current_node == current_node.parent.leftChild:
current_node.parent.leftChild = None
else:
current_node.parent.rightChild = None
elif current_node.hasBothChildren():
succ = current_node.findSuccessor()
current_node.key = succ.key
current_node.payload = succ.payload
succ.spliceOut()
else:
if current_node.hasLeftChild():
if current_node.isLeftChild():
current_node.parent.leftChild = current_node.leftChild
current_node.leftChild.parent = current_node.parent
elif current_node.isRightChild():
current_node.parent.rightChild = current_node.leftChild
current_node.leftChild.parent = current_node.parent
else:
current_node.replaceNodeData(current_node.leftChild.key,current_node.leftChild.payload,
current_node.leftChild.leftChild,current_node.leftChild.rightChild)
else:
if current_node.isLeftChild():
current_node.parent.leftChild = current_node.rightChild
current_node.rightChild.parent = current_node.parent
elif current_node.isRightChild():
current_node.parent.rightChild = current_node.rightChild
current_node.rightChild.parent = current_node.parent
else:
current_node.replaceNodeData(current_node.rightChild.key,current_node.rightChild.payload,
current_node.rightChild.leftChild,current_node.rightChild.RightChild)
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 the tree')
elif self.size == 1 and self.root.key == key:
self.root = None
self.size -= 1
else:
raise KeyError('Error, key not in the tree')
if __name__ == '__main__':
tree = BinarySearchTree()
for i in range(1,16):
tree[i] = i
# tree[18] = 'wangwu'
# tree[33] = 'lisi'
# tree[55] = 'ddd'
# tree[66] = 'zhangsan'
# tree[99] = 'hanh'
# tree = BinarySearchTree()
# tree[17] = 'zhangsan'
# tree[5] = 'lisi'
TreeNode类
class TreeNode:
'''A node for the Binary Search Tree '''
def __init__(self,key,val,left=None,right=None,parent=None):
self.key = key
self.payload = val
self.leftChild = left
self.rightChild = right
self.parent = parent
self.balanceFactor = 0
def height(self):
height_l = 0
height_r = 0
if self.isLeaf():
return 0
if self.leftChild:
height_l = self.leftChild.height()
if self.rightChild:
height_r = self.rightChild.height()
return max(height_l,height_r) + 1
def hasLeftChild(self):
return self.leftChild
def hasRightChild(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 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,value,lc,rc):
self.key = key
self.payload = value
self.leftChild = lc
self.rightChild = rc
if self.hasLeftChild():
self.leftChild.parent = self
if self.hasRightChild():
self.rightChild.parent = self
#查找后继节点
def findSuccessor(self):
succ = None
if self.hasRightChild():
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 spliceOut(self):
if self.isLeaf():
if self.isLeftChild():
self.parent.leftChild = None
else:
self.parent.rightChild = None
elif self.hasAnyChildren():#self.hasRightChild()
if self.hasLeftChild():
if self.isLeftChild():
self.parent.leftChild = self.leftChild
self.leftChild.parent = self.parent
else:
self.parent.rightChild = self.leftChild
self.leftChild.parent = self.parent
else:
if self.isLeftChild():
self.parent.leftChild = self.rightChild
self.rightChild.parent = self.parent
else:
self.parent.rightChild = self.rightChild
self.rightChild.parent = self.parent
def findMin(self):
currnode = self
while currnode.hasLeftChild():
currnode = currnode.leftChild
return currnode
def __iter__(self):
if self:
if self.hasLeftChild():
for node in self.leftChild:
yield node
yield self.key
if self.hasRightChild():
for node in self.rightChild:
yield node
AvlTree类
class AvlTree(BinarySearchTree):
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.balanceFactor = rotRoot.balanceFactor + 1 - min(
newRoot.balanceFactor, 0)
newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(
rotRoot.balanceFactor, 0)
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.isRightChild():
rotRoot.parent.rightChild = newRoot
newRoot.rightChild = rotRoot
rotRoot.parent = newRoot
rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(
newRoot.balanceFactor, 0)
newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(
rotRoot.balanceFactor, 0)
# 如果子树需要左旋，首先检查右子树的平衡因子。如果右子树左倾，就对右子树做一次右旋，再围绕原节点做一次左旋。
# 如果子树需要右旋，首先检查左子树的平衡因子。如果左子树右倾，就对左子树做一次左旋，再围绕原节点做一次右旋。
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 updateBalance(self, node):
if node.balanceFactor > 1 or node.balanceFactor < -1:
self.rebalance(node)
return
if node.parent == None:
return
else:
if node.isLeftChild():
node.parent.balanceFactor += 1
elif node.isRightChild():
node.parent.balanceFactor -= 1
if node.parent.balanceFactor != 0:
self.updateBalance(node.parent)
def _put(self,key,val,currentNode):
if key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key, val, currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key, val, parent=currentNode)
self.updateBalance(currentNode.leftChild)
elif key > currentNode.key:
if currentNode.hasRightChild():
self._put(key, val, currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key, val, parent=currentNode)
self.updateBalance(currentNode.rightChild)
else:
currentNode.payload = val
self.size -= 1
if __name__ == '__main__':
tree = AvlTree()
for i in range(1,16):
tree[i] = i
# tree[18] = 'wangwu'
# tree[33] = 'lisi'
# tree[55] = 'ddd'
# tree[66] = 'zhangsan'
# tree[99] = 'hanh'
print(tree.height())
网友评论