メモ

次のデータ構造が欲しい。

データ構造Ｔ

  • 全順序関係があるデータを格納
  • 挿入 O(log n)
  • 削除 O(log n)
  • 検索 O(log n)
  • 次要素（順序関係において) O(log n)
  • 前要素（順序関係において）O(log n)
  • 順序関係の交換 O(log n)

データ構造H

  • 全順序関係があるデータを格納
  • 挿入 O(log n)
  • 削除 O(log n)
  • 最小値検索 O(log n)

Tはたぶん平衡木だが、順序関係の交換と次、前要素を備えたライブラリが見つからないなー。

自分で書くのもバグがたくさんでてきそうだし。

[追記]

HaskellにもAVL木があった

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/AvlTree

ありがたく利用させていただく。