196の日記

セキュリティ系の勉強、その他開発メモとか雑談、忘れそうな計算式などを書き溜める場所になっています. githhubはUnity触っていた頃ものがメイン https://github.com/196kakinuma

二分木の関係性の覚え方

超適当自分流覚え方。(必ずしも正しくはない)


f:id:thinline196:20180202222456j:plain




高さ n -> 節の数 2^(n+1)-1

高さに対して倍々に増えて行くので指数関数のグラフを意識すると良い。最後のマイナス1は根の数が1つだけだからとなんとなく覚えておけばなんとかなる。
指数関数 - Wikipedia



節の数 n -> 高さ log(2) n

高さの逆。高さが増えて行くためには節の数は倍々に増えている必要があります。なので、増えていくnを抑えて高さを数えて行く必要があります。対数関数のグラフを思い浮かべましょう。
対数 - Wikipedia


節の数 n -> 枝の数 n-1

節ごとがそれぞれ親に繋がる枝を持っているので、節の数と基本的には同じになるが、根のみ親を持たないためマイナス1をしてます。