|
35
|
1 using System;
|
|
20
|
2 using System.Collections;
|
|
|
3 using System.Collections.Generic;
|
|
|
4
|
|
|
5 public class RedNode<K,V> : TreeMapNode<K,V>{
|
|
|
6
|
|
|
7 // Use this for initialization
|
|
|
8 public RedNode (K key, V value, TreeMapNode<K,V> left, TreeMapNode<K,V> right)
|
|
|
9 : base (key, value, left, right)
|
|
|
10 {
|
|
|
11 }
|
|
|
12
|
|
|
13 // Update is called once per frame
|
|
|
14 public override bool isNotEmpty ()
|
|
|
15 {
|
|
|
16 return true;
|
|
|
17 }
|
|
|
18
|
|
|
19 public override rebuildNode<K,V> deleteNode() {
|
|
|
20 TreeMapNode<K,V> emptyNode = new EmptyNode<K,V>(this.getKey());
|
|
|
21 return new rebuildNode<K,V>(false, emptyNode);
|
|
|
22 }
|
|
|
23
|
|
|
24 public override Rotate checkRotate(Rotate side) {
|
|
|
25 if (side == Rotate.L) {
|
|
|
26 if (left.isRed())
|
|
|
27 return Rotate.R;
|
|
|
28 else if (right.isRed())
|
|
|
29 return Rotate.LR;
|
|
|
30 return Rotate.N;
|
|
|
31 } else {
|
|
|
32 if (left.isRed())
|
|
|
33 return Rotate.RL;
|
|
|
34 else if (right.isRed())
|
|
|
35 return Rotate.L;
|
|
|
36 return Rotate.N;
|
|
|
37 }
|
|
|
38 }
|
|
|
39
|
|
|
40 public override rebuildNode<K,V> replaceNode(TreeMapNode<K, V> parent, Comparer<K> ctr) {
|
|
|
41 TreeMapNode<K, V> newNode;
|
|
|
42 if (!this.lefts().isNotEmpty() && !this.rights().isNotEmpty()) { //自身を削除する
|
|
|
43 return deleteNode();
|
|
|
44 } else if (this.lefts().isNotEmpty() && !this.rights().isNotEmpty()) { //左の部分木を昇格させる
|
|
|
45 newNode = lefts().createNode(lefts().getKey(), lefts().getValue(), lefts().lefts(), lefts().rights());
|
|
|
46 return new rebuildNode<K,V>(false, newNode);
|
|
|
47 } else if (!this.lefts().isNotEmpty() && this.rights().isNotEmpty()) { //右の部分木を昇格させる
|
|
|
48 newNode = rights().createNode(rights().getKey(), rights().getValue(), rights().lefts(), rights().rights());
|
|
|
49 return new rebuildNode<K,V>(false, newNode);
|
|
|
50 } else {//子ノードが左右にある場合
|
|
|
51 //左の部分木の最大の値を持つNodeと自身を置き換える
|
|
|
52 TreeMapNode<K, V> cur = this.lefts();
|
|
|
53
|
|
|
54 while (cur.rights().isNotEmpty()) {
|
|
|
55 cur = cur.rights();
|
|
|
56 }
|
|
|
57 if (this.lefts().rights().isNotEmpty()) {
|
|
|
58 rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts().deleteSubTreeMaxNode(null, ctr, Rotate.L);
|
|
|
59 if (leftSubTreeNodeRebuildNode.rebuilds()) {
|
|
|
60 TreeMapNode<K, V> node = leftSubTreeNodeRebuildNode.getNode();
|
|
|
61 TreeMapNode<K, V> newParent = createNode(cur.getKey(), cur.getValue(), node, this.rights());
|
|
|
62 return node.deleteBalance(newParent, ctr);
|
|
|
63 }
|
|
|
64 TreeMapNode<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
|
|
|
65 newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.rights());
|
|
|
66 return new rebuildNode<K,V>(false, newNode);
|
|
|
67 } else {
|
|
|
68 rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.lefts().replaceNode(this, ctr);
|
|
|
69 if (leftSubTreeNodeRebuildNode.rebuilds()) {
|
|
|
70 TreeMapNode<K, V> node = leftSubTreeNodeRebuildNode.getNode();
|
|
|
71 TreeMapNode<K, V> newParent = createNode(this.lefts().getKey(), this.lefts().getValue(), node, this.rights());
|
|
|
72 return node.deleteBalance(newParent, ctr);
|
|
|
73 }
|
|
|
74 TreeMapNode<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
|
|
|
75 newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.rights());
|
|
|
76 return new rebuildNode<K,V>(false, newNode);
|
|
|
77 }
|
|
|
78
|
|
|
79 }
|
|
|
80 }
|
|
|
81
|
|
|
82 public override bool isRed() {
|
|
|
83 return true;
|
|
|
84 }
|
|
|
85
|
|
|
86 public override TreeMapNode<K, V> createNode(K key, V value, TreeMapNode<K, V> left, TreeMapNode<K, V> right) {
|
|
|
87 return new RedNode<K,V>(key, value, left, right);
|
|
|
88 }
|
|
|
89
|
|
|
90 public override TreeMapNode<K, V> insBalance() {
|
|
|
91 return this;
|
|
|
92 }
|
|
|
93
|
|
|
94 public override int checkDepth(int count, int minCount) { // test method
|
|
|
95 count++;
|
|
|
96 minCount = lefts().checkDepth(count, minCount);
|
|
|
97 minCount = rights().checkDepth(count, minCount);
|
|
|
98 return minCount;
|
|
|
99 }
|
|
|
100 }
|
