二叉搜索树 BST

自平衡二叉搜索树

AVL树

红黑树

二叉搜索树的前驱节点和后继节点

前驱结点：节点val值小于该节点val值并且值最大的节点

后继节点：节点val值大于该节点val值并且值最小的节点

https://www.cnblogs.com/xiejunzhao/p/f5f362c1a89da1663850df9fc4b80214.html

BST（Binary Search Tree）指的是二叉搜索树，也称为二叉查找树或有序二叉树。它是一种特殊的二叉树结构，具有以下特性：

核心特性

1. 左子树值更小：每个节点的左子树所有节点的值都小于该节点的值。
2. 右子树值更大：每个节点的右子树所有节点的值都大于该节点的值。
3. 无重复值：通常每个节点的值唯一（某些实现允许重复值）。
4. 中序遍历有序：对 BST 进行中序遍历（左→根→右），可得到升序排列的数据。

示例结构

      5
     / \
    3   7
   / \ / \
  1  4 6  8

• 根节点是 5，左子树 {1,3,4} 均小于 5，右子树 {6,7,8} 均大于 5。

• 每个子树

  也满足 BST 特性，例如：

  • 节点 3 的左子树是 1（小于 3），右子树是 4（大于 3）。

主要操作

1. 插入（Insert）
   • 从根节点开始比较，若值小于当前节点，则往左子树插入；否则往右子树插入。
   • 时间复杂度：平均 O(log**n)，最坏 O(n)（退化为链表时）。
2. 查找（Search）
   • 类似插入，从根节点开始比较，直到找到目标值或遍历到叶子节点。
   • 时间复杂度：平均 O(log**n)，最坏 O(n)。
3. 删除（Delete）
   • 若节点是叶子节点，直接删除；若有一个子节点，则用子节点替换；若有两个子节点，则用右子树的最小节点（或左子树的最大节点）替换。
   • 时间复杂度：平均 O(log**n)，最坏 O(n)。

应用场景

• 高效搜索与排序：适合动态数据集合的快速插入、删除和查找（如数据库索引）。
• 优先队列：通过维护 BST 可实现高效的优先队列。
• 范围查询：利用 BST 结构快速找到某个范围内的所有值。

与普通二叉树的区别

注意事项

• 平衡性：若插入顺序不当（如按升序插入），BST 会退化为链表，导致操作效率降为 O(n)。为避免此问题，可使用平衡二叉搜索树（如 AVL 树、红黑树）。
• 递归特性：BST 的插入、查找等操作通常用递归实现，但需注意深度过大时的栈溢出风险。

如果需要进一步了解 BST 的实现代码或应用案例，可以继续提问！ 😊

二叉搜索树不研究修改么？

二叉搜索树（BST）的修改操作是其核心功能之一，主要包括插入、删除和更新。这些操作会改变树的结构，但必须保证修改后仍满足 BST 的特性（左子树值 < 根节点值 < 右子树值）。

1. 插入操作（Insertion）

插入新节点时，需根据节点值的大小递归找到合适的叶子位置，保证插入后仍满足 BST 特性。

示例步骤： 插入 2 到以下 BST：

    3
   / \
  1   4

• 比较 2 < 3，向左子树走；
• 比较 2 > 1，向右子树走（此时为空）；
• 插入 2 作为 1 的右子节点。

结果：

    3
   / \
  1   4
   \
    2

2. 删除操作（Deletion）

删除节点时需考虑三种情况：

1. 叶子节点：直接删除。

2. 只有一个子节点：用子节点替换被删除节点。

3. 有两个子节点

   ：

   • 方法一：用右子树的最小节点（即右子树中最左边的节点）替换。
   • 方法二：用左子树的最大节点（即左子树中最右边的节点）替换。

示例步骤： 删除 3 节点：

    3
   / \
  1   4
   \
    2

• 3 有两个子节点，用右子树的最小节点 4 替换；
• 删除原 4 节点（此时 4 为叶子节点）。

结果：

    4
   /
  1
   \
    2

3. 更新操作（Update）

更新节点值时，需先删除原节点，再插入新值的节点，以确保 BST 特性。

示例步骤： 将 2 更新为 5：

    4
   /
  1
   \
    2

• 删除 2 节点；
• 插入 5 节点（因 5 > 4，成为 4 的右子节点）。

结果：

    4
   / \
  1   5

4. 修改操作的复杂度

• 时间复杂度：平均 O(logn)，最坏 O(n)（退化为链表时）。
• 空间复杂度：递归实现时为 O(h)（h 为树的高度）。

5. 平衡二叉搜索树的优化

普通 BST 在频繁插入 / 删除后可能失衡（如退化为链表），导致操作效率下降。因此实际应用中常使用自平衡 BST（如 AVL 树、红黑树），通过旋转操作保证树的高度始终为 O(logn)，从而将修改操作的最坏时间复杂度优化到 O(logn)。

为什么 BST 重视修改操作？

• 动态数据结构：BST 的优势在于支持高效的动态插入、删除和查询，适合需要频繁更新的场景（如数据库索引）。
• 维持有序性：通过中序遍历可始终保持数据的有序性，这是其他数据结构（如哈希表）无法做到的。

logn

在计算机科学和数学中， log*n* 通常指以 2 为底的对数（二进制对数），表示 将数值 *n* 连续除以 2 直到结果为 1 所需的次数。它是算法复杂度分析中最常见的时间复杂度之一，代表一种 「指数级缩减」或「分治」的效率。

数学定义

• 一般形式：若 a**x=n，则 loga**n=x（a 为底数，n 为真数）。

• 计算机领域的默认情况

  ：

  若无特殊说明，

  logn

  通常指

  以 2 为底的对数

  （写作

  log2n

  ），例如：

  • log28=3（因为 23=8），
  • log216=4（因为 24=16）。 这是因为计算机中数据常以二进制形式存储，算法（如二分查找、树结构）也常基于二分逻辑。

在算法复杂度中的意义

logn 表示算法的执行时间随输入规模 n 的增长呈 对数级增长，这是一种非常高效的复杂度，仅次于常数时间 O(1)。 常见场景包括：

1. 二分查找：每次将问题规模减半，最多需要 log2n 次查找。
2. 平衡树操作：如 AVL 树、红黑树的插入 / 删除 / 查找，时间复杂度为 O(logn)。
3. 分治算法：如归并排序、快速排序（平均情况），递归深度为 O(logn)。

直观理解：对数增长的速度

• 与线性增长对比

  ：

  当

  n

  很大时，

  logn

  的值远小于

  n

  。例如：

  n	log2n（约）	n
  1024	10	1024
  1,048,576	20	1,048,576
  1,073,741,824	30	1,073,741,824
  可见，即便 n 达到十亿级，logn 仅为 30 左右，增长极其缓慢。

不同底数的对数：复杂度等价性

在算法分析中，不同底数的对数属于同一复杂度量级，因为： loga​n=logb​alogb​n​ 其中 logb​a 是常数，根据大 O 符号的定义，常数因子可忽略。因此：

• log2n、log10n、lnn（自然对数，底数为 e）在复杂度中均视为 O(logn)。

常见误区

• 问：logn 中的 n 一定是输入规模吗？ 答：不一定。例如，在计算树的高度时，n 是节点数，logn 表示树的高度；在二分查找中，n 是数组长度。
• 问：为什么对数复杂度比线性复杂度优？ 答：对数函数是线性函数的反函数。线性复杂度 O(n) 表示操作次数与 n 成正比，而对数复杂度 O(logn) 表示操作次数随 n 增长呈「指数级减速」，效率差异巨大。

总结

• 本质：logn 是「将问题规模不断减半」的数学抽象，体现了分治思想的高效性。
• 应用场景：几乎所有涉及「二分」「分治」「平衡树」的算法都会出现 logn 复杂度。
• 核心价值：通过数学上的对数特性，将指数级问题转化为多项式级问题，大幅提升算法效率。