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