2019/08/28 もくもく会 #181

[maraigue]

引き続き、「要素取得も挿入・削除も対数時間でできるリスト構造」を実装する。 必要なメソッドを順次作っていく。前回でinsertメソッドがちゃんとできたので、他のメソッドもテストしやすくなっているはず…

[ignisan]

前回、実装に詰まり気味だったので参考になりそうな配列操作ライブラリを探す

[maraigue]

eraseを実装していた（未完成）。 STLのeraseだと「削除した要素の次の要素にあたるイテレータを返す」という処理があるが、現状のリストの実装では単にイテレータを指定して削除するところしかしておらず、戻り値に対応したかった。 それをちゃんと実装しようとすると現状の実装では面倒だということに気づき、設計を見直していた。

[maraigue]

メモ

二分探索木の頂点を与え、それを削除する。ただし平衡を保つ処理をしやすくするため、左右の子をともに持つ頂点は木から直接取り除けず、もし存在するならば一つ前か一つ後ろの要素を表す頂点（これが左右の子をともに持つことはありえない）と値を交換してから削除しないとならない。

考えられる状況

• 1 削除したい頂点が最終要素である、2 削除したい頂点が最終要素ではない
• A 削除したい頂点を直接木から取り除ける（左右の子が高々一方のみ存在）、B 直接木から取り除けない（左右の子がともに存在）

処理の場合分け

• 1+A: 当該頂点をそのまま削除すればよい。戻り値はend()。
• 1+B: この場合にはなりえない。
• 2+A: 当該頂点をそのまま削除すればよい。戻り値は一つ先の頂点。
• 2+B: 当該頂点の一つ後の要素を表す頂点との間で値のみ交換してから、交換先を削除する。戻り値は当初削除しようとしていた（ただし値は交換済みの）頂点。

実際の処理

• 削除しようとしている頂点を n とする。
• n == end() - 1 なら、
  • n を削除する
  • return end()
• n != end() - 1 なら、
  • n の一つ先の要素を表す頂点を取得する。 o とする。
  • もし n に左の子と右の子の両方が存在するなら、
  • n と o で値のみ交換する。
  • o を削除する。
  • return n
  • もし n に左の子と右の子の両方は存在しないなら、
  • n を削除する
  • return o

補足

• 一つ前や一つ後の要素を表す頂点を取得するのは O(log N) 時間がかかるので極力避けたい。
• ただし、end() - 1（back()に相当する頂点）はすぐ取得できるので問題ない。