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

user_12247844 0
Viewed 41

We have the following algorithm that allows us to generate a binary tree.

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

The tree is built by a sequence of INSERT(root, v) we provide each time the current root and the key we want to insert.

I want to prove or find a counter-example to the following affirmation: If we purposefully insert a key in such a way that it violates the binary tree propriety (left_child <= parent <= right_child) but continue inserting compliant keys afterwards, the only misplaced node will be that one we purposefully misplaced. This also implies that the violating node will only have one child.

To illustrate I made this schema (the red node should contain 20 and not 10):

example of binary tree with violation

As you notice the red key (is 20 not 10) is our violation and the keys that comes after it are correct keys. We can see in that example that the only key in violation is the red one. It does not impact the keys that comes after it.

This is just one example. I haven't found a counter-example yet. I want to know how can I generally prove this without having to rely in my proof on specific examples.

binary-search-tree proof binary-tree algorithm
1 Answers

Surely it will be impossible to find the violating node from a search. But there's noway with just one violating node, to hinder the compliance of additional insertions. When you think of the property of the binary tree it becomes apparent that the violating node can only have one child (child-tree):

      X
     /
    X+
   /
  Ys

The violating child is X+. It's greater than X. It's placed to the left of X, violating the binary tree propriety. Any subsequent insertions of nodes (Ys) that will be placed to the left of X must be less than X, hence also less than X+. Therefore all those nodes can only be placed as/along the left child of X+. The reasoning is similar for placement of a X- to the right of X.

In your example it's only slightly more tricky to see, because the violating node doesn't violate it's immediate parent:

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

But the logic to prove that X+ can ever only have one child-tree is the same. There is no new node, that is greater than X, that will be inserted into the left child-tree of X (the child tree of Z), so every node to be inserted into the child-tree of Z (either Z- or Z+), will be less than X and hence also less than X+.

user_126950270
Related