N分ヒープの要素Xの左の子がN(X-1)+2になる

N分ヒープを1から始まる配列の番号にわりあてたとき、

番号x　の左の子は番号　N(x-1)+2

ってのを示すメモ

根から深度を1,2,...ｄて数えるとする

深度dの右端の番号は,深度dには N^(d-1)個の要素があるので、等比の和で　
R(d) = (N^d-1)/(N-1)

深度dの左端の番号は,深度d-1の右端の番号+1 なので
L(d) = R(d-1)+1
= (N^(d-1)-1)/(N-1) + 1

要素xが深度dにあるとする

要素xの左にある深度dのノードは、x - L(d)　個　ある

要素xのもつ一番左の子の左側には,深度d+1のノードが N*(x - L(d)) 個　ある　（N分だから。）

よってxのもつ一番左の子の番号は
(深度d+1の一番左端の要素の番号) + (xのもつ一番左の子の左側にあるノードの数)

ℓ(x) = L(d+1) + N*(x-L(d))

= (N^d - 1)/(N-1) +1 + Nx - N(N^(d-1)-1)/(N-1) - N

= N(x-1)+2

余談: 番号ｘのある深度の求め方
xの深度がdにあるとする

${ R(d-1) < x <= R(d) }$

R(d),L(d)　は上の方で書いたのとおなじ

(N^(d-1)-1)/(N-1) < x <= (N^d-1)/(N-1)
N^(d-1) < x(N-1) + 1 <= N^d (↑の全辺にN-1をかけてから１をたす)
1/N < (x(N-1)+1)/N^d <= 1 (↑の全辺をN^dでわる)
(x(N-1)+1) <= N^d < N(x(N-1)+1) (↑の全辺の逆数を取ったあと(x(N-1)+1)をかける)

ここで、全辺の ${log_{N}}$ をとる