【rust】AVL木の変形バージョンを実装してみた（avltriee）

rustでAVL木（の独自カスタマイズ版）のクレートを作り、公開してみました。
https://crates.io/crates/avltriee

通常のAVL木との違いが二つほどあります。

違い1: 同一の値の扱いについて

通常のAVL木の場合、同一の値があった場合、一定のルールに従って、右か左の枝に振り分けられます。
AVL木はそのような同一の値のデータが大量にあった場合に性能が低下するそうです。
例えば、人物図鑑的なデータベースで血液型というフィールドがあった場合、通常はA/B/AB/Oの4パターンのみになりますので、このような場合は同一の値が大量にできる事になります。

そのよう場合でも性能を劣化させないようにするため、avltrieeでは、同一の値があった場合に三つ目の枝に分岐するようにしてみました。

avl「triee」と、変なタイプミスっぽい名前になっているのは、tri(3)とtreeをかけた造語であるためです。

違い2: 行指向

AVL木の実装サンプルを見ると、木の操作時に値ごとノードを移動させる事が多いようです。

それに対し、avltrieeでは、行指向と表現するのが正しいかわかりませんが、データの挿入や変更は行番号を指定して行います。
ノードの左右（および同値の中央）の枝も行番号で示すので、回転操作ではノードそのものは移動させず、左右（および同値の中央）の枝を行番号で更新します。
つまり、値の位置はデータ追加後、永久に変わりません。
そのため、目的のデータの行番号を指定してアクセスする場合は、検索処理が不要で瞬時に値にアクセスできます。Vecや配列でインデックスを指定するのと同じです。

使い方

use avltriee::Avltriee;
use avltriee::AvltrieeNode;
use rand::distributions::{Distribution, Uniform};

let len = 10;
let mut list: Vec<AvltrieeNode<i64>> = (0..=len).map(|_| AvltrieeNode::new(0, 0, 0)).collect();
let mut t = Avltriee::new(list.as_mut_ptr());

let mut rng = rand::thread_rng();
let die = Uniform::from(0..=20);

futures::executor::block_on(async {
	for i in 1..=len {
		let num = die.sample(&mut rng);
		println!("update:{}", num);
		unsafe {
			t.update(i.try_into().unwrap(), num).await;
		}
	}
});

println!("iter_by(5)");
for i in t.iter_by(|v| v.cmp(&5)) {
	println!("{}:{}", i, unsafe { t.value_unchecked(i) });
}
println!("iter_range(3-5)");
for i in t.iter_range(|v| v.cmp(&3), |v| v.cmp(&5)) {
	println!("{}:{}", i, unsafe { t.value_unchecked(i) });
}

println!("iter_from(5)");
for i in t.iter_from(|v| v.cmp(&5)) {
	println!("{}:{}", i, unsafe { t.value_unchecked(i) });
}
println!("iter_to(5)");
for i in t.iter_to(|v| v.cmp(&5)) {
	println!("{}:{}", i, unsafe { t.value_unchecked(i) });
}

※初期化の際の<i64>は値の型を指定します。
ジェネリック型として定義しているので型は自由に指定できますが、メモリに直接データをコピーするという処理が入っているため、Copy traitを実装している型のみに限ります。

そのため、可変長なデータを扱うことができないのですが、それはそれで別途クレートを用意しているので、またの機会に紹介したいと思います。