平衡二分探索木とは

募: タイトル

文章が怪しいので書き直してほしいです

平衡二分探索木とは, 二分探索木の高さを低く保つことで, 各操作の計算量を抑えるデータ構造

平衡二分探索木が扱うことのできるデータは, 大きく分けて2種類

マップ (連想配列, 正確にはordered map)

keyに対応した値を保持する

keyは比較できる必要があり, 平衡二分探索木には, keyの順序でそのkeyに対応した値が保持される

ここに画像がほしい

列系(いい名前募集)

配列を保持する

平衡二分探索木には, 配列のインデックスの順序で配列の値が保持される

ここに画像がほしい

葉木と葉木でないやつがある

split merge を書く

マップのできる操作

(key, value) を指定して要素を挿入する

key を指定して要素を削除する

key を指定して要素を検索する

列系のできる操作

(index, value) を指定して要素を挿入する

index を指定して要素を削除する

index を指定して要素を検索する