二叉搜索树
二叉搜索树是一种特殊的二叉树,它的特点是:
一个图例:
基于二叉搜索树的这种关系,我们可以用它来实现有序映射
遍历二叉搜索树
这里还需要思考的一个内容是在基于中序遍历的前提下,如何求一个节点的后继节点或前驱节点。
显然这就是求比该节点大的下一个节点或比它小的前一个节点。我们拿求后继节点为例:
算法用伪代码表示为:
def after(p):
"""寻找二叉搜索树的后继节点的伪代码"""
if right(p) is not None:
walk = right(p)
while left(right(p)) is not None: # 找最左
walk = left(walk)
return walk
else:
walk = p
ancestor = parent(walk)
while ancestor is not None and walk == right(ancestor): # 当walk是左孩子时或walk是根节点时停止
walk = ancestor
ancestor = parent(walk)
return ancestor
找前驱同理
搜索
既然叫做二叉搜索树,那它很重要的一个用途就是搜索,搜索的方式为:
算法用伪代码表示为:
def search(T,p,k):
"""二叉树搜索的伪代码,k是要搜索的值"""
if k == p.key():
return p
elif k < p.key() and T.left(p) is not None:
return search(T,T.left(p))
elif k > p.key() and T.right(p) is not None:
return search(T,T.right(p))
return p
搜索的时间与高度有关,是O(h),也就是最坏的情况下为O(n),最好的情况下是O(log(n))
插入
插入算法较简单,它依赖于搜索算法,将搜索的返回的位置的值与key进行比较,
删除
删除操作较为复杂,因为删除的位置可以是任意的位置,设删除的位置为p
1.先找到位置p的前驱r,前驱在左子树中
2.把p删除,将r代替p
3.把r原来的位置删除
使用前驱的原因是它必然比p的右子树的所有节点小,也必然比除了r的p的左子树的所有节点大
python实现
我们利用二叉树来实现有序映射
class OrderedMap(BinaryTree,MutableMapping):
"""使用二叉搜索树实现的有序映射"""
class _item():
def __init__(self, key, value):
self.key = key
self.value = value
def __eq__(self, other):
return self.key == other.key
def __ne__(self, other):
return self.key != other.key
def __lt__(self, other):
return self.key < other.key
class Position(BinaryTree.Position):
def key(self):
return self.element().key
def value(self):
return self.element().value
BinaryTree是在之前文章中定义的二叉树类,具体参考用Python实现数据结构之树
首先定义了两个内嵌类,一个表示键值项,一个用于封装节点
然后定义些非公开方法用于其他方法使用:
def _subtree_search(self, p, k):
"""搜索算法"""
if k == p.key():
return p
elif k < p.key():
if self.left(p) is not None:
return self._subtree_search(self.left(p), k)
else:
if self.right(p) is not None:
return self._subtree_search(self.right(p), k)
return p
def _subtree_first_position(self, p):
"""返回树的最左节点"""
walk = p
while self.left(walk) is not None:
walk = sel