算法导论第12章 二叉搜索树

12.1 什么是二叉搜索树

二叉搜索树以二叉树的结构组织, 每个结点包含key, 卫星数据, left(指向左孩子), right(指向右孩子), p(指向双亲). 二叉搜索树满足以下性质: 对于每个结点\(x\) , 其左子树上的结点不大于\(x\) , 右子树上的结点不小于\(x\) .

中序遍历二叉搜索树, 可以按序输出树中所有关键字.

# 调用下面的过程inorder_tree_walk(T.root)可以按序输出二叉搜索树T中所有元素inorder_tree_walk(x):  if x is not None:    inorder_tree_walk(x.left)    print x.key    inorder_tree_walk(x.right)

定理12.1 : 如果\(x\) 是一棵有n个结点子树的根, 那么调用 inorder_tree_walk(x) 需要\(\Theta(n)\) 时间.

12.2 查询二叉搜索树

SEARCH

# 调用下面的过程recurrsive_tree_search(x,k), 其中x为根结点, k为关键字.# 如果关键字为k的结点存在, 返回一个指向关键字为k的结点的引用; 否则返回Nonerecurrsive_tree_search(x,k):  if (x is None) or (k == x.key):    return x  if k < x.key:    return tree_search(x.left)  else:    return tree_search(x.right)

# 调用下面的过程iterative_tree_search(x,k), 其中x为根结点, k为关键字.# 如果关键字为k的结点存在, 返回一个指向关键字为k的结点的引用; 否则返回Noneiterative_tree_search(x,k):  while (x is not None) and (k != x.key):    if k < x.key:      x = x.left    else:      x = x.right  return x

MAXIMUM & MINIMUM

# x为根结点# 返回最小结点tree_minimum(x):  while x.left is not None:    x = x.left    return x

# x为根结点# 返回最大结点tree_maximum(x):  while x.right is not None:    x = x.right    return x

以上过程在一棵高度为h的树上均能在O(h)时间内执行完.

SUCCESSOR & PREDECESSOR

# x是根结点# 若x的后继存在, 返回其后继结点# 若x是最大关键字, 返回Nonetree_successor(x):  # 若x的右子树非空, 则x的后继为右子树中的最小结点  if x.right is not None:     return tree_minimum(x.right)  # 若x的右子树为空, 则x是某棵树T的最大结点(最右下角)  # 找到满足x是其最右下角的最大的子树T, 则x的结点为T.p.  # 具体做法是一直往父结点找, 一直找到一个有左子树的根结点T.  y = x.p  while (y is not None) and (x == y.right):    x = y    y = y.p  return y

# x是根结点# 若x的前驱存在, 返回其前驱结点# 若x是最小关键字, 返回Nonetree_predecessor(x):  # 若x的左子树非空, 则x的前驱为左子树中的最大结点  if x.left is not None:     return tree_maximum(x.left)  # 若x的左子树为空, 则x是某棵树T的最小结点(最左下角)  # 找到满足x是其最左下角的最大的子树T, 则x的结点为T.p.  # 具体做法是一直往父结点找, 一直找到一个有右子树的根结点T.  y = x.p  while (y is not None) and (x == y.left):    x = y    y = y.p  return y

定理12.2 : 在一棵高度为h的二叉搜索树上, 动态集合上的操作SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR可以在O(h)时间内完成.

12.3 插入和删除

INSERT

# T是一棵二叉搜索树(根结点)# z是一个新结点, 其中z.key=v, z.left=None, z.right=Nonetree_insert(T, z):  # y用来找z的父节点  y = None  # x用来遍历  x = T.root  # 确定父节点  while x is not None:    y = x    if z.key < x.key:      x = x.left    else:      x = x.right  # 插入  z.p = y  if y is None:    T.root = z  else if z.key < y.key:    y.left = z  else:    y.right = z

DELETE

从一棵二叉搜索树T中删除一个结点z分为三种基本情况:

• 若z没有孩子结点, 简单删除并修改其父结点.
• 若z只有一个孩子结点, 用这个孩子代替z的位置.
• 若z有两个孩子, 找z的后继(或前驱)y, 并让y代替z的位置.

实际算法中可以这样实现:

• 若z没有左孩子, 则用右孩子代替z的位置. (包括了没有右孩子的情况).
• 若z有左孩子:
  • 若z没有右孩子, 则用左孩子代替z的位置.
  • 若z有右孩子, 找出z的后继y:
    • 若y是z的右孩子, 用y替换z的位置.
    • 若y不是z的右孩子, 先用y的右孩子替换y, 再用y替换z.

# 用一棵以v为根结点的子树替换一棵以u为根结点的子树# u的双亲变成v的双亲, v成为u的双亲的相应孩子# 注: v可以看作是一棵新的树, 可以不是原树T的子树transplant(T, u, v):  # u是T的根  if u.p is None:    T.root = v  # u是父结点的左孩子  else if u == u.p.left:    u.p.left = v  # u是父结点的右孩子  else:    u.p.right = v  if v is not None:    v.p = u.p

# 从二叉搜索树T中删除结点z# 流程见上面实际算法的实现tree_delete(T, z):  if z.left is None:    transplant(T, z, z.right)  else if z.right is None:    transplant(T, z, z.left)  else:    y = tree_minimum(z.right)    if y.p != z:      transplant(T, y, y.right)      y.right = z.right      y.right.p = y    transplant(T, z, y)    y.left = z.left    y.left.p = y

定理12.3 : 在一棵高度为h的二叉搜索树上, 实现动态集合操作INSERT和DELETE的运行时间均为O(h).

12.4 随机构建二叉搜索树

随机构建二叉搜索树: 按随机次序插入这些关键字到一棵初始的空树中而生成的树.

定理12.4 : 一棵有n个不同关键字的随机构建二叉搜索树的期望高度为O(lgn).