从删除节点操作开始讲起

二叉搜索树的删除操作可以将树中一个给定的节点移除，要被删除的那个节点通过 key 来指定，二叉搜索树中的每个节点都有一个唯一的 key, 也就是说在同一个二叉树中，不存在 key 相等的两个节点。

对于二叉搜索树中节点的删除操作而言，删除函数可被声明为一个签名如下的函数：

function deleteNode<KeyT>(root: Node, key: KeyT): Node;

将函数的返回类型声明为一个非 void 类型是为了：

1. 便于以递归的方式实现，例如，deleteNode 函数在执行的过程中可能会发现：要被删除的那个节点不是当前节点，而是当前节点的左子节点，那么它只需执行 root.left = deleteNode(root.left, key) 即可得到期待的行为。
2. 便于使用，可以通过 node = deleteNode(node, key) 这种方式来使用，使用时不用去考虑 node 是不是 null, 或者 node 被删除后是不是 null .

整体来说，deleteNode 的工作思路是这样的：假定 root 是 truthy 的，那么 deleteNode 判定 key 和 root.key 的相对大小关系，根据判定结果，决定接下来的行为：

1. 若 key < root.key, 那么 deleteNode 进入到左子树，也就是对左子树递归调用自身，拿得到的结果更新左子树；
2. 若 key > root.key, 那么类似的递归对右子树调用自身，拿得到的结果更新右子树；
3. 若 key = root.key, 那么被删除的实际上就是当前节点，deleteNode 需要返回一个排除根节点后，由剩余节点构成的树。

以下是代码：

const deleteNode = <T extends any>(root: Node, key: T) => 
  key < root?.left ? ({ ...root, left: deleteNode(root?.left, key) }) :
  key > root?.right ? ({ ...root, right: deleteNode(root?.right, key) }) : 
  deleteRootNode(root, key);

代码中的 deleteRootNode 函数删除一棵树的根节点，返回这棵树剩下的节点构成树，当然了，在具体实现时不会去从头开始以剩余节点再次构建这棵树（线性时间复杂度），存在对数级别时间复杂度的 deleteRootNode 的实现方法。

这样的 deleteRootNode 的实现依赖 deleteMin, getMin 这两个辅助函数（也可以是 deleteMax，不过道理是类似的），顾名思义，deleteMin 的作用是删除一棵树中 key 最小的那个节点，并且返回一个指针，该指针指向删除操作生效了的那个树，换言之即删除了 min 节点后的树。

getMin 返回一棵树中的 key 最小的节点，以一个指向非有效地址的指针去调用 getMin 会造成未定义行为。

为了实现 deleteRootNode，我们首先来实现 deleteMin 函数：

const deleteMin = 
  (root: Node): Node => 
    root?.left ? ({ ...root, left: deleteMin(root.left) }) : root?.right;

实现 getMin 函数：