私は、バイナリ検索ツリーについて勉強するときに出てきた2つの質問について疑問に思っています。平衡二分木の最下位にあるノードの数
nノードを持つ平衡バイナリ検索ツリーの最下位レベルにあるノードの最大数はいくらですか？
ノードがn個あるバランス型バイナリ検索ツリーの最下位レベルにあるノードの最小数はいくらですか？
私の教科書にはこれに関する何らかの公式はありません。これらの質問に答えられる方法はありますか？私にお知らせください。 （あなたは、頂点がレベル0であると仮定した場合）
フルバイナリツリーとすると、リーフ内のノード数は常に(n/2)+1に等しくなります。
ノードの最小数の場合、ノードの総数は、1（バランスの取れたツリーでなければならないという条件を満たす）になる可能性があります。
彼は完全なバイナリツリーのノード数を求めていません。彼はこれがnノードのBSTであることを明確に述べました。 –
私はリーフレベルのノードの数は（n/2）+1 – attaboy182
私の間違いだと言いました。しかし、依然としてこれは質問が完全に異なっているので質問に答えません。 –
バイナリツリーにおけるレベルLのノードの最大数は2^Lあります。これは、各レベルで前の各リーフから2人の子供をスポーンするので、見やすいです。平衡/探索木であるということは無関係です。だから2^L < nのような最大のLを見つけてnから引く必要があります。これは数学の言語である：
ノードの最小数はあなたの木のバランスをとる方法に依存します。高さのバランスの取れた木、重さのバランスの取れた木などがあります。バランスのとれた樹木でも、バランスの取れた木が何を意味するかを定義することができます。技術的には、N + 2の高さを持つ2^Nノードのツリーは、依然としてバランスの取れたツリーです。
私は教授から答えを得ました。最後のレベルのノードの
1）最大数：⌈n/2⌉
7つのノードと平衡二分探索木がある場合、答えは⌈7/なり2⌉ = 4、15ノードのツリーの場合は、⌈15/ 2 = = 8となります。 しかし、バランスのとれたツリーの最後のレベルがの場合にのみ、この式が正解を返すということは問題ありません。左から右に塗りつぶされています。 たとえば、5つのノードを持つ平衡バイナリ検索ツリーの場合、上記の式は3の答えを示します。これは、5つのノードを持つツリーが最後のレベルで4ノードの最大ノードを含むことができるためです。 私は彼が完全なバランスのとれたバイナリ検索ツリーを意味していると推測しています。最後のレベルのノードの
2）最小数：バイナリツリーが持っているどのような属性の
と思います。各ノードは最大2つのリーフ/サブツリーを有する。 2つのノードがある場合、いくつのノードが最下位レベルにありますか？あなたは3または4を持っている場合？nとnに依存するツリーの高さに依存して数式を作成してみてください。 – flashingx
これは、私たちがどのようにバランスを取っているのか、どのようなバランスがあるのかによって多少異なります。 – user2357112
あなたは本の中の数式を見つけられませんでしたが、どこで問題を自分自身で考えていましたか？小さなバランスのとれた木を描いて、底のノードを数えましたか？完全なバランスの取れた木々を見ることは良いスタートになるでしょう。 –