У нас есть следующий алгоритм, который позволяет нам генерировать двоичное дерево.
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), которую мы предоставляем каждый раз, когда текущий root и ключ, который мы хотим вставить.
Я хочу доказать или найти контрпример к следующему утверждению: если мы намеренно вставим ключ таким образом, что он нарушает свойство двоичного дерева (left_child < = parent <= right_child), но после этого продолжайте вставлять совместимые ключи, единственным неуместным узлом будет тот, который мы намеренно потеряли. Это также подразумевает, что у узла-нарушителя будет только один дочерний элемент. </p>
Для иллюстрации я создал эту схему (красный узел должен содержать 20, а не 10):
Как вы заметили, красный ключ (это 20, а не 10) - это наше нарушение, а ключи, которые идут после него, являются правильными. В этом примере мы видим, что единственным нарушающим ключом является красный. Это не влияет на ключи, которые идут после него.
Это только один пример. Я еще не нашел контрпример. Я хочу знать, как я могу вообще доказать это, не полагаясь в своем доказательстве на конкретные c примеры.