木構造とヒトの家系図って逆で、100万の祖先の先に俺たちは立っている

木構造、特に完全二分木は各ノードに子ノードが２個ずつあるけど、ヒトの家系図は必ず一人の子に対して親が二人いるので逆だなって思った話です。

木構造

木構造（きこうぞう）とは、グラフ理論の木の構造をしたデータ構造のこと。階層的な構造を表すのに適したデータ構造。フォルダ構成や組織図などの階層構造を抽象化することができる。深さ優先探索や幅優先探索などを行う時のデータ構造でもあり、プログラミングには欠かせない概念である。

逆やん！

、、、というのは一度置いておいて。ノード間の関係は家系図に見立てた用語で表現されます。親ノード、子ノード、兄弟ノードなど言ったりします。確かにこのメタファーは理解しやすいし、このように呼称することに異論はありません。ところで、ふと実際の家系図はどのような形をしているかと考えたところ逆やん！と思い、ご先祖様ってめちゃくちゃな人数いるやん、怖っ！2^Nで増えてくよ、ということに気づきました。で、せっかくなので、血縁のご先祖様はどのくらいいるか数えてみました。

100万（1,000,000）の祖先にたどり着くのは何世代前？

世代	人数
1(親)	2
2(祖父母)	4
3	8
N	2^N

3世代前まで辿るだけですでに合計で14人（2+4+8）の先祖がいます。

さて100万にたどり着くのは何世代前か、プログラミングしてみました。

fn main() {
    let mut sum = 0;
    let mut generation = 1;
    while sum < 1_000_000 {
        sum += 2u64.pow(generation);
        generation += 1;
    }
    println!("sum:{} generatio:{}",sum,generation);
}
=> sum:1048574 generatio:20

はい出ました、20世代です。長く見積もって1世代40歳とすると800年前くらい前までたどれば余裕で「100万の祖先の先に俺たちは立てます」昔は今より低年齢で出産していたはずなので、厳密にはもうちょい手前だとは思います。

せっかくなので西暦0年まで辿るとどのくらいの人数になるか見てみましょう。40年を1世代とするので、2000年遡ると50世代遡ることになります。

fn main() {
    let mut sum = 0;
    let mut generation = 1;
    while generation < 50 {
        sum += 2u64.pow(generation);
        generation += 1;
    }
    println!("sum:{} generatio:{}",sum,generation);
}
=> sum:1125899906842622 generatio:50

はい出ました、約1千兆人です。だいぶ怖いですね。
大きい数字でかつ間違いなくヒトは生きてきたので、ちょっと想像するだけでだいぶ恐怖を感じます。ちなみにホモサピエンスの誕生まで遡ると20万年前まで到達します。さらに人類（ヒト属）まで遡ると。。。これくらいにしておきます。

1000000-lives.com