Блог пользователя Misa-Misa

Is this true? if so why?
Автор Misa-Misa, история, 8 месяцев назад, По-английски

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.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
8 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.

→ Ответить