为什么二叉搜索树的中序遍历保证非降序？

Question

TL;DR 我的最终问题是在适当的二叉树上找到两个节点（即它本身至少有两个节点），一个仅大于输入，另一个仅小于输入。（线下续）

为了实现这一点，我个人断言从字面上看，如果你画一棵树（体面地），你在水平方向上看到右边的那棵肯定比上面的任何一棵都大它的左边。

换句话说，引用自维基百科（二叉搜索树）：

The key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in the right sub-tree.

而且好像只能保证在当地是真的。像这样的图：

          A
       /    \
      B      C
    /   \  /   \
   D     E F    G
 /   \
H     I

(字母无先后顺序，即只为结构)

局部我的意思是当我们谈论节点E时，它保证D（带有F和G）小于E，但是C，F，G与E相比，是否也有保证？

这似乎很直观（F、C、G都大于E），但我没有找到证明这一点的方法，那么有什么反例或理论证明吗？任何现有的定理或建议？

编辑：我终于发现这等同于为什么二叉搜索树的中序遍历具有非递减顺序。

Answer 1

This seems quite intuitive (that F,C,G are all greater than E), but I don't find anyway to prove that, so is there any counterexample or theoretical proof? Any existed theorems or suggestions?

F > A — BST 的定义 ("key in each node must be … smaller than all keys in the right sub-tree")
E < A — BST 的定义 ("key in each node must be greater than all keys stored in the left sub-tree")
E < A < F — 传递性

C 和 G 依此类推

Answer 2

您需要区分 "binary tree" 和 "binary search tree" 才能准确区分。

一个二叉搜索树有你要找的属性；左分支中的所有节点都小于右分支中的所有节点。如果不是这样，你就不能使用通常关联的搜索方法——即查看一个节点，如果你正在寻找一个较小的节点，则向左走，如果你正在寻找一个较大的节点节点，向右走。我认为基本的 BST，加上像 AVL 和 red-black 这样的平衡树，都观察到相同的属性.

还有其他不是 "Binary Search Trees" 的二叉树数据结构——例如，min-heap 和 max-heap 都是二叉树，但是 'left is smaller than right'通过树的所有方式都没有满足约束。堆用于查找集合中的最小或最大元素，因此您通常只推理树顶部的节点。

至于证明，我想是有这个；如果您接受搜索算法有效，那么我们可以证明这个属性必须成立。例如，在这棵树中；

      a
     / \
    b   n
   / \
  c   d

那么假设您想证明 d 小于 n 或任何 child。假设您正在搜索 d，而您在 a。显然，您将 a 与 d 进行比较，发现 d 更小——这就是您知道向左遍历到 b 的方式。所以就在那里，我们必须相信整个左树（b 及以下）都必须小于 a。右侧和大于 a 的数字的参数相同。

所以left-children(a) < a < right-children(a)

糟透了pseudo-proof...

Answer 3

想象一下，你有没有 E 的同一棵树：

         A
       /   \
      B     C
    /     /   \
   D     F     G
 /   \
H     I

现在你插入这个大于B的E。如果E也大于A怎么办？在这种情况下，它将被插入到 A 的右子树中，好吗？但是当E在B的右子树中时，它小于A:

         A
       /   \
      B     C
     / \   / \
    D   E F   G
   / \
  H   I

为什么二叉搜索树的中序遍历保证非降序？

Why inorder traversal of binary search tree guarantee to have non-decreasing order?

algorithm

binary-search-tree