Mercurial > hg > Database > jungle-sharp
view src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/BlackNode.cs @ 0:dec15de2c6ff
first commit
author | Kazuma |
---|---|
date | Tue, 21 Jun 2016 17:11:12 +0900 |
parents | |
children | 5c58219da97e |
line wrap: on
line source
using UnityEngine; 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 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); } } } }