binary-tree - 左平衡二分木

Question

データ構造に関する本を読んでいますが、左バランス バイナリ ツリーは、葉が最後のレベルの左端の位置のみを占めるツリーであると書かれています。

これは私には少しあいまいに思えました。これは、葉が根の左側にのみ存在し、レベル全体に分布していることを意味しますか、それともツリー全体の左側にのみ葉が存在することを意味しますか。正確に何がバランスの取れたままになっているのですか？

私の推測が答えのいずれかをカバーしているかどうかはわかりません。そのため、誰かが助けてくれれば大歓迎です:-)。

Answer 1

左バランス二分木は、各ノードの左サブツリーが右サブツリーの前に埋められるバランス二分木と考えることができます。より非公式な言い方をすれば、これは最下位レベルのノードがすべてツリー全体の左側にあるツリーです。

たとえば、次のツリーを見てください。

このツリーはバランスが取れていますが、左バランスではありません。ただし、ノード 67 が削除された場合、ツリーは左バランスになります。

Answer 2

左バランス二分木の定義は、完全二分木の定義と同じように思えます。

Answer 3

答えはよくわかりませんが、本の説明からするとこんな感じです...

手始めに、このように考えてみましょう。ツリーのすべての「行」には、ゼロから始まりカウントアップする番号があります。番号が最も大きい行が最後のレベルと見なされます。

リーフノードは子のないノードであることを忘れないでください。したがって、ツリーは、次のように、最後のレベルのすべてのリーフノードが左側にある必要があるという条件を満たしています。

          50
       /     \
     /         \
    35         70
   /  \       /  \
 10    34    57  90
 /     /        /
9     7        78

90の右の子として「98」を追加した場合、または57の右の子として「59」を追加した場合、このツリーはもはや左バランスになりません。

---

編集：ブランドンEテイラーの答えを読んだ後、あなたは間違いなくこれを選ぶべきではありません。それを調べて説明をもう一度読んだ後、彼はより理にかなっているだけでなく、説明によりよく適合します。