数据结构与算法(Python版)五十三：二叉查找树实现及算法分析

二叉搜索树的实现： 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

ADT Map也应该实现这样的迭代器功能

特殊方法__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)，其它方法也是类似情况