二叉搜索树的定义与操作

二叉搜索树的性质是什么？

• 定义: 任一节点的左子树所有节点值都小于它, 右子树所有节点值都大于它;
• 推论: 中序遍历得到严格递增的序列;
• 约定: 标准二叉搜索树不存放重复值;

如何查找节点？

• 步骤: 从根节点开始比较, 小于当前值走向左子树, 大于走向右子树, 相等即命中;
• 复杂度: 理想 O(log n), 退化成链表时 O(n);

const find = (node, value) => {
  while (node != null) {
    if (node.val === value) return node;
    node = value < node.val ? node.left : node.right;
  }
  return null;
};

如何插入节点？

• 步骤: 按查找规则走到空位置, 在那里挂上新节点;
• 重复值: 已存在时不做改动;

const insert = (node, value) => {
  if (node == null) return new TreeNode(value);
  if (value < node.val) node.left = insert(node.left, value);
  else if (value > node.val) node.right = insert(node.right, value);
  return node;
};

如何删除节点？

• 叶子节点: 直接删除;
• 只有一个子节点: 用该子节点顶替;
• 有两个子节点: 用右子树的最小节点 (或左子树的最大节点) 替换当前值, 再删掉那个替换节点;
• 选择理由: 替换值仍满足左小右大, 其余结构不动;

const remove = (node, value) => {
  if (node == null) return null;
  if (value < node.val) node.left = remove(node.left, value);
  else if (value > node.val) node.right = remove(node.right, value);
  else {
    if (node.left == null) return node.right;
    if (node.right == null) return node.left;
    let min = node.right;
    while (min.left != null) min = min.left;
    node.val = min.val;
    node.right = remove(node.right, min.val);
  }
  return node;
};

效率如何？

场景	查找	插入	删除
理想 (平衡)	O(log n)	O(log n)	O(log n)
退化 (链表)	O(n)	O(n)	O(n)

• 结论: 二叉搜索树的效率完全取决于树高, 自平衡结构见 插入删除与再平衡;