Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
maraigue opened this issue Aug 28, 2019 · 4 comments

Comments

@maraigue
Copy link
Contributor

commented Aug 28, 2019

No description provided.

@maraigue

This comment has been minimized.

Copy link
Contributor Author

commented Aug 28, 2019

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

@ignisan

This comment has been minimized.

Copy link
Contributor

commented Aug 28, 2019

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

@maraigue

This comment has been minimized.

Copy link
Contributor Author

commented Aug 28, 2019

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

@maraigue

This comment has been minimized.

Copy link
Contributor Author

commented Aug 28, 2019

メモ

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

考えられる状況

  • 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 に左の子と右の子の両方が存在するなら、
      • no で値のみ交換する。
      • o を削除する。
      • return n
    • もし n に左の子と右の子の両方は存在しないなら、
      • n を削除する
      • return o

補足

  • 一つ前や一つ後の要素を表す頂点を取得するのは O(log N) 時間がかかるので極力避けたい。
  • ただし、end() - 1back()に相当する頂点)はすぐ取得できるので問題ない。
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
2 participants
You can’t perform that action at this time.