二叉查找树

1 定义

1. Tree 是一个二叉树(Binary Tree)
2. 对于任何一个节点，它左子树里所有节点的值都比它小，右子树里所有节点的值都比它大。

使用数学描述法如下:

TODO: binary search treee 生成小程序

2 性质

1. 基本性质: 对于任何一个节点，它左子树里所有节点的值都比它小，右子树里所有节点的值都比它大。

2. 基本性质

将任何一个点看作Root节点，则这个点的左子树也是 Binary Search Tree 将任何一个点看作Root节点，则这个点的右子树也是 Binary Search Tree 这说明递归定义,局部与整体相似

Binary Search Tree中的最小节点，一定是整棵树中最左下的叶子节点(从Root开始一直顺着左子树往下走，直到某一个点没有左子节点，则这个点就是最小的) Binary Search Tree中的最大节点，一定是整棵树中最右下的叶子节点(从Root开始一直顺着右子树往下走，直到某一个点没有右子节点，则这个点就是最大的)

如何判断两个节点是否是祖先后代关系？

祖先结点 p 与节点 a 之间的大小关系.

后继祖先:第一个比自己大的祖先

祖先 p 和 a 的关系：因为 p 是 a 的祖先且 p > a，那么 a 必然位于 p 的左子树中。这是二叉查找树的基本性质。: 反证法

3 操作

• build 构造
• 遍历
• 最值:数学归纳法
• find
• 排名 rank
• 排名为空的元素 kth
• 前驱/后继

在这种情况下，我们需要从节点 a 开始向上回溯，直到找到一个节点 p，并且 a 位于 p 的左子树中。那么这个节点 p 就是 a 的后继。

查找所有的比节点 a 大的节点 你的总结完全正确，而且非常到位！

你准确地抓住了这个算法的精髓：它是一个 递归 过程，通过比较节点值来不断 缩小问题规模（这个操作在算法里常被称为“剪枝”），从而避免了无效的搜索。

为了把它变成可以写成代码的清晰步骤，我们可以这样描述这个递归函数，我们叫它 findLarger(node, a):

1. 基本情况（递归出口）: 如果当前 node 为空，说明这条路已经走到头了，直接返回。

2. 比较和决策:

   • 如果 node.value > a:
     • 将 node 的值加入结果列表。
     • 将 node 右子树的 所有节点 加入结果列表（因为它们都比 node 大，所以肯定也比 a 大）。
     • 继续向左递归，调用 findLarger(node.left, a)，因为左边可能还有比 a 大的节点。
   • 如果 node.value <= a:
     • 忽略当前节点和整个左子树。
     • 继续向右递归，调用 findLarger(node.right, a)，在右子树里继续寻找。

这个算法流程是不是和你刚才总结的思路完全一样？

要不要我们用一个具体的二叉搜索树例子，一步一步走一遍这个流程，看看它是如何工作的？

4 重要操作

• 插入
• 删除