Javaでスプレー木クラス作成

プログラミング

平衡二分木の一つスプレー木（スプレイ木、自己調整二分木(英:Splay Tree)）クラスを制作しました。

前回の
「Javaで二分探索木クラス作成」
http://d.hatena.ne.jp/g940425/20101211/1292088124
で制作したクラスBinarySearchTreeをベースに、スプレー操作と呼ばれる操作を付け加えました。

Wikipedia「スプレー木」
http://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%97%E3%83%AC%E3%83%BC%E6%9C%A8

つまり、木の回転によって二分探索木の条件を保ったまま、
アクセスしたノードを根の近くに移動させる(Move to Root)ことで、最近アクセスしたノードへの再アクセスを高速にします。しかもこの操作により木全体として自動的に大まかな平衡が取られるというものです。


スプレー操作が具体的にどんな変形操作なのかに関してはWikiを見てもらうとして、とりあえずデータ、コンストラクタ、スプレー操作、挿入、参照、削除のコードを晒します。
クラス名はSplayTree

データ及びコンストラクタは以下の通り。
ここでは変更なし。

public int key;
	public T value;
	public SplayTree<T> left;
	public SplayTree<T> right;
	public SplayTree<T> parent;
	
	//コンストラクタ：木を作成
	SplayTree(){
		this.value = null;
		this.key = 0;
		this.left = null;
		this.right = null;
		this.parent = null;
	}
	
	//コンストラクタ：ノードを作成
	SplayTree(int key,T value,SplayTree<T> p){
		this.value = value;
		this.key = key;
		this.left = null;
		this.right = null;
		this.parent = p;
	}
データ型 要素名 意味
int key キー値
T value データ
BinarySearchTree left 左の子（キー値小）
BinarySearchTree right 右の子（キー値大）
BinarySearchTree parent 親

ここまで全く変化なし。
次、肝心のスプレー操作。

//zig操作
	public void zig(){
		
		//キー・データのスワップ
		int temp_key = this.key;
		T temp_value = this.value;
		this.key = this.parent.key;
		this.value = this.parent.value;
		this.parent.key = temp_key;
		this.parent.value = temp_value;
		
		//回転
		if(this.parent.left == this){
			this.parent.left = this.left;
			if(this.left != null){
				this.left.parent = this.parent;
			}
			
			this.left = this.right;
			
			this.right = this.parent.right;
			if(this.right != null){
				this.right.parent = this;
			}
			
			this.parent.right = this;
			
		}else{
			this.parent.right = this.right;
			if(this.right != null){
				this.right.parent = this.parent;
			}
			
			this.right = this.left;
			
			this.left = this.parent.left;
			if(this.left != null){
				this.left.parent = this;
			}
			
			this.parent.left = this;
		}
		
		return;
	}
	
	//zig-zig操作
	public void zig_zig(){
		
		//キー・データのスワップ
		int temp_key = this.key;
		T temp_value = this.value;
		this.key = this.parent.parent.key;
		this.value = this.parent.parent.value;
		this.parent.parent.key = temp_key;
		this.parent.parent.value = temp_value;
		
		//回転
		if(this.parent.left == this){
			this.parent.parent.left = this.left;
			if(this.parent.parent.left != null){
				this.parent.parent.left.parent = this.parent.parent;
			}
			this.parent.left = this.right;
			if(this.parent.left != null){
				this.parent.left.parent = this.parent;
			}
			this.left = this.parent.right;
			if(this.left != null){
				this.left.parent = this;
			}
			this.right = this.parent.parent.right;
			if(this.right != null){
				this.right.parent = this;
			}
			this.parent.parent.right = this.parent;
			this.parent.right = this;
		}else{
			this.parent.parent.right = this.right;
			if(this.parent.parent.right != null){
				this.parent.parent.right.parent = this.parent.parent;
			}
			this.parent.right = this.left;
			if(this.parent.right != null){
				this.parent.right.parent = this.parent;
			}
			this.right = this.parent.left;
			if(this.right != null){
				this.right.parent = this;
			}
			this.left = this.parent.parent.left;
			if(this.left != null){
				this.left.parent = this;
			}
			this.parent.parent.left = this.parent;
			this.parent.left = this;
		}
		return;
	}
	
	//zig-zag操作
	public void zig_zag(){
		
		//キー・データのスワップ
		int temp_key = this.key;
		T temp_value = this.value;
		this.key = this.parent.parent.key;
		this.value = this.parent.parent.value;
		this.parent.parent.key = temp_key;
		this.parent.parent.value = temp_value;
		
		//回転
		if(this.parent.right == this){
			this.parent.right = this.left;
			if(this.parent.right != null){
				this.parent.right.parent = this.parent;
			}
			this.left = this.right;
			this.right = this.parent.parent.right;
			if(this.right != null){
				this.right.parent = this;
			}
			this.parent.parent.right = this;
			this.parent = this.parent.parent;
		}else{
			this.parent.left = this.right;
			if(this.parent.left != null){
				this.parent.left.parent = this.parent;
			}
			this.right = this.left;
			this.left = this.parent.parent.left;
			if(this.left != null){
				this.left.parent = this;
			}
			this.parent.parent.left = this;
			this.parent = this.parent.parent;
		}
		return;
	}
	
	//Splay操作
	public void Splay(){
		SplayTree<T> st = this;
		while(st.parent != null){
			if(st.parent.parent == null){
				//親が根ならzig
				st.zig();
				st = st.parent;
			}else if((st.parent.parent.left == st.parent && st.parent.left == st) || (st.parent.parent.right == st.parent && st.parent.right == st)){
				st.zig_zig();
				st = st.parent.parent;
			}else{
				st.zig_zag();
				st = st.parent;
			}
		}
		return;
	}

zig、zig-zig、zig-zagという三種類の「スプレーステップ」のうち、そのノードの親とそのまた親の状況をみて一つ選んで実行。これをwhileループで繰り返し行い、対象ノードを根まで引き上げます。
つまり、各基本操作後には、スプレー操作の対象となったノードを根とする木になっているというわけです。

スプレー木クラス制作において、この操作を起動させるタイミングと実行対象のノードが、少し迷うとこだった。↑のリンク先のWikiにも詳しくは書いておらず、「アクセスしたノード」としか書いてない。
特に「削除」は、指定したノード先は既に削除されているわけで、どうしたもんかと迷いました。

Wikiのリンク先のスプレー木可視化シミュレータで色々試してみた結果、とりあえずこのクラスの仕様では、

(1)挿入操作：挿入後、挿入（または上書き）したノードに対し適用。

(2)参照操作：キーに合致するノードを発見したら、参照したノードに対し適用。

(3)削除操作：削除したのち、削除されたノードの親に対し適用。ただし、削除ノードが両方に子をもち、その右部分木の最小ノードが代わりに木から切り離されたときは、切り離されたノードの親に適用。

としました。（実際にSleator、Tarjanによって発明された正式なものとは異なる可能性がございます。）

で、挿入、参照は前の記事（http://d.hatena.ne.jp/g940425/20101211/1292088124）での二分探索木とほぼ同じで次の通り。
↑で示した場所にスプレー操作を挟んである。

	//木に挿入
	public void insert(int key,T value){
		
		if(this.parent == null && this.value == null){
			//根が空の場合
			this.value = value;
			this.key = key;
			return;
		}else if(this.key > key){
			//左に挿入
			if(this.left == null){
				//左に子がない
				this.left = new SplayTree<T>(key,value,this);
				//Splay操作
				this.left.Splay();
			}else {
				//左に部分木あり
				this.left.insert(key,value);
			}
		}else if(this.key < key){
			//右に挿入
			if(this.right == null){
				//右に子がない
				this.right = new SplayTree<T>(key,value,this);
				//Splay操作
				this.right.Splay();
			}else {
				//右に部分木あり
				this.right.insert(key,value);
			}
		}else{
			//既存のキーの場合：上書きする
			this.value = value;
			//Splay操作
			this.Splay();
		}
		
		return;
	}
	
	//キーを指定して検索
	public SplayTree<T> search(int key){
		
		if(this.key == key && this.value != null){
			//Splay操作
			this.Splay();
			return this;
		}
		if(this.key > key && this.left != null){
			return this.left.search(key);
		}
		if(this.key < key && this.right != null){
			return this.right.search(key);
		}
		return null;
	}

で、削除は少し変更してある。

	//最小の値を削除
	//木から切り取るだけなので、この関数から返ったノードへのアドレスを呼び出し側で受けることで削除したノードへのアクセスが可能
	//なお、削除操作での使用を想定しているため、削除ノードが根だった場合を考慮していない
	public SplayTree<T> extractMin(){
		if(this.left == null){
			//左に子を持たない場合：これが最小ノードなので、削除
			if(this.right == null){
				//孤立した（子がない）場合：削除ノードを切り離す
				if(this.parent.left == this){
					this.parent.left = null;
				}else {
					this.parent.right = null;
				}
			}else{
				//右に子を持つ場合：このノードの代わりに右の子を親の子とする
				if(this.parent.left == this){
					this.parent.left = this.right;
				}else {
					this.parent.right = this.right;
				}
				this.right.parent = this.parent;
			}
			//Splay操作
			this.parent.Splay();
			return this;
		}else{
			//左に子を持つ場合：左の部分木の最小ノードを取り除く
			return this.left.extractMin();
		}
	}
	
	//キーを指定して削除
	public boolean delete(int key){
		if(this.key>key && this.left != null){
			return this.left.delete(key);
		}else if(this.key<key && this.right != null){
			return this.right.delete(key);
		}else if(this.key == key){
			if(this.left == null && this.right == null){
				if(this.parent != null){
					//子が根ではなく、両方とも子がない場合：削除ノードを切り離す
					if(this.parent.left == this){
						this.parent.left = null;
					}else {
						this.parent.right = null;
					}
					//Splay操作
					this.parent.Splay();
				}else{
					//子が根であり、両方とも子がない場合：キーと値を削除する
					this.key = 0;
					this.value = null;
				}
			}else if(this.left == null){
				if(this.parent != null){
					//子が根ではなく、左にのみ子がない場合：このノードの代わりに右の子を親の子とする
					if(this.parent.left == this){
						this.parent.left = this.right;
					}else {
						this.parent.right = this.right;
					}
					this.right.parent = this.parent;
					//Splay操作
					this.parent.Splay();
				}else{
					//子が根であり、左にのみ子がない場合：右のノードのデータを根に入れ、右のノードの子を受け継ぐ
					this.key = this.right.key;
					this.value = this.right.value;
					this.left = this.right.left;
					this.right = this.right.right;
					if(this.right != null)this.right.parent = this;
					if(this.left != null)this.left.parent = this;
				}
			}else if(this.right == null){
				if(this.parent != null){
					//子が根ではなく、右にのみ子がない場合：このノードの代わりに左の子を親の子とする
					if(this.parent.left == this){
						this.parent.left = this.left;
					}else {
						this.parent.right = this.left;
					}
					this.left.parent = this.parent;
					//Splay操作
					this.parent.Splay();
				}else{
					//子が根であり、右にのみ子がない場合：左のノードのデータを根に入れ、左のノードの子を受け継ぐ
					this.key = this.left.key;
					this.value = this.left.value;
					this.right = this.left.right;
					this.left = this.left.left;
					if(this.right != null)this.right.parent = this;
					if(this.left != null)this.left.parent = this;
				}
			}else{
				//両方に子を持つ場合：右の最小の子とデータを入れ替え、右の最小の子を切り離す
				SplayTree<T> min = this.right.extractMin();
				this.key = min.key;
				this.value = min.value;
			}
			return true;
		}else{
			return false;
		}
	}

以前（http://d.hatena.ne.jp/g940425/20101211/1292088124）は、削除は「検索→削除」という道筋を通っていたが、それだと検索した時点で削除するノードが根まで引っ張っていかれてしまうので、削除操作自体を再帰関数にしました。
再帰の仕方は参照と同じ。

さて。ということで、これを「class SplayTree{〜}」でまとめて一つの汎用クラスとして使えるようになるわけだけど、如何せんちょっと特殊な平衡二分探索木なので単純な性能比較も難しい。
試しに適当に疑似乱数を５００個ほど詰めてみたが、むしろ普通の二分探索木の方が低かった。

まあ、性能がどうとかではなく単純に書いてみたかっただけなんだけどね（　・ω・）〜♪

次の記事もまた別の木を書いてみるかもです。
それではまた。（・ω・）ﾉｼ