7.6 まとめ¶
1. 要点の振り返り¶
- 二分木は非線形データ構造の一種であり、「二分する」分割統治の考え方を体現している。各二分木ノードは 1 つの値と 2 本のポインタを持ち、それぞれ左子ノードと右子ノードを指す。
- 二分木のあるノードについて、その左（右）子ノードおよびその配下から構成される木を、そのノードの左（右）部分木と呼ぶ。
- 二分木に関する用語には、根ノード、葉ノード、レベル、次数、辺、高さ、深さなどがある。
- 二分木の初期化、ノードの挿入、ノードの削除は、連結リストの操作方法と似ている。
- 一般的な二分木の種類には、perfect 二分木、complete 二分木、full 二分木、平衡二分木がある。perfect 二分木が最も理想的な状態であり、連結リストは退化後の最悪の状態である。
- 二分木は配列で表現できる。方法としては、ノード値と空き位置をレベル順走査の順に並べ、親ノードと子ノードのインデックス対応関係に基づいてポインタを実現する。
- 二分木のレベル順走査は幅優先探索の一種であり、「同心円状に外へ広がる」ような逐次的な走査方式を表しており、通常はキューによって実装される。
- 前順、中順、後順走査はいずれも深さ優先探索に属し、「まず末端まで進み、その後バックトラックして続ける」という走査方式を体現しており、通常は再帰で実装される。
- 二分探索木は効率的な要素探索データ構造であり、探索、挿入、削除の時間計算量はいずれも \(O(\log n)\) である。二分探索木が連結リストへ退化すると、各操作の時間計算量は \(O(n)\) まで悪化する。
- AVL 木は平衡二分探索木とも呼ばれ、回転操作によって、ノードの挿入と削除を繰り返した後も木が平衡を保つようにしている。
- AVL 木の回転操作には、右回転、左回転、右回転してから左回転、左回転してから右回転がある。ノードの挿入または削除の後、AVL 木は下から上へ回転操作を行い、木を再び平衡状態に戻す。
2. Q & A¶
Q：ノードが 1 つしかない二分木では、木の高さと根ノードの深さはどちらも \(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() を単独で呼び出しても意味はなく、これは挿入や削除の途中の 1 ステップにすぎません。一方で 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\) です。