Is this true? if so why?

Revision en3, by Misa-Misa, 2023-10-23 04:41:23

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Misa-Misa 2023-10-23 04:41:23 0 (published)
en2 English Misa-Misa 2023-10-23 04:40:58 87
en1 English Misa-Misa 2023-10-23 04:38:46 366 Initial revision (saved to drafts)