二元搜尋樹

二叉搜索树（，简称BST）是一种有根二叉树数据结构。它要求每个内部节点的键值都大于其左子树中所有节点的键值，且都小于其右子树中所有节点的键值。该树各项操作时间复杂度均与树的高度成线性关系。

二叉搜索树每次比较都能排除大约一半的剩余节点，故能以对数时间查找、插入、删除数据。但其性能依赖于节点的插入顺序，插入随机键值时仍能维持对数级别，但在下会退化成链表。为保证效率，研究者发明了多种平衡树，能将最坏查找复杂度维持在。

二叉搜索树最早由多位研究者独立提出，1960年被用来解决带标签数据的存储问题。其还可用来实现及优先队列。

 历史 
二叉搜索树最早由多位研究者独立提出，包括P.F.温德利、安德鲁·唐纳德·布思、安德鲁·科林、托马斯·N·希巴德。这种数据结构常被归功于及，他们在1960年将之用于磁带上带标签数据的存储。希巴德实现二叉搜索树的方法也是最早广为流传的一种。

若按任意顺序插入节点，树的高度可能接近节点数，导致操作效率急剧下降。研究者们发明了平衡树（即能够自平衡的二叉搜索树），将树的高度限制在以内。同时，相关人员也提出了多种高度平衡的二叉搜索树结构，例如AVL树、树堆、红黑树等。其中，AVL树是首类平衡树，由格奥尔吉·阿杰尔松-韦利斯基及叶夫根尼·兰迪斯于1962年发明，用于高效组织信息。

 性质 
二叉搜索树为有的二叉树，其节点顺序为严格全序关系，每个节点都满足：左子树上所有节点的键值都小于该节点，右子树上所有节点的键值都大于该节点。这一结构保证可以在对数时间内定位任意键值。除查找外，其也常用于排序，但性能取决于节点的插入和删除顺序——在下，连续操作可能使树退化为类似单链表的结构，这时的查找复杂度与链表相同。

 遍历 

二叉搜索树的遍历有三种基本方法：前序、中序、后序。
 中序遍历：依次遍历左子树、根节点、右子树。遍历结果为键值递增顺序。
 前序遍历：依次遍历根节点、左子树、右子树。
 后序遍历：依次遍历左子树、右子树、根节点。

以下是递归实现的遍历伪代码：

  Inorder-Tree-Walk(x)
    if x ≠ NIL then
      Inorder-Tree-Walk(x.left)
      visit node
      Inorder-Tree-Walk(x.right)
    end if  Preorder-Tree-Walk(x)
    if x ≠ NIL then
      visit node
      Preorder-Tree-Walk(x.left)
      Preorder-Tree-Walk(x.right)
    end if  Postorder-Tree-Walk(x)
    if x ≠ NIL then
      Postorder-Tree-Walk(x.left)
      Postorder-Tree-Walk(x.right)
      visit node
    end if

 操作 
 搜索 
在二叉搜索树中查找某个特定的键，可以使用递归或迭代方式实现。

查找过程从树的开始：

 如果根节点为空（），说明该键不存在。
 如果根节点的键值与目标键值相等，返回该节点，表示查找成功。
 如果目标键值小于根节点的键值，则继续在左子树中查找；
 如果目标键值大于根节点的键值，则继续在右子树中查找。
重复上述步骤，直到找到该键，或者剩余子树为空。若到达空子树仍未找到，说明该键不存在于树中。

 递归搜索 
以下伪代码展示递归方式实现的查找过程：

 Recursive-Tree-Search(x, key)
     if x = NIL or key = x.key then
         return x
     if key < x.key then
         return Recursive-Tree-Search(x.left, key)
     else
         return Recursive-Tree-Search(x.right, key)
     end if

递归会一直进行，直到遇到或是找到目标键。

 迭代搜索 
递归过程也可展开为循环形式，一般情况下循环版本的效率更高。其伪代码如下：

 Iterative-Tree-Search(x, key)
     while x ≠ NIL and key ≠ x.key do
         if key < x.key then
             x := x.left
         else
             x := x.right
         end if
     repeat
     return x

由于查找可能会一直到叶节点，因此时间复杂度为树的高度（为树的高度）。在最坏情况下，一棵严重不平衡的二叉搜索树可能退化成单链表，这时复杂度会达到（为树中节点总数）。但对于高度平衡的二叉搜索树而言，复杂度为。

 后继与前驱 
在某些场景下，需要查找给定节点的「后继」或「前驱」。后继节点是大于该节点键值的节点中，键值最小的那一个；前驱节点是小于该节点键值的节点中，键值最大的那一个。以下伪代码给出求节点的后继与前驱方法：

  BST-Successor(x)
      if x.right ≠ NIL then
          return BST-Minimum(x.right)
      end if
      y := x.parent
      while y ≠ NIL and x = y.right do
          x := y
          y := y.parent
      repeat
      return y  BST-Predecessor(x)
      if x.left ≠ NIL then
          return BST-Maximum(x.left)
      end if
      y := x.parent
      while y ≠ NIL and x = y.left do
          x := y
          y := y.parent
      repeat
      return y

寻找树中键值最大或最小的节点，是寻找后继与前驱过程中的重要环节。其伪代码如下：

  BST-Maximum(x)
      while x.right ≠ NIL do
          x := x.right
      repeat
      return x  BST-Minimum(x)
      while x.left ≠ NIL do
          x := x.left
      repeat
      return x

 选择与排名 
若在节点中维护以之为根节点的子树的节点总数，则可实现选择与排名操作。选择操作用于在树中直接定位排名为的节点，即第小的键。排名操作则与之相对，给定指定键后，其会返回小于该键的节点数。这两种操作的伪代码如下：

  Select‑By‑Rank(T, k)
      return Select(T.root, k)
  Select(x, k)
      if x = NIL then
          return NIL
      end if
      t := size(x.left)
      if t > k then
          return Select(x.left, k)
      else if t < k then
          return Select(x.right, k − t − 1)
      else
          return x
      end if

  Rank-In-Tree(T, key)
      return Rank(key, T.root)
  Rank(key, x)
      if x = NIL then
          return 0
      cmp := compare(key, x.key)
      if cmp < 0 then
          return Rank(key, x.left)
      else if cmp > 0 then
          return 1 + size(x.left) + Rank(key, x.right)
      else
          return size(x.left)
      end if

其中size表示子树规模信息，即子树中节点数量。

 范围查找 
利用中序遍历，可以实现，即查询两个给定值之间的元素数量。其伪代码如下：

  Range-Query(x, lo, hi, list)
      if x = NIL then
          return
      end if
      if lo < x.key then
          Range-Query(x.left, lo, hi, list)
      end if
      if lo ≤ x.key ≤ hi then
          list.append(x.key)
      end if
      if hi > x.key then
          Range-Query(x.right, lo, hi, list)
      end if

其中list是用来收集结果的列表（也可视作队列）。上述过程将所有符合条件的值加入列表中，并跳过不可能含有目标值的子树。

 插入 
二叉搜索树的数据结构会随插入和删除操作而变化。插入操作须保证二叉搜索树的性质不会遭到破坏，且插入的节点总是作为叶节点加入。以下伪代码给出迭代形式的插入过程：

 1    BST-Insert(T, z)
 2      y := NIL
 3      x := T.root
 4      while x ≠ NIL do
 5        y := x
 6        if z.key < x.key then
 7          x := x.left
 8        else
 9          x := x.right
 10       end if
 11     repeat
 12     z.parent := y
 13     if y = NIL then
 14       T.root := z
 15     else if z.key < y.key then
 16       y.left := z
 17     else
 18       y.right := z
 19     end if

过程使用变量作为遍历节点的父节点（追踪指针）。初始时如果为，说明树为空，新节点即作为树的根；否则，需根据节点键值大小关系插入对应位置。

 删除 

从树中删除某个节点时，需分三种情况处理：
 是叶节点：直接用空指针替换即可。（如图中(a)）
 仅有一个子节点：用的子节点替换。（如图中(b)、(c)）
 有两个子节点：用的中序遍历所得到的后继或前驱代替。此处以后继为例：
 如果恰好是的右子节点：直接用取代，的右子树保持不变。（如图中(d)）
 如果位于的右子树内部：先用的右子节点替换，再用替代。（如图中(e)）

以下伪代码实现删除操作：

 1    BST-Delete(BST, z)
 2      if z.left = NIL then
 3        Shift-Nodes(BST, z, z.right)
 4      else if z.right = NIL then
 5        Shift-Nodes(BST, z, z.left)
 6      else
 7        y := BST-Successor(z)
 8        if y.parent ≠ z then
 9          Shift-Nodes(BST, y, y.right)
 10         y.right := z.right
 11         y.right.parent := y
 12       end if
 13       Shift-Nodes(BST, z, y)
 14       y.left := z.left
 15       y.left.parent := y
 16     end if 1    Shift-Nodes(BST, u, v)
 2      if u.parent = NIL then
 3        BST.root := v
 4      else if u = u.parent.left then
 5        u.parent.left := v
 5      else
 6        u.parent.right := v
 7      end if
 8      if v ≠ NIL then
 9        v.parent := u.parent
 10     end if

过程根据上述3种情况处理节点删除：第1种情况（叶节点）对应第2—3行；第2种情况（单个子节点）对应第4—5行；第3种情况（有两个子节点）对应第6—16行。辅助函数用于把节点替换成。

若在第3种情况中，仅选用后继或前驱节点中的一种，则并未考虑到树的对称性，可能会导致性能问题。若要避免此问题，可以随机选择使用后继或前驱。

 平衡树 

普通的二叉搜索树中，若不加以平衡，插入或删除操作可能会导致树退化。若是使用随机键值构建二叉搜索树，那么平均高度仍能维持在对数级别（当节点数足够大时，高度趋近于）；但在下，高度会达到节点数，查找性能退化至线性搜索的-{zh:水平;zh-hans:水平;zh-hant:水平;zh-tw:水準;}-。要保持二叉搜索树的高效，关键在于通过「自平衡」机制，使树的高度始终维持在级别。

 高度平衡树 
若一棵树的任意节点，其左右子树高度之比都被某个常数所限制，就称其为高度平衡树。这一思想最早在AVL树中使用，后续的红黑树也沿用了类似机制。每次执行插入或删除操作后，需要沿着从根到修改节点的路径，检查并修正各节点的高度，以维持平衡。

 加权平衡树 

在加权平衡树中，平衡条件不再以高度衡量，而是以子树的叶节点数量为准。叶节点数量即代表权重，左右子树的权重差最多为常数。但单纯依靠差值，难以在插入和删除时用的代价维护，因此引入比例因子，要求左右子树的权重各自至少占整棵子树权重的比例，由此形成-权重平衡树族。

 其他类型 
常见的自平衡二叉搜索树包括：、树堆、红黑树、B树、2-3树、伸展树。

 应用 
 排序 

二叉搜索树可用于树排序：先将所有元素插入二叉搜索树中，然后对树做中序遍历，即可得到有序序列。在快速排序的某些实现中，也可借助二叉搜索树来提高性能。

 优先队列 

二叉搜索树也可用来实现优先队列，借助节点的键值来表示优先级。插入操作与普通的二叉搜索树相同，但删除操作取决于优先队列的类型：

 升序优先队列：移除最低优先级元素时，从根节点向左一路遍历即可找到最小键。
 降序优先队列：移除最高优先级元素时，从根节点向右一路遍历即可找到最大键。

 参见 

 搜索树
 最优二叉搜索树

 三叉搜索树

 脚注 
 注释 

 来源 

 延伸阅读 







 外部链接 

 的教学视频：
 Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. (PDF; 1675 kB) 2004. 

Category:带有伪代码示例的条目
Category:二叉树
Category:搜索树