二叉搜索树与平衡树

// 运行环境：Node.js 14+
// 保存为 dsa-l12.js，执行：node dsa-l12.js

class TreeNode {
  constructor(val) { this.val = val; this.left = null; this.right = null }
}

function insert(root, val) {
  if (!root) return new TreeNode(val)
  if (val < root.val) root.left = insert(root.left, val)
  else if (val > root.val) root.right = insert(root.right, val)
  return root
}

function search(root, val) {
  while (root) {
    if (val === root.val) return root
    root = val < root.val ? root.left : root.right
  }
  return null
}

// 删除：①叶子直接删 ②单子节点接上 ③双子节点→用"后继"(右子树最小)替身
function remove(root, val) {
  if (!root) return null
  if (val < root.val) root.left = remove(root.left, val)
  else if (val > root.val) root.right = remove(root.right, val)
  else {
    if (!root.left) return root.right
    if (!root.right) return root.left
    let succ = root.right
    while (succ.left) succ = succ.left
    root.val = succ.val
    root.right = remove(root.right, succ.val)
  }
  return root
}

// 中序验证 BST（升序即通过）
function isValidBST(root, prev = { v: -Infinity }) {
  if (!root) return true
  if (!isValidBST(root.left, prev)) return false
  if (root.val <= prev.v) return false
  prev.v = root.val
  return isValidBST(root.right, prev)
}

let r = null
;[5, 3, 7, 2, 4].forEach(v => r = insert(r, v))
console.log(search(r, 4)?.val, isValidBST(r)) // 4 true