什么是二叉搜索树？

二叉搜索树（BST）是一种特殊的二叉树，它具有以下性质：

• 每个节点的左子树中所有节点的值都小于该节点的值。
• 每个节点的右子树中所有节点的值都大于该节点的值。
• 左右子树也都是二叉搜索树。

这个性质使得在树中进行查找、插入和删除等操作非常高效。

基本操作

• 查找 (Search): 从根节点开始，如果目标值小于当前节点，则在左子树中继续查找；如果大于，则在右子树中查找。
• 插入 (Insert): 类似于查找，找到一个空位插入新节点，同时保持 BST 的性质。
• 删除 (Delete): 这是最复杂的操作，需要考虑三种情况：
  1. 要删除的节点是叶子节点。
  2. 要删除的节点只有一个子节点。
  3. 要删除的节点有两个子节点。