Misa-Misa's blog

Is this true? if so why?
By Misa-Misa, history, 13 months ago, In English

we have a permutation p of size N.

we iterate on this permutation and insert elements into a Binary Search Tree.

Prove that each sub-tree will consists of all elements from some l to r.

In other words, prove that elements of each sub-tree form continuous subarray of identity permutation (if written is sorted order).

identity permutation -> 1, 2, 3, 4 ... N.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Misa-Misa (previous revision, new revision, compare).

→ Reply
»
13 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Proof by induction.

Base case: $$$n \le 1$$$. Trivial.

Induction: Let us assume that we inserted $$$k$$$ first from the permutation of length $$$n$$$. Then, all elements smaller than $$$k$$$ will be on the left subtree, and the rest are on the right subtree. Then the left subtree is a permutation of $$$[1,k-1]$$$, and the right subtree is a permutation of $$$[k+1,n]$$$. A permutation of $$$[1,k-1]$$$ is a permutation of length $$$k-1$$$, and a permutation of $$$[k+1,n]$$$ is similarly a permutation of length $$$n-k$$$. Thus the induction holds.

→ Reply