木の高さと節点数の関係とは？
木の高さと節点数の関係とは、根の高さを0と数えると、高さhの二分木が持てる節点数は最大で2の(h+1)乗マイナス1個になる。逆にn個の節点を持つ木の高さは、最も詰まった形でおよそ log₂n、一直線なら n−1 になる。
きのたかさとせってんすうのかんけい
木の高さと節点数の関係の意味
根の高さを0と数えると、高さhの二分木が持てる節点数は最大で2の(h+1)乗マイナス1個になる。逆にn個の節点を持つ木の高さは、最も詰まった形でおよそ log₂n、一直線なら n−1 になる。
木の高さと節点数の関係の具体例
1000件を偏りのない二分探索木に入れると高さは約10で、探索は最大でも10回程度の比較で終わる。一方、昇順に並んだデータをそのまま挿入すると一直線になり、1000回近い比較が必要になる。
木の高さと節点数の関係は試験でどう引っ掛けられる？
「二分探索木の探索はO(log n)」は木が偏っていないことが前提。偏れば O(n) まで悪化するので、平衡化の仕組みがあるかを確かめずに計算量を答えると誤りになる。
木の高さと節点数の関係と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。