Skip to content

Commit 9919d4e

Browse files
author
Raven G. Duran
committed
Partial Stack Implementation fro multiple splits
1 parent ec4709c commit 9919d4e

File tree

2 files changed

+69
-27
lines changed

2 files changed

+69
-27
lines changed

‎btree.c

+69-27
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,16 @@ struct nodePosition {
1515
struct node* box;
1616
};
1717

18+
// Left-right stack for multiple splitting
19+
struct splitStack {
20+
struct node *leftHalf;
21+
struct node *rightHalf;
22+
struct splitStack *next;
23+
} *head = NULL;
24+
25+
void pushS(struct node *leftHalf, struct node *rightHalf);
26+
struct splitStack *popS();
27+
1828
// Globals
1929
int treeOrder;
2030

@@ -28,7 +38,7 @@ void doInOrder();
2838
// Tree Operations
2939
struct node* newNode(int value,struct node *parent);
3040
struct node* insertN(int value,struct node *root,struct node *parent);
31-
struct node* searchNValue(int value,struct node *root);
41+
struct nodePosition* searchNValue(int value,struct node *root);
3242
struct nodePosition* searchNBox(struct node *toFind,struct node *root);
3343

3444
// Printing
@@ -209,14 +219,20 @@ struct node* insertN(int value,struct node *root,struct node *parent){
209219
struct node *rightHalf = NULL;
210220

211221
for (i = 0; i <= left; i++){ // Move all left half data to new LeftHalf Box
212-
leftHalf = insertN(root->value[i],leftHalf,parent); // Set the parent to NULL temporarily
222+
leftHalf = insertN(root->value[i],leftHalf,NULL); // Set the parent to NULL temporarily
213223
leftHalf->keys[i] = root->keys[i];
224+
225+
if (root->keys[i] != NULL) root->keys[i]->parent = leftHalf;
214226
} leftHalf->keys[left+1] = root->keys[left+1];
227+
if (root->keys[treeOrder] != NULL) root->keys[treeOrder]->parent = leftHalf;
215228

216229
for (i = right; i < treeOrder; i++){ // Move all right half data to new LeftHalf Box
217-
rightHalf = insertN(root->value[i],rightHalf,parent);
230+
rightHalf = insertN(root->value[i],rightHalf,NULL);
218231
rightHalf->keys[i] = root->keys[i];
232+
233+
if (root->keys[i] != NULL) root->keys[i]->parent = rightHalf;
219234
} rightHalf->keys[treeOrder] = root->keys[treeOrder];
235+
if (root->keys[treeOrder] != NULL) root->keys[treeOrder]->parent = rightHalf;
220236

221237
int pIsNull = parent == NULL ? 1 : 0;
222238
struct node *tempRoot = root;
@@ -234,30 +250,27 @@ struct node* insertN(int value,struct node *root,struct node *parent){
234250
return parent;
235251
} else {
236252
// Find the parent of the current left and right box
237-
struct nodePosition *nodeF = searchNBox(tempRoot,parent);
238-
if (nodeF != NULL){
239-
nodeF->box->keys[nodeF->key] = leftHalf;
240-
nodeF->box->keys[nodeF->key+1] = rightHalf;
241-
}
242-
243-
/*
253+
int found = 0;
244254
for (i = 0; i < parent->keyCount; i++){
245-
if (parent->keys[i] == tempRoot){
255+
if (parent->keys[i] != NULL && parent->keys[i] == tempRoot){
246256
parent->keys[i] = leftHalf;
247257
parent->keys[i+1] = rightHalf;
248-
} else if (parent->keys[i] != NULL) {
249-
for (j = 0; j < parent->keys[i]->keyCount; j++){
250-
if (parent->keys[i]->keys[j] == tempRoot){
251-
parent->keys[i]->keys[j] = leftHalf;
252-
parent->keys[i]->keys[j+1] = rightHalf;
253-
}
254-
}
258+
259+
leftHalf->parent = parent;
260+
rightHalf->parent = parent;
261+
found = 1;
255262
}
256263
}
257-
*/
258264

265+
266+
struct nodePosition *nodeF = searchNBox(tempRoot,tRoot);
267+
if (nodeF != NULL && !found) {
268+
printf("Beep: i is %d\n",nodeF->key);
269+
nodeF->box->keys[nodeF->key] = leftHalf;
270+
nodeF->box->keys[nodeF->key+1] = rightHalf;
271+
}
259272

260-
free(tempRoot);
273+
//free(tempRoot);
261274
return leftHalf;
262275
}
263276

@@ -268,13 +281,18 @@ struct node* insertN(int value,struct node *root,struct node *parent){
268281
return root;
269282
}
270283

271-
struct node* searchNValue(int value,struct node *root){
284+
struct nodePosition* searchNValue(int value,struct node *root){
272285
int i;
273-
struct node *nodeF = NULL;
286+
struct nodePosition *nodeF = NULL;
274287
if (root == NULL) return NULL;
275288
else {
276289
for (i = 0; i < root->keyCount; i++){ // -1 since left and right key of every data box
277-
if (root->value[i] == value) return root;
290+
if (root->value[i] == value) {
291+
nodeF = (struct nodePosition*)malloc(sizeof(struct nodePosition));
292+
nodeF->box = root;
293+
nodeF->key = i;
294+
return nodeF;
295+
}
278296
else if (nodeF != NULL) return nodeF;
279297
else nodeF = searchNValue(value,root->keys[i]);
280298
}
@@ -289,6 +307,7 @@ struct nodePosition* searchNBox(struct node *toFind,struct node *root){
289307
else {
290308
for (i = 0; i < root->keyCount; i++){ // -1 since left and right key of every data box
291309
if (root == toFind) {
310+
nodeF = (struct nodePosition*)malloc(sizeof(struct nodePosition));
292311
nodeF->box = root;
293312
nodeF->key = i;
294313
return nodeF;
@@ -305,8 +324,8 @@ void inOrder(struct node *root){
305324
int i;
306325
if (root == NULL) return;
307326
else {
308-
// root = root->keys[2];
309-
for (i = 0; i < root->keyCount; i++){ // -1 since left and right key of every data box
327+
//root = root->keys[1]->keys[3];
328+
for (i = 0; i < root->keyCount + 2; i++){ // -1 since left and right key of every data box
310329
inOrder(root->keys[i]);
311330
if (i < root->keyCount - 1) printf("~%d~\n",root->value[i]);
312331
}
@@ -318,12 +337,12 @@ void levelOrder(struct node *root){
318337
if (root == NULL) return;
319338
else {
320339
for (i = 0; i < root->keyCount - 1; i++){ // -1 since left and right key of every data box
321-
printf("%d ",root->value[i]);
340+
printf("Node %d : %d ",i,root->value[i]);
322341
}
323342
printf(" ");
324343
if (root->parent == NULL) printf("\n");
325344
else {
326-
for (i = 0; i < root->parent->keyCount; i++){ // Check if had a right sibling, if none then proceed to next level
345+
for (i = 0; i < root->parent->keyCount + 2; i++){ // Check if had a right sibling, if none then proceed to next level
327346
if (root->parent->keys[i] == root){
328347
if (root->parent->keys[i+1] == NULL) printf("\n");
329348
break;
@@ -336,3 +355,26 @@ void levelOrder(struct node *root){
336355
}
337356
}
338357
}
358+
359+
void pushS(struct node *leftHalf, struct node *rightHalf){
360+
struct splitStack *newNode = (struct splitStack*)malloc(sizeof(struct splitStack));
361+
newNode->leftHalf = leftHalf;
362+
newNode->rightHalf = rightHalf;
363+
if (head == NULL){
364+
head = newNode;
365+
head->next = NULL;
366+
} else {
367+
newNode->next = head;
368+
head = newNode;
369+
}
370+
}
371+
372+
struct splitStack *popS(){
373+
if (head == NULL) {
374+
printf("Stack Underflow!!\n");
375+
getch();
376+
exit(-1);
377+
} else {
378+
379+
}
380+
}

‎btree.exe

1.55 KB
Binary file not shown.

0 commit comments

Comments
 (0)