为了叙述方便，在不引起歧义的情况下，本文把节点关键字的值简称为节点或节点的值。

概念

显然，二叉搜索树（Binary Search Tree）是一颗二叉树。但与普通的二叉树不同的是，对于BST的每个节点，它的左子树中的所有节点（如果有的话）的值都不大于该节点的值；它的右子树中的所有节点（如果有的话）的值都不小于该节点的值。

  1. TREENODE:
  2.     parent,
  3.     left,
  4.     right,
  5.     val

查询二叉搜索树

查找

由于BST的特殊结构，查找操作是非常简单的：

  1. 判断当前节点node是否为空节点；若是，则返回null（表示没找到target），否则进行第二步。
  2. 比较node的值val与目标值target的大小
    1. 如果val < target：那么在node右子树node.right中查找，返回第一步
    2. 如果val > target：那么在node左子树node.left中查找，返回第一步
    3. 如果val == target：返回node（表示存在）
      1. BST_SEARCH(node, target):
      2. if node == null or node.val == target:
      3.   return node
      4. if node.val < target:
      5.   return BST_SEARCH(node.right, target)
      6. else:
      7.   return BST_SEARCH(node.left, target)
      1. BST_SEARCH(node, target):
      2. while node != null and node.val != target:
      3.   if node.val < target:
      4.       node = node.right
      5.   else:
      6.       node = node.left
      7. return node
      时间复杂度：二叉搜索树 - 图1。

最大元和最小元

只要BST非空，那么它总存在最大元和最小元：

  • 从根节点root出发，沿着左子树一直前进到最后一个非空节点，该节点就是最小元
  • 同理，从根节点root出发，沿着右子树一直前进到最后一个非空节点，该节点就是最大元
    1. BST_MIN(root):
    2.   while root.left != null:
    3.       root = root.left
    4.   return root
    1. BST_MAX(root):
    2.   while root.right != null:
    3.       root = root.right
    4.   return root

    后继和前驱

    如果所有节点互不相同，一个节点的后继是大于该节点的最小节点，前驱是小于该节点的最大节点。把BST看成一个升序数组（事实上，就是中序遍历BST生成的数组），那么一个节点的前驱就是前一个节点，后继就是后一个节点。显然，最小的节点没有前驱，最大的节点没有后继。

回到BST中，一个节点node的前驱：

  • 如果node存在左子树，那么node的前驱就是node.left中最大元素
  • 如果node不存在左子树，且node的父节点node.parent存在：
    • 若node是node.parent的左子树，令node = node.parent，重复此行为
    • 若node是node.parent的右子树，返回其父节点node.parent

  • 如果node不存在左子树，且node的父节点不存在，那么node没有后继

    1. BST_PREDECESSOR(node):
    2.   if node.left != null:
    3.       return BST_MAX(node.left)
    5.   p_node = node.parent
    6.   while p_node != null and node == p_node.left:
    7.       node = p_node
    8.       p_node = node.parent
    9.   return p_node

    节点node的后继就是前驱的对称：

    1. BST_SUCCESSOR(node):
    2.   if node.right != null:
    3.       return BST_MIN(node.right)
    4.   p_node = node.parent
    5.   while p_node != null and node == p_node.right:
    6.       node = p_node
    7.       p_node = node.parent
    8.   return p_node

    时间复杂度：二叉搜索树 - 图2。
    即使存在相同节点的值，我们可以定义前驱和后继为BST_PREDECESSOR(node)和BST_SUCCESSOR(node)的值。

    插入和删除

    插入

    插入很简单，首先按BST_SEARCH的方法找到待插入的节点位置，在判断该节点是其父节点的左子节点还是右子节点。 ``` BST_INSERT(root, x): temp_node = root while root != null:

    1.   temp_node = root
    2.   if root.val < x.val:
    3.       root = root.right
    4.   else:
    5.       root = root.left

    x.parent = temp_node if temp_node == null:

    1.   return x         # 空树返回x

    else if temp_node.val < x.val:

    1.   temp_node.right = x

    else:

    1.   temp_node.left = x

    return null # 表示不是空树

  1. <a name="u574z"></a>
  2. ### 删除
  3. 删除节点`x`时，可以分三种情况讨论：
  5. - `x`没有子节点：直接删除`x`即可
  6. - `x`只有一个子节点：直接将子节点放到`x`的位置上即可
  7. - `x`有两个子节点：那么`x`的后继必然在右子树中，命名为`y`。`y`的左子节点必然是空的，将`y`与`x`的位置交换，将`y.right`放到原来`y`的位置上

BST_DELETE(root, x): if x.left == null and x.right == null: if x == x.parent.left: x.parent.left = null else: x.parent.right = null else if x.left == null: if x == x.parent.left: x.parent.left = x.right x.right.parent = x.parent else: x.parent.right = x.right x.right.parent = x.parent else if x.right == null: if x == x.parent.left: x.parent.left = x.left x.left.parent = x.parent else: x.parent.right = x.left x.left.parent = x.parent else: y = BST_SUCCESSOR(x) if y == x.right: x.parent.left = y y.parent = x.parent y.left = x.left else: y.parent.left = y.right y.right.parent = y.parent y.left = x.left y.right = x.right y.left.parent = y y.right.parent = y y.parent = x.parent if x == x.parent.left: y.parent.left = y else: y.parent.right = y ``` 时间复杂度：二叉搜索树 - 图3