|
273
|
1 #include <stdio.h>
|
|
|
2
|
|
|
3 #include "../context.h"
|
|
|
4
|
|
445
|
5 // extern enum Relational compare(struct Node* node1, struct Node* node2);
|
|
|
6
|
|
273
|
7
|
|
|
8 Tree* createRedBlackTree(struct Context* context) {
|
|
|
9 struct Tree* tree = new Tree();
|
|
|
10 struct RedBlackTree* redBlackTree = new RedBlackTree();
|
|
418
|
11 tree->tree = (union Data*)redBlackTree;
|
|
273
|
12 redBlackTree->root = NULL;
|
|
415
|
13 redBlackTree->nodeStack = (union Data*)createSingleLinkedStack(context);
|
|
445
|
14
|
|
|
15 // tree->put = C_putRedBlackTree;
|
|
|
16 // tree->get = C_getRedBlackTree;
|
|
273
|
17 // tree->remove = C_removeRedBlackTree;
|
|
|
18 // tree->clear = C_clearRedBlackTree;
|
|
|
19 return tree;
|
|
|
20 }
|
|
|
21
|
|
445
|
22 // void printTree(union Data* data) {
|
|
|
23 // printTree1(data);
|
|
|
24 // printf("\n");
|
|
|
25 // }
|
|
|
26 //
|
|
|
27 // void printTree1(union Data* data) {
|
|
|
28 // struct Node* node = &data->Node;
|
|
|
29 // if (node == NULL) {
|
|
|
30 // printf("NULL");
|
|
|
31 // } else {
|
|
|
32 // printf("key = %d (", node->key);
|
|
|
33 // printTree1((union Data*)(node->right));
|
|
|
34 // printf("), (");
|
|
|
35 // printTree1((union Data*)(node->left));
|
|
|
36 // printf(")");
|
|
|
37 // }
|
|
|
38 // }
|
|
|
39 //
|
|
|
40 // __code putRedBlackTree(struct RedBlackTree* tree, struct Node* node) {
|
|
|
41 // struct Node* newNode = &ALLOCATE(context, Node)->Node;
|
|
|
42 // struct Node* root = tree->root;
|
|
|
43 // printTree(tree->root);
|
|
|
44 // tree->newNode = newNode;
|
|
|
45 // tree->root = newNode; // this should done at stackClear
|
|
|
46 // tree->parent = NULL;
|
|
|
47 // if (root) {
|
|
|
48 // tree->current = root;
|
|
|
49 // tree->result = compare(tree->current, node);
|
|
|
50 // goto insertRBTree(tree);
|
|
|
51 // }
|
|
|
52 // goto insertRBTree(tree, node);
|
|
|
53 // }
|
|
273
|
54
|
|
445
|
55 __code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) {
|
|
|
56 tree->current = 0;
|
|
|
57 nodeStack->stack = (union Data*)tree->nodeStack;
|
|
|
58 nodeStack->next = next;
|
|
|
59 goto meta(context, tree->nodeStack->clear);
|
|
273
|
60 }
|
|
|
61
|
|
445
|
62 // __code getRedBlackTree(struct RedBlackTree* tree, __code next(...)) {
|
|
|
63 // if (tree->root) {
|
|
|
64 // tree->current = tree->root;
|
|
|
65 // goto insertRBTree();
|
|
|
66 // // goto deleteRBTree();
|
|
|
67 // }
|
|
|
68 //
|
|
|
69 // goto next(...);
|
|
|
70 // }
|
|
273
|
71
|
|
445
|
72 __code insertRBTree(struct Node* newNode,struct Stack* nodeStack, struct RedBlackTree* rbtree) {
|
|
|
73 rbtree->current = rbtree->root;
|
|
|
74 goto insertLocate(newNode, nodeStack, rbtree);
|
|
273
|
75 }
|
|
|
76
|
|
445
|
77 __code insertLocate(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* rbtree) {
|
|
273
|
78
|
|
445
|
79 struct Stack* nodeStack = tree->nodeStack;
|
|
|
80 struct Node* trace = rbtree->current;
|
|
273
|
81
|
|
445
|
82 // i think faster "compare rbtree->current, node" than "switch case EQ, LT, RT"
|
|
|
83 if (rbtree->current > node) {
|
|
|
84 goto nodestack->push(nodeStack,trace,insertLocate);
|
|
|
85 } else if (rbtree->current < node) {
|
|
|
86 goto nodestack->push(nodeStack, trace, insertLocate);
|
|
|
87 } else if (rbtree->current == node) {
|
|
|
88 printf("alady member this node(insertLocate)");
|
|
|
89 goto next(...);
|
|
|
90 } else if (rbtree->current == null){
|
|
|
91 rbtree->current = node;
|
|
|
92 goto nodeStack->pop(nodeStack,insertBalance);
|
|
|
93 }else{
|
|
|
94 rbtree->root = node;
|
|
|
95 goto next(...);
|
|
|
96 }
|
|
273
|
97 }
|
|
|
98
|
|
445
|
99 __code insertBalance(struct RedBlackTree* rbtree, struct Node* nodeStack, struct Node* node){
|
|
|
100 rbtree->current = nodeStack->data;
|
|
|
101 // insert case
|
|
|
102 if (current->left->left || current->left->right){
|
|
|
103 goto insertBalanceLeft(rbtree,nodeStack);
|
|
|
104 }else if (current->right->left || current->right->right){
|
|
|
105 goto insertBalanceRight(rbtree,nodeStack);
|
|
|
106 }else{
|
|
|
107 goto nodeStack->pop(nodeStack,insertBalance);
|
|
|
108 }
|
|
273
|
109 }
|
|
|
110
|
|
445
|
111 __code insesrtBalanceLeft(struct RedBlackTree* rbtree, struct Node* nodeStack, struct Node* node){
|
|
273
|
112
|
|
445
|
113 if (current->color == Black && current->left->color == Red && current->left->left->color == Red){
|
|
|
114 struct Node* tmp0 = rbtree->current;
|
|
|
115 struct Node* tmp1 = rbtree->current->left;
|
|
|
116 struct Node* tmp2 = rbtree->current->left->left;
|
|
273
|
117
|
|
445
|
118 rbtree->current = tmp1;
|
|
|
119 rbtree->current->right = tmp0;
|
|
|
120 rbtree->current->left = tmp2;
|
|
|
121 rbtree->current->right->right = tmp0->right;
|
|
|
122 rbtree->current->right->left = tmp1->right;
|
|
|
123 rbtree->current->color = Black;
|
|
|
124 rbtree->current->left->color = Red;
|
|
|
125 rbtree->current->right->color = Red;
|
|
|
126 goto nodeStack->pop(nodeStack,insertBalance);
|
|
273
|
127
|
|
445
|
128 } else if(current->color == Black && current->left->color == Red && current->left->right->color == Red){
|
|
|
129 struct Node* tmp0 = rbtree->current;
|
|
|
130 struct Node* tmp1 = rbtree->current->left;
|
|
|
131 struct Node* tmp2 = rbtree->current->left->right;
|
|
273
|
132
|
|
445
|
133 rbtree->current = tmp1;
|
|
|
134 rbtree->current->right = tmp0;
|
|
|
135 rbtree->current->left = tmp2;
|
|
|
136 rbtree->current->right->right = tmp0->right;
|
|
|
137 rbtree->current->right->left = tmp1->right;
|
|
|
138 rbtree->current->color = Black;
|
|
|
139 rbtree->current->left->color = Red;
|
|
|
140 rbtree->current->right->color = Red;
|
|
|
141 goto nodeStack->pop(nodeStack,insertBalance);
|
|
273
|
142
|
|
445
|
143 }
|
|
|
144 }
|
|
273
|
145
|
|
445
|
146 __code insertBalanceRight(struct RedBlackTree* rbtree, struct Node* nodeStack, struct Node* node){
|
|
|
147 if (current->color == Black && current->right->color == Red && current->right->right->color == Red){
|
|
|
148 struct Node* tmp0 = rbtree->current;
|
|
|
149 struct Node* tmp1 = rbtree->current->left;
|
|
|
150 struct Node* tmp2 = rbtree->current->left->right;
|
|
273
|
151
|
|
445
|
152 rbtree->current = tmp1;
|
|
|
153 rbtree->current->right = tmp0;
|
|
|
154 rbtree->current->left = tmp2;
|
|
|
155 rbtree->current->right->right = tmp0->right;
|
|
|
156 rbtree->current->right->left = tmp1->right;
|
|
|
157 rbtree->current->color = Black;
|
|
|
158 rbtree->current->left->color = Red;
|
|
|
159 rbtree->current->right->color = Red;
|
|
|
160 goto nodeStack->pop(nodeStack,insertBalance);
|
|
273
|
161
|
|
445
|
162 } else if (current->color == Black && current->right->color == Red && current->right->left->color == Red){
|
|
273
|
163
|
|
445
|
164 struct Node* tmp0 = rbtree->current;
|
|
|
165 struct Node* tmp1 = rbtree->current->right;
|
|
|
166 struct Node* tmp2 = rbtree->current->right->left;
|
|
273
|
167
|
|
445
|
168 rbtree->current = tmp1;
|
|
|
169 rbtree->current->right = tmp0;
|
|
|
170 rbtree->current->left = tmp2;
|
|
|
171 rbtree->current->right->right = tmp0->right;
|
|
|
172 rbtree->current->right->left = tmp1->right;
|
|
|
173 rbtree->current->color = Black;
|
|
|
174 rbtree->current->left->color = Red;
|
|
|
175 rbtree->current->right->color = Red;
|
|
|
176 goto nodeStack->pop(nodeStack,insertBalance);
|
|
273
|
177
|
|
445
|
178 } else {
|
|
|
179 printf("error insertBalanceRight");
|
|
|
180 goto next(...);
|
|
|
181 }
|
|
|
182 }
|
|
273
|
183
|
|
445
|
184 // insertion code end
|
|
273
|
185
|
|
445
|
186
|
|
|
187
|
|
273
|
188
|
|
445
|
189 // __code deleteRBTree(struct RedBlackTree newNode, struct RedBlackTree* rbtree) {
|
|
|
190 // rbtree->current = rbtree->root;
|
|
|
191 // goto deleteLocate;
|
|
|
192 // }
|
|
273
|
193
|
|
445
|
194 // __code deleteLocate(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* rbtree) {
|
|
|
195 // /\* check delete node locate and push route node *\/
|
|
|
196 // struct Stack* nodeStack = tree->nodeStack;
|
|
|
197 // struct Node* trace = rbtree->current;
|
|
273
|
198
|
|
445
|
199 // if (rbtree->current > node) {
|
|
|
200 // goto nodeStack->push(nodeStack,trace,deleteLocate);
|
|
|
201 // } else if (rbtree->current < node) {
|
|
|
202 // goto nodeStack->push(trace,deleteLocate);
|
|
|
203 // } else if (rbtree->current == node) {
|
|
|
204 // // trace = rbtree->current;
|
|
|
205 // goto deleteNode(struct Stack* nodeStack, struct RedBlackTree* rbtree,struct Node* trace);
|
|
|
206 // // goto nodeStack->push(trace,deleteNode);
|
|
|
207 // } else if (rbtree->current == null){
|
|
|
208 // printf("No member Delete node (__code deleteLocate)");
|
|
|
209 // goto next(...);
|
|
|
210 // } else {
|
|
|
211 // printf("Error,__code deleteLocate");
|
|
|
212 // goto next(...);
|
|
|
213 // }
|
|
|
214 // }
|
|
273
|
215
|
|
445
|
216 // __code deleteNode(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* rbtree) {
|
|
|
217 // struct Stack* nodeStack = tree->nodeStack;
|
|
|
218 // struct Node* replaceNode = nodeStack->data;
|
|
273
|
219
|
|
445
|
220 // if(replaceNode->right == null){
|
|
|
221 // rbtree->current = replaceNode;
|
|
|
222 // rbtree->current = rbtree->current->left;
|
|
|
223 // goto deleteUnbalance(nodeStack,replaceNode);
|
|
|
224 // }else if(replaceNode->left == null){
|
|
|
225 // rbtree->current = replaceNode;
|
|
|
226 // rbtree->current = rbtree->current->right;
|
|
|
227 // goto deleteUnbalance(nodeStack,replaceNode);
|
|
|
228 // //goto deleteNodeReplaceNull();
|
|
|
229 // }else{
|
|
|
230 // // goto nodeStack->push(nodeStack,replaceNode,deleteNodeReplace);
|
|
|
231 // goto deleteNodeReplace(nodeStack,replaceNode);
|
|
|
232 // }
|
|
|
233 // }
|
|
273
|
234
|
|
|
235
|
|
445
|
236 // __code deleteNodeReplace(){
|
|
273
|
237
|
|
445
|
238 // if (replaceNode->left != null){
|
|
|
239 // replaceNode = replaceNode->left;
|
|
|
240 // goto deleteNodeReplace();
|
|
|
241 // }else if(){
|
|
273
|
242
|
|
|
243
|
|
445
|
244 // }
|
|
|
245
|
|
|
246 // }
|
|
|
247
|
|
273
|
248
|
|
445
|
249 // __code deleteUnbalance() {
|
|
|
250 // if () {
|
|
|
251 // }
|
|
273
|
252
|
|
445
|
253 // }
|
