【数据结构Python描述】二叉搜索树简介与使用二叉搜索树实现有序映射

文章目录

• 一、二叉搜索树简介
• 二、二叉搜索树的节点定位
• • 1. 二叉搜索树与有序映射
  • 2. 二叉搜索树的节点定位
• 三、二叉搜索树的查询操作
• 四、二叉搜索树的插入操作
• 五、二叉搜索树的删除操作
• 六、二叉搜索树实现有序映射
• 七、有序映射操作时间复杂度

在文章【数据结构Python描述】使用列表手动实现一个有序映射中，我们实现了第一个有序映射，虽然当待操作键值对存在时，利用二分查找可以将查询、修改操作的最坏时间复杂度保证在$O(logn)$，但是当待操作键值对不存在时，由于增、删操作可能在列表头部进行，此时增、删操作引起的每个元素平移将使得最坏时间复杂度变为$O(n)$。

针对上述问题，在【数据结构Python描述】跳跃表简介及使用跳跃表实现有序映射中，我们又使用跳跃表实现了一个有序映射，跳跃表由于本质是链表，因此避免了元素增、删后可能引起的其他元素位置变动，对于链表遍历效率低的问题，跳跃表通过增加节点的引用数量的方式来解决，因此通过跳跃表实现的有序映射可实现增、删、改、查操作在大概率情况下都是$O(logn)$。

本文将使用一种特殊的二叉树——二叉搜索树来实现有序映射。

一、二叉搜索树简介

定义：二叉搜索树是一种特殊的二叉树，相较于普通二叉树，其特殊之处在于节点位置p处保存的元素(k, v)和其左右子树满足下列关系：

• 位置p的左子树中所有节点的元素的键都小于k；
• 位置p的右子树中所有节点的元素的键都大于k；

下面是一个典型的二叉搜索树，为简便起见，这里仅显示了每个节点处的键，而省略了每个节点处键对应的值，因为值不影响节点间的相对关系：

二、二叉搜索树的节点定位

1. 二叉搜索树与有序映射

二叉搜索树之所以可以用来表示一个有序映射，原因在于对一个二叉搜索树使用二叉树的中序遍历算法将按照节点的键升序依次遍历树中的每一个节点。

2. 二叉搜索树的节点定位

尽管二叉树的中序遍历一般通过自上而下的递归来实现，而对于二叉搜索树，按照节点间键的相对大小关系，我们还可以提供粒度更细的节点定位方法。

因此，这里除了提供一般二叉树的节点定位方法parent(p)、left(p)以及right(p)（其中p代表抽象节点位置的实例对象）之外，还提供一下几个方法：

• first()：返回包含最小键的节点的位置，当二叉搜索树树为空时返回None；
• last()：返回包含最大键的节点的位置，当二叉搜索树树为空时返回None；
• after(p)：对于键大于位置p处节点的键的所有节点，返回其中键最小的节点的位置（即中序遍历中，位置p的下一个位置），当p代表最后一个节点的位置，则返回None；
• before(p)：对于键小于位置p处节点的键的所有节点，返回其中键最大的节点的位置（即中序遍历中，位置p的上一个位置），当p代表第一个节点的位置，则返回None。

first()

根据二叉搜索树的性质，为找到其键最小的节点，只要从根节点开始重复调用left(p)方法直到某节点不存在左子节点，则该节点位置即为所需的节点位置。

last()

类似上述first()方法，根据二叉搜索树的性质，为找到其键最大的节点，只要从根节点开始重复调用right(p)方法直到某节点不存在右子节点，则该节点位置即为所需的节点位置。

after(p)

对于二叉搜索树，为找到中序遍历时位置p处节点的后继节点位置，可通过下列算法实现：

Algorithm after(p):
	// successor is leftmost position in p’s right subtree
	if right(p) is not None then
		walk = right(p)
		while left(walk) is not None do
			walk = left(walk)
		return walk
	// successor is nearest ancestor having p in its left subtree
	else
		walk = p
		ancestor = parent(walk)
		while ancestor is not None and walk == right(ancestor) do
			walk = ancestor
			ancestor = parent(walk)
		return ancestor

上述算法完全是基于中序遍历的原理以及二叉搜索树的性质，即：

• 如果p处节点有右子树，则对p处节点进行访问后，紧随其后被访问的是该右子树“最左侧”位置的节点；
• 如果p处节点无右子树，则在该节点处的中序遍历递归调用返回到p的父节点；
  • 紧接着，如果p处节点在其父节点的右子树中，则其父节点处的中序遍历递归调用返回到p处节点的祖父节点，以此类推，直到递归调用返回至某祖先节点前是对其左子树进行递归遍历，此时该祖先节点即为目标节点。

before(p)

对于二叉搜索树，为找到中序遍历时位置p处节点的前序节点位置，可通过下列算法实现：

Algorithm before(p):
	// predecessor is rightmost position in p’s left subtree
	if left(p) is not None then
		walk = left(p)
		while right(walk) is not None do
			walk = right(walk)
		return walk
	// predecessor is nearest ancestor having p in its right subtree
	else
		walk = p
		ancestor = parent(walk)
		while ancestor is not None and walk == left(ancestor) do
			walk = ancestor
			ancestor = parent(walk)
		return ancestor

实际上，上述实现before(p)的算法和after(p)的算法具有完全的对称性。

三、二叉搜索树的查询操作

当需要根据键查找二叉搜索树的某节点时，根据二叉搜索树的性质，只需要从根节点处开始递归地做如下判断：

• 当待查找的键小于位置p处节点的键，则查询在以p的左子节点为根节点的左子树继续递归；
• 当待查找的键等于位置p处节点的键，则返回p；
• 当待查找的键大于位置p处节点的键，则查询在以p的右子节点为根节点的右子树继续递归。

递归过程中，除了上述第二种情况递归返回，另一种递归返回的情况发生在遇到空子树时。

下图分别表示了成功搜索到键为65的节点及未能成功搜索到键为68的节点两种情况：

下面给出二叉搜索树的查询操作的算法伪代码：

Algorithm TreeSearch(T, p, k):
	if k == p.key() then
	// successful search
		return p
	else if k < p.key() and T.left(p) is not None then
		// recur on left subtree
		return TreeSearch(T, T.left(p), k)
	else if k > p.key() and T.right(p) is not None then
		// recur on right subtree
		return TreeSearch(T, T.right(p), k)
	// unsuccessful search
	return p

需要注意的是，在查询操作失败时，上述算法会返回最后访问的节点所在位置，这对于后续实现节点插入操作很有帮助。

四、二叉搜索树的插入操作

基于__setitem__方法实现的映射操作M[k] = v依赖于先根据键k进行查找节点（假定映射非空），如果找到键同样为k的节点，则节点处的值被修改为v；否则键值对将被插入二叉搜索树中，且位置为查询操作最后所到达节点的空子树处，下面是二叉搜索树插入操作的伪代码：

Algorithm TreeInsert(T, k, v):
	p = TreeSearch(T, T.root(),k)
	if k == p.key() then
		Set p’s value to v
	else if k < p.key() then
		add node with item (k, v) as left child of p
	else
		add node with item (k, v) as right child of p

下图表示了向二叉搜索树中插入键为68的节点所需的步骤，即首先如图(a)所示将先搜索到键为76的节点处并确定应该将新节点插在该节点的左子节点处，然后如图(b)所示将该节点插在键为76的节点的左子节点位置。

五、二叉搜索树的删除操作

相较于向二叉搜索树T中插入一个节点，从T中删除一个节点要复杂不少，因为节点插入操作永远发生在树的一条路径的终点，相反待删除的节点可能出现在T的任意位置处。

因此，为了删除某节点，需要先调用TreeSearch(T, T.root(), k)找到键为k的节点所在位置p，如果成功找到了待删除节点，我们还需按照下列两种情况进行区分：

1. 至多一个子节点情况下的节点删除

如位置p处的节点至多只有一个子节点，可以使用之前一般二叉树LinkedBinaryTree实现类中的_delete(p)方法，该方法会删除位置p处的节点，并且在该位置有子节点时（至多一个）使用其子节点填充该位置。下图即描述了当删除键为32的节点，且该节点仅有一个键为28的子节点时的操作流程。

2. 恰好两个子节点情况下的节点删除

如位置p处的节点有两个子节点，此时以下图为例，当待删除键为88的节点，且该节点有键分别为65和97的两个子节点，此时节点删除操作遵循下列步骤：

• 首先，通过r = before(p)获得p处节点的前序节点所在位置r，由于位置p处节点有两个子节点，故r为p的左子树中“最右侧”节点的位置，如下图所示即键为82的节点所在位置；
• 然后，使用位置r处的节点替代被删除的位置p处节点，这么做可以确保二叉树不违反二叉搜索树的性质。因为在中序遍历中，程序访问r处节点后将立即访问p处节点，且位置p处的右子树中所有节点的键都大于r处节点的键，而在位置p处的左子树中，r处节点的键最大；
• 最后，将原本位置r处的节点删除，奇妙的是由于位置r是某子树“最右侧”位置，因此该位置至多有一个子节点，故可以使用第一种简单情形删除该节点。

六、二叉搜索树实现有序映射

下面我们将使用二叉搜索树来实现一个有序映射类TreeMap，这里为提高代码的复用程度并再次体现模板设计模式的优势，此处利用多继承，即TreeMap类同时继承一般二叉树实现类LinkedBinaryTree和映射基类MapBase，其中：

• 通过继承映射基类MapBase，我们可以得到用于表示键值对的_Item类以及collections.MutableMapping抽象基类中所有的映射ADT方法；
• 通过继承一般二叉树实现类LinkedBinaryTree，我们一方面可以复用一般二叉树的所有ADT方法，从而只需实现二叉搜索树的特有方法，另外还可以通过重写其中的Position类来提供更简单的键、值访问方法p.key()和p.value()。

1. 节点描述类Position

该类嵌套定义在TreeMap类中且继承LinkedBinaryTree中的Position类。

class Position(LinkedBinaryTree.Position):
    """用于表示二叉搜索树中节点位置的类"""

    def key(self):
        """返回映射中某键值对的键"""
        return self.element().key

    def value(self):
        """返回映射中某键值对的值"""
        return self.element().value

2. 实用查询方法_subtree_search

该方法即为TreeSearch(T, p, k)算法的具体实现。

def _subtree_search(self, p, k):
    """针对根节点在位置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  # 查找失败

3. 查询“第一个”节点实用方法_subtree_first_position

def _subtree_first_position(self, p):
    """返回以位置p处节点为根节点的二叉搜索（子）树中“第一个”节点的位置"""
    walk = p
    while self.left(walk) is not None:
        walk = self.left(walk)
    return walk

4. 查询“最后一个”节点实用方法_subtree_last_position

def _subtree_last_position(self, p):
    """返回以位置p处节点为根节点的二叉搜索（子）树中“最后一个”节点的位置"""
    walk = p
    while self.right(walk) is not None:
        walk = self.right(walk)
    return walk

5. 查询“第一个”节点方法first

def first(self):
    """返回该二叉搜索树第一个节点的位置"""
    return self._subtree_first_position(self.root()) if len(self) > 0 else None

6. 查询“最后一个”节点方法last

def last(self):
    """返回该二叉搜索树最后一个节点的位置"""
    return self._subtree_last_position(self.root()) if len(self) > 0 else None

7. 中序遍历时定位前一个位置方法before

def before(self, p):
    """返回中序遍历时，位置p的前一个位置，当位置p为第一个位置时返回None"""
    self._pos2node(p)
    if self.left(p):
        return self._subtree_last_position(self.left(p))
    else:
        walk = p
        ancestor = self.parent(walk)
        while ancestor is not None and walk == self.left(ancestor):
            walk = ancestor
            ancestor = self.parent(walk)
        return ancestor

8. 中序遍历时定位后一个位置方法after

def after(self, p):
    """返回中序遍历时，位置p的后一个位置，当位置p为最后一个位置时返回None"""
    self._pos2node(p)
    if self.right(p):
        return self._subtree_first_position(self.right(p))
    else:
        walk = p
        ancestor = self.parent(walk)
        while ancestor is not None and walk == self.right(ancestor):
            walk = ancestor
            ancestor = self.parent(walk)
        return ancestor

9. 查找指定键所在位置方法find_position

def find_position(self, k):
    """
    如果有序映射非空，则当有序映射中存在键为k的键值对，
    则返回该键值对所在节点在二叉搜索树中的位置，
    不存在则返回最后到达的位置，否则返回None
    """
    if self.is_empty():
        return None
    else:
        return self._subtree_search(self.root(), k)

10. 查找并返回键最小的键值对方法find_min

def find_min(self):
    """
    如有序映射非空，则返回有序映射中键最小的键值对所在节点在二叉搜索树中的位置，
    否则返回None
    """
    if self.is_empty():
        return None
    else:
        p = self.first()
        return p.key(), p.value()

11. 查找并返回不小于指定键的键值对方法find_ge

def find_ge(self, k):
    """查找并返回键不小于k的键值对，如不存在这样的键值对则返回None"""
    if self.is_empty():
        return None
    else:
        p = self.find_position(k)
        if p.key() < k:
            p = self.after(p)
        return p.key(), p.value() if p is not None else None

12. 根据区间查找键值对的方法find_range

def find_range(self, start, stop):
    """
    迭代所有满足start <= key < stop的键值对(key,value)，
    且如果start为None，则迭代从最小的键开始，
    如果stop为None，则迭代到最大的键结束。
    """
    if not self.is_empty():
        if start is None:
            p = self.first()
        else:
            p = self.find_position(start)
            if p.key() < start:
                p = self.after(p)
        while p is not None and (stop is None or p.key() < stop):
            yield p.key(), p.value()
            p = self.after(p)

13. 支持映射通过M[k]获取值的方法__getitem__

def __getitem__(self, k):
    """返回有序映射中键k所对应的值，如键k不存在则抛出KeyError异常"""
    if self.is_empty():
        raise KeyError('Key Error: ' + repr(k))
    else:
        p = self._subtree_search(self.root(), k)
        if k != p.key():
            raise KeyError('Key Error: ' + repr(k))
        return p.value()

14. 支持映射通过M[k] = v设置键值对方法__setitem__

def __setitem__(self, k, v):
    """向有序映射中插入键值对(k, v)，当k存在时替换原有的值"""
    if self.is_empty():
        self._add_root(self._Item(k, v))
    else:
        p = self._subtree_search(self.root(), k)
        if p.key() == k:
            p.element().value = v
            return
        else:
            item = self._Item(k, v)
            if p.key() < k:
                self._add_right(p, item)
            else:
                self._add_left(p, item)

15. 生成映射所有键的迭代方法__iter__

def __iter__(self):
    """生成映射所有键的一个迭代"""
    p = self.first()
    while p is not None:
        yield p.key()
        p = self.after(p)

16. 删除给定位置节点的方法delete

def delete(self, p):
    """删除给定位置处的节点"""
    self._pos2node(p)  # 确保待操作位置的节点依然有效
    if self.left(p) and self.right(p):  # 位置p处有两个子节点
        replacement = self._subtree_last_position(self.left(p))
        self._replace(p, replacement.element())  # 将位置p处节点的键值对进行替换
        p = replacement
    # 这时位置p处至多有一个子节点
    self._delete(p)

17. 支持映射通过del M[k]删除键值对方法__delitem__

def __delitem__(self, k):
    """删除键为k的节点，当键k不存在时抛出KeyError异常"""
    if not self.is_empty():
        p = self._subtree_search(self.root(), k)
        if k == p.key():
            self.delete(p)
            return
    raise KeyError('Key Error: ' + repr(k))

七、有序映射操作时间复杂度

映射操作	最坏时间复杂度
__getitem__	$O(h)$
__setitem__	$O(h)$
__delitem__	$O(h)$
M.delete(p)	$O(h)$
M.find_position(k)	$O(h)$
M.first(), M.last(), M.find_min(), M.find_max()	$O(h)$
M.before(p), M.after(p)	$O(h)$
M.find_ge(k)	$O(h)$
M.find_range(start, stop)	$O(s+h)$
__iter__, __reversed__	$O(n)$

本文地址：https://blog.csdn.net/weixin_37780776/article/details/110100408