共计 2189 个字符，预计需要花费 6 分钟才能阅读完成。

算法里有一种数据结构叫二叉树，其中又有一种特殊形态，叫做“二叉搜索树”，今天我们就来聊一聊。

什么是二叉搜索树

其形式就是二叉树，对于每个节点 x，其左子树的值 <=x.value，右子树的值 >=x.value。

二叉搜索树的遍历与查询

遍历

对于二叉搜索树，我们可以使用中序遍历，得到树上从小到大所有的元素。时间复杂度平均为 O(n)。

function inorderTreeWalk(x) {if(x!== null) {inorderTreeWalk(x.left);
    print(x.key);
    inorderTreeWalk(x.right);
  }
}

查询关键字

当我们想要查询二叉搜索树中某个关键字应该怎么做呢？由于二叉搜索树左子树和右子树的特点，我们很容易写出：

function treeSearch(x,k) {  // 最开始 x 代表根节点
  if(x === null || x.key === k) {return x;}
  if(k < x.key) {return treeSearch(x.left, k);
  } else {return treeSearch(x.right, k);
  }
}

我们还可以写出循环版本（一般比递归更高效）:

function treeSearch(x, k) {while(x !== null || k !== x.key) {if(k < x.key) {x = x.left;} else {x = x.right;}
  }
  return x;
}

查询最小元素和最大元素

我们很容易可以找到二叉搜索树中的最小元素和最大元素，其查找时间复杂度为 O(lgn)：

function treeMinimum(x) {while(x.left !== null) {x = x.left;}
  return x;
}

function treeMaximum(x) {while(x.right !== null) {x = x.right;}
  return x;
}

有时候我们需要按中序遍历查找二叉搜索树某个节点的后继和前驱。

分析二叉搜索树性质可知，如果该节点右子树不为空，则它的后继应该是右子树中的最小元素；若右子树为空，则该节点的后继应该是其双亲有左子树的父节点。前驱则与其对称. 时间复杂度 O(lgn)：

function treeSuccessor(x) {  // 后继查找
  if(x.right !== null) {return treeMinimum(x.right);
  } else {
    let y = x.parent;
    while(y !== null && x === y.right) {
      x = y;
      y = y.parent;
    }
    return y;
  }
}

function treeSuccessor(x) {  // 前驱查找
  if(x.left !== null) {return treeMaximum(x.left);
  } else {
    let y = x.parent;
    while(y !== null && x === y.left) {
      x = y;
      y = y.parent;
    }
    return y;
  }
}

二叉搜索树实现插入和删除操作。

插入

插入相对比较简单，我们只要遍历二叉树把值插入到合适的位置就行了。

function treeInsert(tree, newNode) {
  let y = null;
  while(tree !== null) {
    y = tree;
    if(newNode.key < tree.key) {tree = tree.left;} else {tree = tree.right;}
  }
  newNode.parent = y;
  if(y === null) {  // 树为空
    tree.root = newNode;
  } else {if(newNode.key < y.key) {y.left = newNode;} else {y.right = newNode;}
  }
}

删除

删除操作相对较复杂。假如删除 z 节点，我们考虑三种情况：z 没有子节点、z 有一个子节点、z 有两个子节点。
- 第一种情况：z 没有子节点，则直接删除 z，修改父节点属性，用 null 代替 z。
- 第二种情况：z 只有一个子节点，则用子节点代替 z。
- 第三种情况：z 有两个子节点，我们需要找到 z 的后继 y，y 肯定在 z 的右子树并且没有左孩子，当 y 恰好是 z 的右子节点，则直接用 y 替代 z，并留下 y 的右孩子；否则先用 y 的右子节点替代 y，再用 y 替代 z。

function transplant(tree, u, v) {  // 子树替换父节点方法
  if(u.p === null) {tree.root = v;} else if(u === u.parent.left) {u.parent.left = v;} else {u.parent.right = v;}
  if(v !== null) {v.parent = u.parent;}
}

function treeDelete(tree, z) {if(z.left === null) {transplant(tree, z, z.right);
  } else if(z.right === null) {transplant(tree, z, z.left);
  } else {let y = treeMinimum(z.right);
    if(y.parent !== z) {transplant(tree, y, y.right);
      y.right = z.right;
      y.right.parent = y;
    }
    transplant(tree, z, y);
    y.left = z.left;
    y.left.parent = y;
  }
}

至此，我们完成了二叉搜索树的 js 实现。具体算法证明参考《算法导论》