7.6   まとめ

1.   重要なポイント

• 二分木は非線形データ構造で、「一つを二つに分ける」分割統治のロジックを反映しています。各二分木ノードには値と2つのポインタが含まれ、それぞれ左と右の子ノードを指します。
• 二分木のノードについて、その左（右）子ノードとその下に形成される木は、まとめてそのノードの左（右）部分木と呼ばれます。
• 二分木に関連する用語には、根ノード、葉ノード、レベル、次数、エッジ、高さ、深さがあります。
• 二分木の初期化、ノードの挿入、ノードの削除の操作は、連結リストの操作と似ています。
• 一般的な二分木の種類には、完全二分木、完備二分木、満二分木、平衡二分木があります。完全二分木は理想的な状態を表し、連結リストは退化後の最悪の状態です。
• 二分木は、ノード値と空きスロットをレベル順走査シーケンスで配置し、親ノードと子ノード間のインデックスマッピング関係に基づいてポインタを実装することで、配列を使用して表現できます。
• 二分木のレベル順走査は幅優先探索手法で、「円を拡大しながら」の層ごとの走査方式を反映しています。通常はキューを使用して実装されます。
• 前順、中順、後順走査はすべて深度優先探索手法で、「まず最後まで行き、その後バックトラックして続行する」走査方式を反映しています。通常は再帰を使用して実装されます。
• 二分探索木は要素検索のための効率的なデータ構造で、検索、挿入、削除操作の時間計算量はすべて\(O(\log n)\)です。二分探索木が連結リストに退化すると、これらの時間計算量は\(O(n)\)に悪化します。
• AVL木は平衡二分探索木とも呼ばれ、回転操作を通して継続的なノード挿入と削除後も木が平衡を保つことを保証します。
• AVL木の回転操作には、右回転、左回転、右左回転、左右回転があります。ノードの挿入または削除後、AVL木はボトムアップ方式でこれらの回転を実行して自己平衡を取ります。

2.   Q & A

Q: 一つのノードのみを持つ二分木について、木の高さと根ノードの深さの両方が\(0\)ですか？

はい、高さと深さは通常「通過したエッジの数」として定義されるためです。

Q: 二分木における挿入と削除は一般的に一連の操作によって達成されます。ここでの「一連の操作」とは何を指しますか？子ノードのリソースを解放することを意味しますか？

二分探索木を例に取ると、ノードを削除する操作は3つの異なるシナリオで処理する必要があり、それぞれ複数ステップのノード操作が必要です。

Q: 二分木のDFS走査で前順、中順、後順の3つのシーケンスがあるのはなぜですか？その用途は何ですか？

配列の順次および逆順走査と同様に、前順、中順、後順走査は二分木を走査する3つの方法であり、特定の順序で走査結果を取得できます。例えば、二分探索木では、ノードサイズが「左子ノード値 < 根ノード値 < 右子ノード値」を満たすため、「左 \(\rightarrow\) 根 \(\rightarrow\) 右」の優先順位で木を走査することで、順序付けられたノードシーケンスを取得できます。

Q: 不平衡ノードnode、child、grand_child間の関係を処理する右回転操作において、右回転後にnodeとその親ノード間の接続とnodeの元のリンクが失われるのではありませんか？

この問題を再帰的な観点から見る必要があります。right_rotate(root)操作は部分木の根ノードを渡し、最終的にreturn childで回転された部分木の根ノードを返します。部分木の根ノードとその親ノード間の接続は、この関数が戻った後に確立され、これは右回転操作の保守範囲外です。

Q: C++では、関数はprivateとpublicセクションに分かれています。これにはどのような考慮事項がありますか？なぜheight()関数とupdateHeight()関数がそれぞれpublicとprivateに配置されているのですか？

これはメソッドの使用範囲によります。メソッドがクラス内でのみ使用される場合、privateに設計されます。例えば、ユーザーが独自にupdateHeight()を呼び出すことは意味がありません。これは挿入または削除操作の一ステップに過ぎないからです。しかし、height()はノードの高さにアクセスするためのもので、vector.size()と同様であるため、使用のためにpublicに設定されています。

Q: 入力データのセットから二分探索木をどのように構築しますか？根ノードの選択は非常に重要ですか？

はい、木を構築する方法は二分探索木コードのbuild_tree()メソッドで提供されています。根ノードの選択については、通常入力データをソートし、中央の要素を根ノードとして選択し、再帰的に左と右の部分木を構築します。このアプローチは木の平衡を最大化します。

Q: Javaでは、文字列比較に常にequals()メソッドを使用する必要がありますか？

Javaでは、プリミティブデータ型の場合、==は2つの変数の値が等しいかどうかを比較するために使用されます。参照型の場合、2つのシンボルの動作原理は異なります。

• ==: 2つの変数が同じオブジェクトを指しているかどうか、つまりメモリ内の位置が同じかどうかを比較するために使用されます。
• equals(): 2つのオブジェクトの値が等しいかどうかを比較するために使用されます。

したがって、値を比較するにはequals()を使用すべきです。ただし、String a = "hi"; String b = "hi";で初期化された文字列は文字列定数プールに格納され、同じオブジェクトを指すため、a == bも2つの文字列の内容を比較するために使用できます。

Q: 最下位レベルに到達する前に、幅優先走査でキュー内のノード数は\(2^h\)ですか？

はい、例えば高さ\(h = 2\)の満二分木は合計\(n = 7\)個のノードを持ち、最下位レベルには\(4 = 2^h = (n + 1) / 2\)個のノードがあります。