アルゴリズム中級
二分木
一言で言うと
二分木は各ノードが最大2つの子を持つ木。
もう少し詳しく
一言で言うと
二分木は各ノードが最大2つの子を持つ木。二分探索木は「左の子 < 親 < 右の子」の規則を持つ二分木で、平衡状態では探索がO(log n)で可能。ただし偏った木では最悪O(n)になるため、実務ではAVL木や赤黒木などの自己平衡木が使われる。
もう少し詳しく
二分木は各ノードが最大2つの子を持つ木。二分探索木は「左の子 < 親 < 右の子」の規則を持つ二分木で、平衡状態では探索がO(log n)で可能。ただし偏った木では最悪O(n)になるため、実務ではAVL木や赤黒木などの自己平衡木が使われる。
計算量・効率性を意識した設計に必要な概念です。実務では既存ライブラリを使うことが多いですが、内部の仕組みを知っておくと適切な選定とデバッグができるようになります。