具有一个键违规但不影响输入的其余键的二叉树

Question

我们有以下算法可以生成二叉树。

root <- INSERT(x, v) // x is the root and v is the key we want to insert in the tree.

//The definition of the algorithm
INSERT(x, v):
   if x is an external node: 
       y <- new node with key v
       return y

   if v < x.key:
      x.left <- INSERT(x.left, v)
   else:
      x.right <- INSERT(x.right, v)

return x

树是由我们每次提供当前根和我们要插入的键的一系列 INSERT(root, v) 构建的。

我想证明或找到以下断言的反例：如果我们故意以违反二叉树原则（left_child <= parent <= right_child）的方式插入一个键，但之后继续插入兼容的键，那么唯一放错位置的节点就是我们故意错位。这也意味着违规节点将只有一个子节点。

为了说明我做了这个模式（红色节点应该包含 20 而不是 10）：

正如您所注意到的，红色键（是 20 而不是 10）是我们的违规行为，紧随其后的键是正确的键。我们可以在该示例中看到，唯一违反的键是红色键。它不会影响后面的键。

这只是一个例子。我还没有找到反例。我想知道如何在不依赖具体示例的证明的情况下一般性地证明这一点。

Answer 1

肯定不可能通过搜索找到违规节点。但是没有办法只用一个违规节点来阻止其他插入的合规性。想到二叉树的属性就变成了apparent，违规节点只能有一个child(child-tree):

      X
     /
    X+
   /
  Ys

违规的child是X+。它大于 X。它位于 X 的左侧，违反了二叉树的原则。将放置在 X 左侧的任何后续节点插入 (Ys) 必须小于 X，因此也小于 X+。因此所有这些节点只能放在 as/along X+ 的左边 child。将 X- 放置在 X.

右侧的推理类似

在您的示例中，看到它只是稍微有点棘手，因为违规节点不会立即违反它 parent:

       X
      /
     Z
    / \
  Z-s  X+
      /
    Z+s

但是证明X+永远只能有一个child-tree的逻辑是一样的。没有大于 X 的新节点将被插入 X 的左侧 child-tree（Z 的 child 树），因此要插入 Z 的 child-tree 中的每个节点（Z- 或 Z+）都将小于 X，因此也小于 X+.

具有一个键违规但不影响输入的其余键的二叉树

Binary Tree with one key violation that doesn't impact the rest of the keys entered

algorithm

binary-tree

proof

binary-search-tree