class BinarySearchTree:
def __init__(self):
self.root = None
self.size = 0
def height(self):
return self.root.height()
def length(self):
return self.size
def __len__(self):
return self.size
def __iter__(self):
return self.root.__iter__()
def put(self, key, value):
if self.root:
self._put(key, value, self.root)
else:
self.root = TreeNode(key, value)
self.size += 1
def _put(self, key, value, currentNode):
if key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key, value, currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key, value, parent=currentNode)
elif key > currentNode.key:
if currentNode.hasRightChild():
self._put(key, value, currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key, value, parent=currentNode)
else:
currentNode.payload = value
self.size -= 1
def __setitem__(self, key, value):
self.put(key, value)
def get(self, key):
if self.root:
result = self._get(key, self.root)
return result.payload
else:
return 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):
return self.get(key)
def __contains__(self, key):
if self.get(key):
return True
else:
return False
def remove(self, currentNode):
if currentNode.isLeaf():
if currentNode.isLeftChild():
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.hasLeftChild():
if currentNode.isLeftChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.leftChild
elif currentNode.isRightChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.leftChild
else:
currentNode.replace(currentNode.leftChild.key, currentNode.leftChild.value,
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.replace(currentNode.rightChild.key, currentNode.rightChild.value,
currentNode.rightChild.leftChild, currentNode.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(f'Key:{key} not found')
elif self.size == 1 and self.root.key == key:
self.root = None
self.size -= 1
else:
raise KeyError(f'Key:{key} not found')
class TreeNode:
def __init__(self, key, value, left=None, right=None, parent=None):
self.key = key
self.payload = value
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.hasLeftChild():
height_l = self.leftChild.height()
if self.hasRightChild():
height_r = self.rightChild.height()
return max(height_l, height_r) + 1
def hasLeftChild(self):
return self.leftChild is not None
def hasRightChild(self):
return self.rightChild is not None
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 self.parent is None
def isLeaf(self):
return not(self.rightChild or self.leftChild)
def hasAnyChildren(self):
return self.leftChild or self.rightChild
def hasBothChildren(self):
return self.rightChild and self.leftChild
def replaceNodeData(self, key, value, lc, rc):
self.key = key
self.value = 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 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
else:
self.parent.rightChild = None
elif self.hasAnyChildren():
if self.hasLeftChild():
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 __iter__(self):
if self:
if self.hasLeftChild():
for i in self.leftChild:
yield i
yield self.key
if self.hasRightChild():
for i in self.rightChild:
yield i
t = BinarySearchTree()
for i in range(1, 16):
t[i] = i
print(t.height())
输出：
14
