二叉搜索树的实现： BST.put方法
put(key, val)方法：插入key构造BST
首先看BST是否为空，如果一个节点都没有，那么key成为根节点root，否则，就调用一个递归函数_put(key, val, root)来放置key
二叉搜索树的实现： _put辅助方法
_put(key, val, currentNode)的流程
如果key比currentNode小，那么_put到左子树
- 但如果没有左子树，那么key就成为左子节点
如果key比currentNode大，那么_put到右子树
- 但如果没有右子树，那么key就成为右子节点
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)
else:
# 递归右子树
if currentNode.hasRightChild():
self._put(key, val, currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key, val, parent=currentNode)
二叉搜索树的实现： 索引赋值
随手把__setitem__做了
特殊方法（前后双下划线）
可以myZipTree[‘PKU’] = 100871
def __setitem__(self, k, v):
self.put(k, v)
二叉搜索树的实现： BST.put图示
插入key=19， currentNode的变化过程（灰色） ：
二叉搜索树的实现： BST.get方法
在树中找到key所在的节点取到payload
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 _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)
二叉搜索树的实现： 索引和归属判断
__getitem__特殊方法
实现val= myZipTree[‘PKU’]
__contains__特殊方法
实现’PKU’ in myZipTree的归属判断运算符in
def __getitem__(self, key):
return self.get(key)
def __contains__(self, key):
if self._get(key, self.root):
return True
else:
return False
二叉搜索树的实现：迭代器
我们可以用for循环枚举字典中的所有key
ADTMap也应该实现这样的迭代器功能
特殊方法__iter__可以用来实现for迭代
BST类中的__iter__方法直接调用了TreeNode中的同名方法
TreeNode类中的__iter__迭代器
迭代器函数中用了for迭代，实际上是递归函数，yield是对每次迭代的返回值中序遍历的迭代
def __iter__(self):
if self:
if self.hasLeftChild():
for elem in self.leftChild:
yield elem
yield self.key
if self.hasRightChild():
for elem in self.rightChild:
yield elem
二叉查找树的实现： BST.delete方法
有增就有减， 最复杂的delete方法：
用_get找到要删除的节点，然后调用remove来删除，找不到则提示错误
def delete(self, key):
if self.size > 1:
nodeToRemove = self._get(key, self.root)
if nodeToRemove:
self.remove(nodeToRemove)
self.size = self-1
else:
raise KeyError('Error, key not in tree')
elif self.size == 1 and self.root.key == key:
self.root = None
self.size = self.size - 1
else:
raise KeyError('Error, key not in tree')
__delitem__特殊方法
实现del myZipTree[‘PKU’]这样的语句操作
def __delitem__(self, key):
self.delete(key)
在delete中， 最复杂的是找到key对应的节点之后的remove节点方法！
二叉查找树的实现： BST.remove方法
从BST中remove一个节点， 还要求仍然保持BST的性质， 分以下3种情形：
这个节点没有子节点
这个节点有1个子节点
这个节点有2个子节点
没有子节点的情况好办， 直接删除
if currentNode.isLeaf(): #leaf
if currentNode == currentNode.parent.leftChild:
currentNode.parent.leftChild = None
else:
currentNode.parent.rightChild = None
第2种情形稍复杂：被删节点有1个子节点
解决：将这个唯一的子节点上移，替换掉被删节点的位置
但替换操作需要区分几种情况：
被删节点的子节点是左？还是右子节点？
被删节点本身是其父节点的左？还是右子节点？
被删节点本身就是根节点？
else: # this node has one child
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.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)
第3种情形最复杂：被删节点有2个子节点
这时无法简单地将某个子节点上移替换被删节点，但可以找到另一个合适的节点来替换被删节点，这个合适节点就是被删节点的下一个key值节点，即被删节点右子树中最小的那个，称为“后继”
BinarySearchTree类： remove方法（情形3）
elif currentNode.hasBothChildren(): #interior
succ = currentNode.findSuccessor()
succ.spliceOut()
currentNode.key = succ.key
currentNode.payload = succ.payload
TreeNode类：寻找后继节点
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
TreeNode类：摘出节点spliceOut()
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
二叉查找树：算法分析（以put为例）
其性能决定因素在于二叉搜索树的高度（最大层次） ， 而其高度又受数据项key插入顺序的影响。
如果key的列表是随机分布的话， 那么大于和小于根节点key的键值大致相等
BST的高度就是log2n（n是节点的个数） ，而且， 这样的树就是平衡树
put方法最差性能为O(log2n)。
但key列表分布极端情况就完全不同
按照从小到大顺序插入的话，如下图这时候put方法的性能为O(n)，其它方法也是类似情况
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: