--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle-main/data/treemap/RedNode.cs	Sun Oct 23 07:40:50 2016 +0900
@@ -0,0 +1,101 @@
+using UnityEngine;
+using System.Collections;
+using System;
+using System.Collections.Generic;
+
+public class RedNode<K,V> : TreeMapNode<K,V>{
+
+	// Use this for initialization
+	public RedNode (K key, V value, TreeMapNode<K,V> left, TreeMapNode<K,V> right)
+		: base (key, value, left, right)
+	{
+	}
+	
+	// Update is called once per frame
+	public override bool isNotEmpty ()
+	{
+		return true;
+	}
+
+	public override rebuildNode<K,V> deleteNode() {
+		TreeMapNode<K,V> emptyNode = new EmptyNode<K,V>(this.getKey());
+		return new rebuildNode<K,V>(false, emptyNode);
+	}
+
+	public override Rotate checkRotate(Rotate side) {
+		if (side == Rotate.L) {
+			if (left.isRed())
+				return Rotate.R;
+			else if (right.isRed())
+				return Rotate.LR;
+			return Rotate.N;
+		} else {
+			if (left.isRed())
+				return Rotate.RL;
+			else if (right.isRed())
+				return Rotate.L;
+			return Rotate.N;
+		}
+	}
+
+	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();
+		} else if (this.lefts().isNotEmpty() && !this.rights().isNotEmpty()) { //左の部分木を昇格させる
+			newNode = lefts().createNode(lefts().getKey(), lefts().getValue(), lefts().lefts(), lefts().rights());
+			return new rebuildNode<K,V>(false, newNode);
+		} else if (!this.lefts().isNotEmpty() && this.rights().isNotEmpty()) { //右の部分木を昇格させる
+			newNode = rights().createNode(rights().getKey(), rights().getValue(), rights().lefts(), rights().rights());
+			return new rebuildNode<K,V>(false, newNode);
+		} else {//子ノードが左右にある場合
+			//左の部分木の最大の値を持つNodeと自身を置き換える
+			TreeMapNode<K, V> cur = this.lefts();
+			
+			while (cur.rights().isNotEmpty()) {
+				cur = cur.rights();
+			}
+			if (this.lefts().rights().isNotEmpty()) {
+				rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts().deleteSubTreeMaxNode(null, ctr, Rotate.L);
+				if (leftSubTreeNodeRebuildNode.rebuilds()) {
+					TreeMapNode<K, V> node = leftSubTreeNodeRebuildNode.getNode();
+					TreeMapNode<K, V> newParent = createNode(cur.getKey(), cur.getValue(), node, this.rights());
+					return node.deleteBalance(newParent, ctr);
+				}
+				TreeMapNode<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
+				newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.rights());
+				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(cur.getKey(), cur.getValue(), leftSubTreeNode, this.rights());
+				return new rebuildNode<K,V>(false, newNode);
+			}
+			
+		}
+	}
+
+	public override bool isRed() {
+		return true;
+	}
+
+	public override TreeMapNode<K, V> createNode(K key, V value, TreeMapNode<K, V> left, TreeMapNode<K, V> right) {
+		return new RedNode<K,V>(key, value, left, right);
+	}
+
+	public override TreeMapNode<K, V> insBalance() {
+		return this;
+	}
+
+	public override int checkDepth(int count, int minCount) { // test method
+		count++;
+		minCount = lefts().checkDepth(count, minCount);
+		minCount = rights().checkDepth(count, minCount);
+		return minCount;
+	}
+}