Mercurial > hg > Database > jungle-sharp

comparison src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle-main/data/treemap/BlackNode.cs @ 17:01a08cf4b2d9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Liq Files
author Kazuma
date Mon, 07 Nov 2016 01:05:24 +0900
parents abe0c247f5a5
children
comparison
equal deleted inserted replaced
16:8f1ce942abfc 17:01a08cf4b2d9
1 using UnityEngine;
2 using System.Collections.Generic;
3 using System.Collections;
4 using System;
5
6 public class BlackNode<K,V>
7 :TreeMapNode<K,V>
8 {
9
10 public BlackNode (K key, V value, TreeMapNode<K, V> left, TreeMapNode<K, V> right)
11 : base (key, value, left, right)
12 {
13 }
14
15 public override rebuildNode<K,V> deleteNode ()
16 {
17 EmptyNode<K, V> emptyNode = new EmptyNode<K,V> (key);
18 return new rebuildNode<K,V> (true, emptyNode);
19 }
20
21 public override int checkDepth (int count, int minCount)
22 { // test method
23 count++;
24 minCount = lefts ().checkDepth (count, minCount);
25 minCount = rights ().checkDepth (count, minCount);
26 return minCount;
27 }
28
29 public override bool isNotEmpty ()
30 {
31 return true;
32 }
33
34 public override TreeMapNode<K, V> createNode (K key, V value, TreeMapNode<K, V> left, TreeMapNode<K, V> right)
35 {
36 return new BlackNode<K,V> (key, value, left, right);
37 }
38
39 public override TreeMapNode<K, V> insBalance ()
40 {
41 Rotate spin = left.checkRotate (Rotate.L);
42
43 if (spin == Rotate.R) {
44 TreeMapNode<K, V> leftChild = new BlackNode<K,V> (left.lefts ().getKey (), left.lefts ().getValue (), left.lefts ().lefts (), left.lefts ().rights ());
45 TreeMapNode<K, V> rightChild = new BlackNode<K,V> (getKey (), getValue (), left.rights (), right);
46 return new RedNode<K,V> (left.getKey (), left.getValue (), leftChild, rightChild);
47
48 } else if (spin == Rotate.LR) {
49 TreeMapNode<K, V> leftChild = new BlackNode<K,V> (left.getKey (), left.getValue (), left.lefts (), left.rights ().lefts ());
50 TreeMapNode<K, V> rightChild = new BlackNode<K,V> (getKey (), getValue (), left.rights ().rights (), right);
51 return new RedNode<K,V> (left.rights ().getKey (), left.rights ().getValue (), leftChild, rightChild);
52
53 }
54
55 spin = right.checkRotate (Rotate.R);
56 if (spin == Rotate.L) {
57 TreeMapNode<K, V> leftChild = new BlackNode<K,V> (getKey (), getValue (), left, right.lefts ());
58 TreeMapNode<K, V> rightChild = new BlackNode<K,V> (right.rights ().getKey (), right.rights ().getValue (), right.rights ().lefts (), right.rights ().rights ());
59 return new RedNode<K,V> (right.getKey (), right.getValue (), leftChild, rightChild);
60
61 } else if (spin == Rotate.RL) {
62 TreeMapNode<K, V> leftChild = new BlackNode<K,V> (getKey (), getValue (), left, right.lefts ().lefts ());
63 TreeMapNode<K, V> rightChild = new BlackNode<K,V> (right.getKey (), right.getValue (), right.lefts ().rights (), right.rights ());
64 return new RedNode<K,V> (right.lefts ().getKey (), right.lefts ().getValue (), leftChild, rightChild);
65
66 }
67
68 return this;
69 }
70
71 public override Rotate checkRotate (Rotate side)
72 {
73 return Rotate.N;
74 }
75
76 public override bool isRed ()
77 {
78 return false;
79 }
80
81 public override rebuildNode<K,V> replaceNode (TreeMapNode<K, V> parent, Comparer<K> ctr)
82 {
83 TreeMapNode<K, V> newNode;
84 if (!this.lefts ().isNotEmpty () && !this.rights ().isNotEmpty ()) { //自身を削除する
85 return deleteNode ();//黒が1つ減るので木のバランスを取る
86 } else if (this.lefts ().isNotEmpty () && !this.rights ().isNotEmpty ()) { //左の部分木を昇格させる
87 newNode = createNode (lefts ().getKey (), lefts ().getValue (), lefts ().lefts (), lefts ().rights ());
88 if (!this.lefts ().isRed ()) //昇格させる木のrootが黒だったらバランスを取る
89 return new rebuildNode<K,V> (true, newNode);
90 return new rebuildNode<K,V> (false, newNode);
91 } else if (!this.lefts ().isNotEmpty () && this.rights ().isNotEmpty ()) { //右の部分木を昇格させる
92 newNode = createNode (rights ().getKey (), rights ().getValue (), rights ().lefts (), rights ().rights ());
93 if (!this.rights ().isRed ()) //昇格させる木のrootが黒だったらバランスを取る
94 return new rebuildNode<K,V> (true, newNode);
95 return new rebuildNode<K,V> (false, newNode);
96 } else {//子ノードが左右にある場合 二回目はここには入らない
97 //左の部分木の最大の値を持つNodeと自身を置き換える
98 TreeMapNode<K, V> cur = this.lefts ();
99 while (cur.rights ().isNotEmpty ()) { //左の部分期の最大値を持つNodeを取得する
100 cur = cur.rights ();
101 }
102 if (this.lefts ().rights ().isNotEmpty ()) { //左の部分木が右の子を持っているか
103 rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts ().deleteSubTreeMaxNode (null, ctr, Rotate.L);//最大値を削除した左の部分木を返す。rootはthisと同じ。
104 if (leftSubTreeNodeRebuildNode.rebuilds ()) {
105 TreeMapNode<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode ();
106 TreeMapNode<K, V> newParent = createNode (cur.getKey (), cur.getValue (), leftSubTreeNode, this.rights ());
107 return leftSubTreeNode.deleteBalance (newParent, ctr);
108 }
109 //same name onece used.
110 TreeMapNode<K, V> leftSubTreeNodes = leftSubTreeNodeRebuildNode.getNode ();
111 newNode = createNode (cur.getKey (), cur.getValue (), leftSubTreeNodes, this.rights ()); //rootをcurと入れ替えることでNodeの削除は完了する
112 return new rebuildNode<K,V> (false, newNode);
113 } else {
114 rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts ().replaceNode (this, ctr);//右の子がいなかった場合、左の子を昇格させるだけで良い。
115 if (leftSubTreeNodeRebuildNode.rebuilds ()) {
116 TreeMapNode<K, V> node = leftSubTreeNodeRebuildNode.getNode ();
117 TreeMapNode<K, V> newParent = createNode (this.lefts ().getKey (), this.lefts ().getValue (), node, this.rights ());
118 return node.deleteBalance (newParent, ctr);
119 }
120 TreeMapNode<K,V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode ();
121 newNode = createNode (this.lefts ().getKey (), this.lefts ().getValue (), leftSubTreeNode, this.rights ());
122 return new rebuildNode<K,V> (false, newNode);
123 }
124 }
125 }
126 }