設計

フィールド

• キー，値
• 親ノードへのポインタ
• 子ノードへのポインタ（左，右）

ポインタは基本的にOption<Rc<RefCell<Node>>>で持たせたいが，ダングリングポインタが発生してしまうことがあるので，親ノードへのポインタはRcではなくWeakでもっておく．

https://doc.rust-jp.rs/book-ja/ch15-06-reference-cycles.html

struct Node<K, V> {
    key: K,
    value: V,
    parent: Option<Weak<RefCell<Node<K, V>>>>,
    left: Option<Rc<RefCell<Node<K, V>>>>,
    right: Option<Rc<RefCell<Node<K, V>>>>,
}

/// 子方向のポインタ
pub type NodePtr<K, V> = Rc<RefCell<Node<K, V>>>;

/// 親方向のポインタ
pub type ParentPtr<K, V> = Weak<RefCell<Node<K, V>>>;

とエイリアスをかけておくと，

struct Node<K, V> {
    key: K,
    value: V,
    parent: Option<ParentPtr<K, V>>,
    left: Option<NodePtr<K, V>>,
    right: Option<NodePtr<K, V>>,
}

とシンプルに書くことができて便利．

Splayの実装

ボトムアップでスプレーを実装する（対象となるノードを回転で根に上げていく）

状態の取得

ポインタが，「根」「右の子」「左の子」のどれに該当するのかを判定します．
これを実装しておくと，後の回転，スプレーの実装がだいぶ楽になる．

https://github.com/kentakom1213/rust-data-structures/blob/a0d3096c69205511d209c5de24148909a202ceb7/splay_tree/src/node/state.rs#L4-L12

回転

与えられたノードが親となるように回転を行う．（頑張ってポインタをこねこねする）

スプレー

回転を準備したので，スプレーは比較的かんたん！
対称な処理はまとめられます．

https://github.com/kentakom1213/rust-data-structures/blob/a0d3096c69205511d209c5de24148909a202ceb7/splay_tree/src/node/splay.rs#L94-L128

挿入

値の挿入をします．splitベースの実装もありますが，一般的な「2分探索→葉に挿入」という実装にしました．挿入に関してはこちらでも比較的シンプルに実装できます（削除は大変）

https://github.com/kentakom1213/rust-data-structures/blob/a0d3096c69205511d209c5de24148909a202ceb7/splay_tree/src/node/insert.rs#L18-L57

検索

値の検索だけでなく，lower_bound (x以上の最大の値を検索) 等のクエリにも対応したいので，工夫した2分探索で実装します．

比較関数fを渡し，fを満たす最小のノードを返す実装にすることでシンプルに実装しました．

https://github.com/kentakom1213/rust-data-structures/blob/a0d3096c69205511d209c5de24148909a202ceb7/splay_tree/src/node/find.rs#L12-L45

削除

一般に，平衡2分木の削除は実装が煩雑になりがちですが，スプレー木は「検索した値が根に来る」という性質から比較的シンプルに実装できます．

具体的には，スプレー木 T から値 x を削除する場合，

1. 値 x をもつノード検索し，根に移動させる
2. T を x 未満の値のみからなる木 T_\mathrm{left} と x より大きい値のみからなる木 T_\mathrm{right} に分割する．
3. T_\mathrm{left} と T_\mathrm{right} をマージする

というふうにすれば良いです．

https://github.com/kentakom1213/rust-data-structures/blob/a0d3096c69205511d209c5de24148909a202ceb7/splay_tree/src/node/remove.rs#L16-L42

実行例

こんな感じに動きます．

（可視化は以下のコードで行っています）

https://github.com/kentakom1213/rust-data-structures/blob/a0d3096c69205511d209c5de24148909a202ceb7/splay_tree/src/print_util.rs#L23-L57

コード全体はこんな感じです．

https://github.com/kentakom1213/rust-data-structures/tree/main/splay_tree