--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle-main/data/treemap/BlackNode.cs	Mon Nov 07 01:05:24 2016 +0900
@@ -0,0 +1,126 @@
+using UnityEngine;
+using System.Collections.Generic;
+using System.Collections;
+using System;
+
+public class BlackNode<K,V> 
+	:TreeMapNode<K,V>
+{
+	
+	public BlackNode (K key, V value, TreeMapNode<K, V> left, TreeMapNode<K, V> right)
+		: base (key, value, left, right)
+	{
+	}
+
+	public override rebuildNode<K,V> deleteNode ()
+	{
+		EmptyNode<K, V> emptyNode = new EmptyNode<K,V> (key);
+		return new rebuildNode<K,V> (true, emptyNode);
+	}
+
+	public override int checkDepth (int count, int minCount)
+	{ // test method
+		count++;
+		minCount = lefts ().checkDepth (count, minCount);
+		minCount = rights ().checkDepth (count, minCount);
+		return minCount;
+	}
+
+	public override bool isNotEmpty ()
+	{
+		return true;
+	}
+
+	public override TreeMapNode<K, V> createNode (K key, V value, TreeMapNode<K, V> left, TreeMapNode<K, V> right)
+	{
+		return new BlackNode<K,V> (key, value, left, right);
+	}
+
+	public override TreeMapNode<K, V> insBalance ()
+	{
+		Rotate spin = left.checkRotate (Rotate.L);
+
+		if (spin == Rotate.R) {
+			TreeMapNode<K, V> leftChild = new BlackNode<K,V> (left.lefts ().getKey (), left.lefts ().getValue (), left.lefts ().lefts (), left.lefts ().rights ());
+			TreeMapNode<K, V> rightChild = new BlackNode<K,V> (getKey (), getValue (), left.rights (), right);
+			return new RedNode<K,V> (left.getKey (), left.getValue (), leftChild, rightChild);
+
+		} else if (spin == Rotate.LR) {
+			TreeMapNode<K, V> leftChild = new BlackNode<K,V> (left.getKey (), left.getValue (), left.lefts (), left.rights ().lefts ());
+			TreeMapNode<K, V> rightChild = new BlackNode<K,V> (getKey (), getValue (), left.rights ().rights (), right);
+			return new RedNode<K,V> (left.rights ().getKey (), left.rights ().getValue (), leftChild, rightChild);
+
+		}
+
+		spin = right.checkRotate (Rotate.R);
+		if (spin == Rotate.L) {
+			TreeMapNode<K, V> leftChild = new BlackNode<K,V> (getKey (), getValue (), left, right.lefts ());
+			TreeMapNode<K, V> rightChild = new BlackNode<K,V> (right.rights ().getKey (), right.rights ().getValue (), right.rights ().lefts (), right.rights ().rights ());
+			return new RedNode<K,V> (right.getKey (), right.getValue (), leftChild, rightChild);
+
+		} else if (spin == Rotate.RL) {
+			TreeMapNode<K, V> leftChild = new BlackNode<K,V> (getKey (), getValue (), left, right.lefts ().lefts ());
+			TreeMapNode<K, V> rightChild = new BlackNode<K,V> (right.getKey (), right.getValue (), right.lefts ().rights (), right.rights ());
+			return new RedNode<K,V> (right.lefts ().getKey (), right.lefts ().getValue (), leftChild, rightChild);
+
+		}
+
+		return this;
+	}
+
+	public override Rotate checkRotate (Rotate side)
+	{
+		return Rotate.N;
+	}
+
+	public override bool isRed ()
+	{
+		return false;
+	}
+
+	public override rebuildNode<K,V> replaceNode (TreeMapNode<K, V> parent, Comparer<K> ctr)
+	{
+		TreeMapNode<K, V> newNode;
+		if (!this.lefts ().isNotEmpty () && !this.rights ().isNotEmpty ()) { //自身を削除する
+			return deleteNode ();//黒が1つ減るので木のバランスを取る
+		} else if (this.lefts ().isNotEmpty () && !this.rights ().isNotEmpty ()) { //左の部分木を昇格させる
+			newNode = createNode (lefts ().getKey (), lefts ().getValue (), lefts ().lefts (), lefts ().rights ());
+			if (!this.lefts ().isRed ()) //昇格させる木のrootが黒だったらバランスを取る
+				return new rebuildNode<K,V> (true, newNode);
+			return new rebuildNode<K,V> (false, newNode);
+		} else if (!this.lefts ().isNotEmpty () && this.rights ().isNotEmpty ()) { //右の部分木を昇格させる
+			newNode = createNode (rights ().getKey (), rights ().getValue (), rights ().lefts (), rights ().rights ());
+			if (!this.rights ().isRed ()) //昇格させる木のrootが黒だったらバランスを取る
+				return new rebuildNode<K,V> (true, newNode);
+			return new rebuildNode<K,V> (false, newNode);
+		} else {//子ノードが左右にある場合 二回目はここには入らない
+			//左の部分木の最大の値を持つNodeと自身を置き換える
+			TreeMapNode<K, V> cur = this.lefts ();
+			while (cur.rights ().isNotEmpty ()) { //左の部分期の最大値を持つNodeを取得する
+				cur = cur.rights ();
+			}
+			if (this.lefts ().rights ().isNotEmpty ()) { //左の部分木が右の子を持っているか
+				rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts ().deleteSubTreeMaxNode (null, ctr, Rotate.L);//最大値を削除した左の部分木を返す。rootはthisと同じ。
+				if (leftSubTreeNodeRebuildNode.rebuilds ()) {
+					TreeMapNode<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode ();
+					TreeMapNode<K, V> newParent = createNode (cur.getKey (), cur.getValue (), leftSubTreeNode, this.rights ());
+					return leftSubTreeNode.deleteBalance (newParent, ctr);
+				}
+				//same name onece used.
+				TreeMapNode<K, V> leftSubTreeNodes = leftSubTreeNodeRebuildNode.getNode ();
+				newNode = createNode (cur.getKey (), cur.getValue (), leftSubTreeNodes, this.rights ()); //rootをcurと入れ替えることでNodeの削除は完了する
+				return new rebuildNode<K,V> (false, newNode);
+			} else {
+				rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts ().replaceNode (this, ctr);//右の子がいなかった場合、左の子を昇格させるだけで良い。
+				if (leftSubTreeNodeRebuildNode.rebuilds ()) {
+					TreeMapNode<K, V> node = leftSubTreeNodeRebuildNode.getNode ();
+					TreeMapNode<K, V> newParent = createNode (this.lefts ().getKey (), this.lefts ().getValue (), node, this.rights ());
+					return node.deleteBalance (newParent, ctr);
+				}
+				TreeMapNode<K,V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode ();
+				newNode = createNode (this.lefts ().getKey (), this.lefts ().getValue (), leftSubTreeNode, this.rights ());
+				return new rebuildNode<K,V> (false, newNode);
+			}
+		}
+	}
+}
\ No newline at end of file