Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: coderaven/B-Tree
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: 9c7e226
Choose a base ref
...
head repository: coderaven/B-Tree
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 9919d4e
Choose a head ref
  • 9 commits
  • 2 files changed
  • 1 contributor

Commits on Sep 30, 2012

  1. Working on the insertion Bug

    Raven G. Duran committed Sep 30, 2012
    Copy the full SHA
    a28833f View commit details

  2. Minor update to printing

    Raven G. Duran committed Sep 30, 2012
    Copy the full SHA
    1f90180 View commit details

  3. Partially corrected insertion recurception problem

    Raven G. Duran committed Sep 30, 2012
    Copy the full SHA
    bc44b58 View commit details

  4. Updated Insertion Again

    Raven G. Duran committed Sep 30, 2012
    Copy the full SHA
    d36c118 View commit details

  5. Starting To Debug 3+ levels

    Raven G. Duran committed Sep 30, 2012
    Copy the full SHA
    20af300 View commit details

  6. Still on 3+ Levels

    Raven G. Duran committed Sep 30, 2012
    Copy the full SHA
    9b40bf8 View commit details

  7. Just a little more bugs for insertion

    Raven G. Duran committed Sep 30, 2012
    Copy the full SHA
    b84b724 View commit details

  8. Added SearchNValue and SearchNBox

    Raven G. Duran committed Sep 30, 2012
    Copy the full SHA
    ec4709c View commit details

Commits on Oct 1, 2012

  1. Partial Stack Implementation fro multiple splits

    Raven G. Duran committed Oct 1, 2012
    Copy the full SHA
    9919d4e View commit details
Showing with 145 additions and 24 deletions.
  1. +145 −24 btree.c
  2. BIN btree.exe
169 changes: 145 additions & 24 deletions btree.c
View file
Original file line number Diff line number Diff line change
@@ -10,6 +10,21 @@ struct node {
int keyCount;
} *tRoot = NULL;

struct nodePosition {
int key;
struct node* box;
};

// Left-right stack for multiple splitting
struct splitStack {
struct node *leftHalf;
struct node *rightHalf;
struct splitStack *next;
} *head = NULL;

void pushS(struct node *leftHalf, struct node *rightHalf);
struct splitStack *popS();

// Globals
int treeOrder;

@@ -23,6 +38,8 @@ void doInOrder();
// Tree Operations
struct node* newNode(int value,struct node *parent);
struct node* insertN(int value,struct node *root,struct node *parent);
struct nodePosition* searchNValue(int value,struct node *root);
struct nodePosition* searchNBox(struct node *toFind,struct node *root);

// Printing
void inOrder(struct node *root);
@@ -71,7 +88,7 @@ void doInsert(){
system("cls");
printf("--- Insertion ---\n");
printf("Value: ");
scanf("%d",&value);
scanf("%d",&value);

tRoot = insertN(value,tRoot,NULL);

@@ -94,6 +111,11 @@ void doSearch(){

system("cls");
printf("--- Search ---\n");
printf("To Find: ");
scanf("%d",&toFind);

if (searchNValue(toFind,tRoot) == NULL) printf("Not found!\n");
else printf("found!\n");

printf("\n\n\nPress any key to continue...\n");
getch();
@@ -106,7 +128,6 @@ void doInOrder(){
system("cls");
printf("--- Printing ---\n");

//for (i = 0; i < tRoot->keyCount - 1; i++) printf("%d ", tRoot->value[i]);
if (tRoot != NULL) inOrder(tRoot);
else printf("\nThe tree is empty!\n");

@@ -147,18 +168,23 @@ struct node* insertN(int value,struct node *root,struct node *parent){
printf("Data Already inserted!\n");
break;
} else if ( value > root->value[i] ){ // if value to be inserted is greater, then proceed to next box
if (root->keys[i+1] != NULL && root->keys[i+1]->keyCount < treeOrder + 1) {
if (root->keys[i+1] != NULL && root->keys[i+1]->keyCount < treeOrder + 1 && root->value[i+1] > value) {
PUT_RIGHT:
root->keys[i+1] = insertN(value,root->keys[i+1],root);
break;
} else i++;

continue;
} else { // This is if the value to be inserted is lesser which means, we can put it now
if (root->keys[i] != NULL && root->keys[i]->keyCount < treeOrder + 1) {
PUT_LEFT:
root->keys[i] = insertN(value,root->keys[i],root);
break;
} else {
for (j = treeOrder - 2; j >= i; j--) root->value[j+1] = root->value[j]; // move everything to the right
for (j = treeOrder - 2; j >= i; j--) {
root->value[j+1] = root->value[j]; // move everything to the right
root->keys[j+2] = root->keys[j+1];
}
root->value[i] = value;
root->keyCount++;

@@ -167,7 +193,12 @@ struct node* insertN(int value,struct node *root,struct node *parent){
}

}
} else { // else if the box is null. Insert directly
} else { // else if the box is null or the last box. Insert directly
if (root->keys[i] != NULL && root->keys[i]->keyCount < treeOrder + 1) {
printf("Succes!\n");
goto PUT_LEFT;
}

root->value[i] = value;
root->keyCount++;

@@ -189,46 +220,114 @@ struct node* insertN(int value,struct node *root,struct node *parent){

for (i = 0; i <= left; i++){ // Move all left half data to new LeftHalf Box
leftHalf = insertN(root->value[i],leftHalf,NULL); // Set the parent to NULL temporarily
}
leftHalf->keys[i] = root->keys[i];

if (root->keys[i] != NULL) root->keys[i]->parent = leftHalf;
} leftHalf->keys[left+1] = root->keys[left+1];
if (root->keys[treeOrder] != NULL) root->keys[treeOrder]->parent = leftHalf;

for (i = right; i < treeOrder; i++){ // Move all right half data to new LeftHalf Box
rightHalf = insertN(root->value[i],rightHalf,NULL); // pointer arithmethic
}
rightHalf = insertN(root->value[i],rightHalf,NULL);
rightHalf->keys[i] = root->keys[i];

if (root->keys[i] != NULL) root->keys[i]->parent = rightHalf;
} rightHalf->keys[treeOrder] = root->keys[treeOrder];
if (root->keys[treeOrder] != NULL) root->keys[treeOrder]->parent = rightHalf;

int pIsNull = parent == NULL ? 1 : 0;
struct node *tempRoot = root;
root = insertN(root->value[mid],parent,parent);
struct node *pParent = pIsNull ? NULL : parent->parent;

if (parent == NULL){ // Special case if splitted is the tRoot (The very Root)
leftHalf->parent = root;
rightHalf->parent = root;
root->keys[0] = leftHalf;
root->keys[1] = rightHalf;
parent = insertN(root->value[mid],parent,pParent);

if (pIsNull){ // Special case if splitted is the tRoot (The very Root)
leftHalf->parent = parent;
rightHalf->parent = parent;
parent->keys[0] = leftHalf;
parent->keys[1] = rightHalf;

//free(tempRoot); // Delete old root node box
return parent;
} else {
for (i = 0; i < tempRoot->parent->keyCount; i++){
if (tempRoot->parent->keys[i] == tempRoot){
tempRoot->parent->keys[i] = leftHalf;
tempRoot->parent->keys[i+1] = rightHalf;
// Find the parent of the current left and right box
int found = 0;
for (i = 0; i < parent->keyCount; i++){
if (parent->keys[i] != NULL && parent->keys[i] == tempRoot){
parent->keys[i] = leftHalf;
parent->keys[i+1] = rightHalf;

leftHalf->parent = parent;
rightHalf->parent = parent;
found = 1;
}
}


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

//free(tempRoot);
return leftHalf;
}

// To do : Non special case split and distribute... or if parent has a parent with values

free(tempRoot); // Delete old root node box
}
}

return root;
}

struct nodePosition* searchNValue(int value,struct node *root){
int i;
struct nodePosition *nodeF = NULL;
if (root == NULL) return NULL;
else {
for (i = 0; i < root->keyCount; i++){ // -1 since left and right key of every data box
if (root->value[i] == value) {
nodeF = (struct nodePosition*)malloc(sizeof(struct nodePosition));
nodeF->box = root;
nodeF->key = i;
return nodeF;
}
else if (nodeF != NULL) return nodeF;
else nodeF = searchNValue(value,root->keys[i]);
}
return nodeF;
}
}

struct nodePosition* searchNBox(struct node *toFind,struct node *root){
int i;
struct nodePosition *nodeF = NULL;
if (root == NULL) return NULL;
else {
for (i = 0; i < root->keyCount; i++){ // -1 since left and right key of every data box
if (root == toFind) {
nodeF = (struct nodePosition*)malloc(sizeof(struct nodePosition));
nodeF->box = root;
nodeF->key = i;
return nodeF;
}
else if (nodeF != NULL) return nodeF;
else nodeF = searchNBox(toFind,root->keys[i]);
}
return nodeF;
}
}

// Printing
void inOrder(struct node *root){
int i;
if (root == NULL) return;
else {
for (i = 0; i < root->keyCount - 1; i++){ // -1 since left and right key of every data box
//root = root->keys[1]->keys[3];
for (i = 0; i < root->keyCount + 2; i++){ // -1 since left and right key of every data box
inOrder(root->keys[i]);
printf("~%d~\n",root->value[i]);
if (i < root->keyCount - 1) printf("~%d~\n",root->value[i]);
}
}
}
@@ -238,12 +337,12 @@ void levelOrder(struct node *root){
if (root == NULL) return;
else {
for (i = 0; i < root->keyCount - 1; i++){ // -1 since left and right key of every data box
printf("%d ",root->value[i]);
printf("Node %d : %d ",i,root->value[i]);
}
printf(" ");
if (root->parent == NULL) printf("\n");
else {
for (i = 0; i < root->parent->keyCount; i++){ // Check if had a right sibling, if none then proceed to next level
for (i = 0; i < root->parent->keyCount + 2; i++){ // Check if had a right sibling, if none then proceed to next level
if (root->parent->keys[i] == root){
if (root->parent->keys[i+1] == NULL) printf("\n");
break;
@@ -257,3 +356,25 @@ void levelOrder(struct node *root){
}
}

void pushS(struct node *leftHalf, struct node *rightHalf){
struct splitStack *newNode = (struct splitStack*)malloc(sizeof(struct splitStack));
newNode->leftHalf = leftHalf;
newNode->rightHalf = rightHalf;
if (head == NULL){
head = newNode;
head->next = NULL;
} else {
newNode->next = head;
head = newNode;
}
}

struct splitStack *popS(){
if (head == NULL) {
printf("Stack Underflow!!\n");
getch();
exit(-1);
} else {

}
}
Binary file modified btree.exe
View file
Binary file not shown.