SkyBlog

二叉搜索树 BST

查找、插入、删除

这篇文章发布于 2024年02月05日，星期一，01:56，归类于 算法。阅读 ? 次，0 条评论

二叉搜索树（Binary Search Tree），是一种具有以下性质的二叉树：

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值
  • 任意节点的左、右子树也分别为二叉搜索树

节点的结构如下，以力扣为标准

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val == undefined ? 0 : val)
    this.left = (left == undefined ? null : left)
    this.right = (right == undefined ? null : right)
  }
}

查找

二叉搜索树的中序遍历单调递增，中序遍历

插入

701. 二叉搜索树中的插入操作

const insertIntoBST = (root: TreeNode | null, val: number): TreeNode | null => {
  if (root == null) return new TreeNode(val)
 
  if (val < root.val) {
    root.left = insertIntoBST(root.left, val)
  } else if (val > root.val) {
    root.right = insertIntoBST(root.right, val)
  }
 
  return root
}

删除

const deleteNode = (root: TreeNode | null, key: number): TreeNode | null => {
  if (root == null) return root
 
  if (root.val == key) {
    if (root.right == null) return root.left
    else {
      let node = root.right
      while (node.left != null) node = node.left
      node.left = root.left
      return root.right
    }
  }
  if (root.val < key) root.right = deleteNode(root.right, key)
  else root.left = deleteNode(root.left, key)
 
  return root
}