Definition

操作

多くは Introduction to Algorithms, third edition に準じるが、独自定義もある。

• MINIMUM(S), MAXIMUM(S)
• SUCCESSOR(S, x), PREDECESSOR(S, x)
• INORDER-TREE-WALK(S)
  • 木の中間順巡回
  • ランク順に全列挙
• SEARCH(S, k)
• INSERT(S, x)
• DELETE(S, x)
  • 削除操作は「ノードの取得」と「既に取得されたノードの削除」のステップに分割されるが、ここでは後者
• SELECT(S, i)
  • ランクからノードを取得する
• RANK(S, x)
  • ノードからランクを取得する
• INSERT-BEFORE(S, x, y), INSERT-AFTER(S, x, y)
  • 指定されたノードの直前または直後のランクとなるように挿入する
• INSERT-BY-RANK(S, i, x)
  • 指定されたランクとなるように挿入する
• RANK-BY-KEY(S, k)
  • キーからランクを取得する

二分木

二分木のノードの個数を n、高さを h とする。
二分木には、次の 3 つのオプションを付加できる。

• サイズ付き (sized)
  • 各ノードがサイズを保持している
    • 各ノードに対して、サイズを O(1) 時間で取得できる
  • ランク (インデックス) による探索が O(h) 時間でできる
• ソート済み (sorted)
  • ある全順序関係により、キーがソートされた状態に保たれる
    • キーの順序によりランクが定まる
  • キーによる探索が O(h) 時間でできる
• 自己平衡機構を持つ (self-balancing)
  • 高さがつねに O(log n) に保たれる
  • 具体的な実現方法については言及しない
  • 木の形状のみに依存するのであれば、挿入および削除の処理とは独立に考えることができる
    • ノードの挿入または削除のあとに自己平衡