B-Tree.c

#include "B-Tree.h"
#include <stdlib.h>
#include <stdio.h>


void treeTraverse(Node* tree)
{
    int i;
    Node* node;
    ListNodeNode* childListNode;

    if(tree == NULL) return;

    // Print keys
    listIntPrint(tree->keys);
    printf("\n");

    // Traverse sub-trees
    i = 0;
    while(1)
    {
        childListNode = getIndexNodeNode(tree->childs, i);
        if(childListNode == NULL) break;

        node = childListNode->address;
        treeTraverse(node);

        printf("----------\n");

        i++;
    }
}

Node* treeAdd(Node* tree, int addValue)
{
    Node *currentNode, *nextNode, *newNode, *result;
    int medianIndex, addValueIndex;
    int subTreeIndex;
    Node *subTreeNode, *splitTreeNode;

    // If tree is empty
    if(tree == NULL)
    {
        newNode = (Node*)malloc(sizeof(Node));
        newNode->childs = NULL;
        newNode->keys = NULL;
        newNode->keysNr = 0;

        newNode->keys = listIntAddSorted(newNode->keys, addValue);
        newNode->keysNr += 1;

        return newNode;
    }

    // If root is full
    if(tree->keysNr == MAX_KEYS)
    {
        newNode = (Node*)malloc(sizeof(Node));
        newNode->childs = NULL;
        newNode->keys = NULL;
        newNode->keysNr = 0;

        newNode->childs = listNodeAdd(newNode->childs, tree);

        tree = treeSplit(newNode, tree);
    }

    // Traverse tree
    currentNode = tree;
    while (currentNode->childs != NULL) // While currentNode is not leaf
    {
        subTreeIndex = getSortedIndexOfValue(currentNode->keys, addValue);
        subTreeNode = getIndexNodeNode(currentNode->childs, subTreeIndex)->address;

        // if subtree root is full
        if(subTreeNode->keysNr == MAX_KEYS)
        {
            splitTreeNode = treeSplit(currentNode, subTreeNode);
            currentNode = splitTreeNode;
        }
        else
            currentNode = subTreeNode;
    }

    // Insert at leaf
    currentNode->keys = listIntAddSorted(currentNode->keys, addValue);
    currentNode->keysNr += 1;

    return tree;
}

Node* treeSplit(Node* parent, Node* child)
{
    int transferKey, i;
    Node* newChild;

    // Init newChild
    newChild = (Node*)malloc(sizeof(Node));
    newChild->childs = NULL;
    newChild->keys = NULL;
    newChild->keysNr = 0;

    // Get median key from child
    transferKey = getIndexIntNode(child->keys, MAX_KEYS / 2)->value;
    listIntRemove(child->keys, transferKey);
    child->keysNr -= 1;

    // Copy first half of child content to newChild & delete it from child
    for(i = 0; i < MAX_KEYS / 2; i++)
    {
        // If child node is not leaf
        if(child->childs != NULL)
        {
            // Add node i of childs to newChild & remove it from child
            newChild->childs = listNodeAdd(newChild->childs, child->childs->address);
            child->childs = listNodeRemove(child->childs, child->childs->address);
        }

        // Add node i of keys to newChild & remove it from child
        newChild->keys = listIntAddSorted(newChild->keys, child->keys->value);
        newChild->keysNr += 1;
        child->keys = listIntRemove(child->keys, child->keys->value);
        child->keysNr -= 1;
    }
    // For x keys there are (x + 1) child nodes
    // so also add the (x + 1) child to newNode
    if(child->childs != NULL)
    {
        // Add node i of childs to newChild & remove it from child
        newChild->childs = listNodeAdd(newChild->childs, child->childs->address);
        child->childs = listNodeRemove(child->childs, child->childs->address);
    }

    // Add transferKey to parent
    parent->keys = listIntAddSorted(parent->keys, transferKey);
    parent->keysNr += 1;

    // Add newChild to parent childs
    int index = getSortedIndexOfValue(parent->keys, transferKey);
    // here add newChild in parent->childs at index (and child should be at (index + 1))
    parent->childs = listNodeAddAtIndex(parent->childs, newChild, index);

    return parent;
}

Node* treeRemoveRebalanceLeaf(Node* tree, Node* parent, int removedValue)
{
    Node* currentNode;
    Node *leftSibling, *rightSibling;
    ListNodeNode *leftSiblingNode, *rightSiblingNode;
    ListNodeInt* updateStatus;
    int parentSeparatorIndex;
    int siblingKey, parentKey;

    if(tree == NULL || parent == NULL) return NULL;

    currentNode = tree;

    // Get separator from parent
    parentSeparatorIndex = getSortedIndexOfValue(parent->keys, removedValue);
    leftSiblingNode = getIndexNodeNode(parent->childs, parentSeparatorIndex - 1);
    rightSiblingNode = getIndexNodeNode(parent->childs, parentSeparatorIndex + 1);

    // Check if child nodes are not NULL to prevent Segfault.
    leftSibling = (leftSiblingNode != NULL) ? leftSiblingNode->address : NULL;
    rightSibling = (rightSiblingNode != NULL) ? rightSiblingNode->address : NULL;

    if(currentNode->keysNr < MIN_KEYS)
    {
        // If a sibling exists AND can be used for [Case 1B-1] (simple value exchange with sibling and parent)
        if((leftSibling && leftSibling->keysNr > MIN_KEYS) || (rightSibling && rightSibling->keysNr > MIN_KEYS))
        {
            // If leftSibling exists => rotate right
            if(leftSibling && leftSibling->keysNr > MIN_KEYS)
            {
                // Rotate right
                treeRemoveRebalanceRotateRight(currentNode, parent, leftSibling, parentSeparatorIndex);
            }
            // Else if rightSibling exists (backup) => rotate left
            else if(rightSibling && rightSibling->keysNr > MIN_KEYS)
            {
                // Rotate left
                treeRemoveRebalanceRotateLeft(currentNode, parent, rightSibling, parentSeparatorIndex);
            }
        }
        else // Else: Case 1B-2 --> Both siblings are at minimum number of keys => merge current node with one of the siblings & the parent separator value.
        {
            // If leftSibling exists (preferred)
            if(leftSibling)
            {
                // Merge with leftSibling
                parent = treeRemoveRebalanceMergeParent(currentNode, leftSibling, parent, parentSeparatorIndex);
            }
            // Else if rightSibling exists
            else if(rightSibling)
            {
                // Merge with rightSibling
                parent = treeRemoveRebalanceMergeParent(currentNode, rightSibling, parent, parentSeparatorIndex);
            }
        }
    }
    else    // Tree is valid, but if current node can be merged with sibling, do this to reduce the expanse of tree
    {
        // If option to minimize leaf nodes is enabled
        if(MINIMIZE_LEAF_NODES == TRUE && currentNode->keysNr == MIN_KEYS)
        {
            if(leftSibling)
            {
                parent = treeRemoveRebalanceMergeParent(currentNode, leftSibling, parent, parentSeparatorIndex);
            }
            else if(rightSibling)
            {
                parent = treeRemoveRebalanceMergeParent(currentNode, rightSibling, parent, parentSeparatorIndex);
            }
        }
    }

    return parent;
}

Node* treeRemoveRebalanceMiddle(Node* tree, Node* parent, int removedValue)
{
    Node* currentNode;
    Node *leftChild, *rightChild;
    Node *leftSibling, *rightSibling;
    Node *siblingChild;
    ListNodeNode *leftChildNode, *rightChildNode;
    ListNodeNode *leftSiblingNode, *rightSiblingNode;
    ListNodeInt* updateStatus;
    int currentSeparatorIndex, parentSeparatorIndex;
    int childKey, currentKey, parentKey, siblingKey;

    if(tree == NULL) return parent;

    currentNode = tree;

    // If node is leaf
    if(currentNode->childs == NULL)
    {
        parent = treeRemoveRebalanceLeaf(currentNode, parent, removedValue);
    }
    else // If childs exist (not leaf)
    {
        // Get separator from currentNode & the coresponding child nodes
        currentSeparatorIndex = getSortedIndexOfValue(currentNode->keys, removedValue);
        leftChildNode = getIndexNodeNode(currentNode->childs, currentSeparatorIndex);
        rightChildNode = getIndexNodeNode(currentNode->childs, currentSeparatorIndex + 1);

        // Check if child nodes are not NULL to prevent Segfault
        leftChild = (leftChildNode != NULL) ? leftChildNode->address : NULL;
        rightChild = (rightChildNode != NULL) ? rightChildNode->address : NULL;

        // Check if node count is in sync with number of keys
        if(getNodeCount(currentNode->childs) == currentNode->keysNr + 1) // Node count is in sync with number of keys => could merge current node with sibling
        {
            // Get separator from parentNode & the coresponding sibling nodes
            parentSeparatorIndex = getSortedIndexOfValue(parent->keys, removedValue);
            leftSiblingNode = getIndexNodeNode(parent->childs, parentSeparatorIndex - 1);
            rightSiblingNode = getIndexNodeNode(parent->childs, parentSeparatorIndex + 1);

            // Check if sibling nodes are not NULL to prevent Segfault.
            leftSibling = (leftSiblingNode != NULL) ? leftSiblingNode->address : NULL;
            rightSibling = (rightSiblingNode != NULL) ? rightSiblingNode->address : NULL;

            if(currentNode->keysNr < MIN_KEYS) // Not enought keys in currentNode => must do something (merge or rotation)
            {
                // Try key rotation with parent & sibling
                if(leftSibling && leftSibling->keysNr > MIN_KEYS)
                {
                    // Get key that will be removed from donor sibling node (last value for left sibling)
                    siblingKey = getLastIntNode(leftSibling->keys)->value;

                    // Roate right
                    currentNode = treeRemoveRebalanceRotateRight(currentNode, parent, leftSibling, parentSeparatorIndex);

                    // Ensure leftSibling subtree is balanced and valid
                    currentNode = treeRemoveRebalanceMiddle(leftSibling, currentNode, siblingKey);
                }
                else if(rightSibling && rightSibling->keysNr > MIN_KEYS)
                {
                    // Get key that will be removed from donor sibling node (first value for right sibling)
                    siblingKey = rightSibling->keys->value;

                    // Rotate left
                    currentNode = treeRemoveRebalanceRotateLeft(currentNode, parent, rightSibling, parentSeparatorIndex);

                    // Ensure rightSibling subtree is balanced and valid
                    currentNode = treeRemoveRebalanceMiddle(rightSibling, currentNode, siblingKey);
                }
                else // Siblings don't allow rotation => merge current node with sibling & parent separator value
                {
                    if(leftSibling)
                    {
                        parent = treeRemoveRebalanceMergeParent(currentNode, leftSibling, parent, parentSeparatorIndex);
                    }
                    else if(rightSibling)
                    {
                        parent = treeRemoveRebalanceMergeParent(currentNode, rightSibling, parent, parentSeparatorIndex);
                    }
                }
            }
            else    // Tree is valid, but if current node can be merged with sibling, do this to reduce the expanse of tree
            {
                if(MINIMIZE_MIDDLE_NODES == TRUE && currentNode->keysNr == MIN_KEYS)
                {
                    if(leftSibling && leftSibling->keysNr == MIN_KEYS)
                    {
                        parent = treeRemoveRebalanceMergeParent(currentNode, leftSibling, parent, parentSeparatorIndex);
                    }
                    else if(rightSibling && rightSibling->keysNr == MIN_KEYS)
                    {
                        parent = treeRemoveRebalanceMergeParent(currentNode, rightSibling, parent, parentSeparatorIndex);
                    }
                }
            }
        }
        // Else must obtain a value from child to respect condition : (childs = keys + 1)
        else
        {
            if(leftChild != NULL && leftChild->keysNr > MIN_KEYS) // Transfer from left child
            {
                currentNode = treeRemoveRebalanceTransfer(currentNode, leftChild, FALSE);
            }
            else if(rightChild != NULL && rightChild->keysNr > MIN_KEYS) // Transfer from right child
            {
                currentNode = treeRemoveRebalanceTransfer(currentNode, rightChild, TRUE);
            }
            else // Merge the left and right children into one node
            {
                currentNode = treeRemoveRebalanceMerge(leftChild, rightChild, currentNode, TRUE);
            }
        }
    }

    return parent;
}

Node* treeRemoveRebalanceRoot(Node* rootNode, int removedValue)
{
    Node* newRoot;
    Node *leftChild, *rightChild;

    leftChild = getIndexNodeNode(rootNode->childs, 0)->address;
    rightChild = getIndexNodeNode(rootNode->childs, 1)->address;

    // Merge the two childs
    treeRemoveRebalanceMerge(leftChild, rightChild, rootNode, TRUE);

    // leftChild becomes the new root node
    newRoot = leftChild;

    // Make sure root node is respecting conditions
    treeRemoveRebalanceMiddle(newRoot, NULL, removedValue);

    return newRoot;
}

Node* treeRemoveRebalanceRotateLeft(Node* receiverSibling, Node* parent, Node* donorSibling, int parentSeparatorIndex)
{
    ListNodeInt* updateStatus;
    Node* siblingChild;
    int siblingKey, parentKey;

    // Get key from parent (right of separator value's index)
    parentKey = getIndexIntNode(parent->keys, parentSeparatorIndex)->value;

    // Get first (smallest) value from the donor sibling (right sibling)
    siblingKey = donorSibling->keys->value;

    // Remove first value from right sibling
    donorSibling->keys = listIntRemove(donorSibling->keys, siblingKey);
    donorSibling->keysNr -= 1;

    // Update value in parent node with siblingKey
    updateStatus = listIntUpdate(parent->keys, parentSeparatorIndex, parentKey, siblingKey);
    if(updateStatus == NULL)
    {
        printf("\nParent value update error");
    }

    // Add key from parent to current node
    receiverSibling->keys = listIntAddSorted(receiverSibling->keys, parentKey);
    receiverSibling->keysNr += 1;

    // If siblings are middle nodes => must also transfer a child
    if(receiverSibling->childs != NULL)
    {
        // Get first child of donorSibling
        siblingChild = donorSibling->childs->address;

        // Remove first child from donorSibling
        donorSibling->childs = listNodeRemove(donorSibling->childs, siblingChild);

        // Add siblingChild to receiverSibling childs
        receiverSibling->childs = listNodeAdd(receiverSibling->childs, siblingChild);
    }

    return receiverSibling;
}

Node* treeRemoveRebalanceRotateRight(Node* receiverSibling, Node* parent, Node* donorSibling, int parentSeparatorIndex)
{
    ListNodeInt* updateStatus;
    Node* siblingChild;
    int siblingKey, parentKey;

    // Get key from parent (left of subtree index)
    parentKey = getIndexIntNode(parent->keys, parentSeparatorIndex - 1)->value;

    // Get last (biggest) value from left sibling
    siblingKey = getLastIntNode(donorSibling->keys)->value;

    // Remove last value from left sibling
    donorSibling->keys = listIntRemove(donorSibling->keys, siblingKey);
    donorSibling->keysNr -= 1;

    // Update value in parent node with siblingKey
    updateStatus = listIntUpdate(parent->keys, parentSeparatorIndex - 1, parentKey, siblingKey);
    if(updateStatus == NULL)
    {
        printf("\nParent value update error");
    }

    // Add key from parent to current node
    receiverSibling->keys = listIntAddSorted(receiverSibling->keys, parentKey);
    receiverSibling->keysNr += 1;

    // If siblings are middle nodes => must also transfer a child
    if(receiverSibling->childs != NULL)
    {
        // Get last child of donorSibling
        siblingChild = getLastNodeNode(donorSibling->childs)->address;

        // Remove last child from donorSibling
        donorSibling->childs = listNodeRemove(donorSibling->childs, siblingChild);

        // Add siblingChild to receiverSibling childs
        receiverSibling->childs = listNodeAddBeginning(receiverSibling->childs, siblingChild);
    }

    return receiverSibling;
}

Node* treeRemoveRebalanceTransfer(Node* receiverNode, Node* child, int isRightChild)
{
    int childKey;

    if(isRightChild)
    {
        // Get first (smallest) value from right child
        childKey = child->keys->value;
    }
    else
    {
        // Get last (biggest) value from left child
        childKey = getLastIntNode(child->keys)->value;
    }

    // Remove childKey from child
    child->keys = listIntRemove(child->keys, childKey);
    child->keysNr -= 1;

    // Add childKey to currentNode
    receiverNode->keys = listIntAddSorted(receiverNode->keys, childKey);
    receiverNode->keysNr += 1;

    return receiverNode;
}

Node* treeRemoveRebalanceMerge(Node* receiverNode, Node* mergedNode, Node* parent, int isRightChild)
{
    Node* siblingChild;
    int siblingKey;

    // Get values from mergedNode
    while(mergedNode->keysNr > 0)
    {
        siblingKey = mergedNode->keys->value;

        receiverNode->keys = listIntAddSorted(receiverNode->keys, siblingKey);
        receiverNode->keysNr += 1;

        mergedNode->keys = listIntRemove(mergedNode->keys, siblingKey);
        mergedNode->keysNr -= 1;
    }

    // Get childs from sibling (mergedNode) (IF THEY EXIST)
    while(mergedNode->childs)
    {
        siblingChild = mergedNode->childs->address;

        if(isRightChild)
        {
            // Add children at the end of the list.
            receiverNode->childs = listNodeAdd(receiverNode->childs, siblingChild);
        }
        else
        {
            // Add children at beginning of list.
            receiverNode->childs = listNodeAddBeginning(receiverNode->childs, siblingChild);
        }

        mergedNode->childs = listNodeRemove(mergedNode->childs, siblingChild);
    }

    if(parent->keysNr + 1 < MIN_KEYS && parent->keysNr + 1 == 1) // parent is empty root => create new root from merged nodes
    {
        // Free memory of parent (root)
        free(parent);

        // receiverNode becomes root
        parent = NULL;
    }
    else
    {
        // Remove mergedNode from parent node childs list
        parent->childs = listNodeRemove(parent->childs, mergedNode);
    }

    // Free memory of mergedNode
    free(mergedNode);

    return parent;
}

Node* treeRemoveRebalanceMergeParent(Node* receiverNode, Node* mergedNode, Node* parent, int parentSeparatorIndex)
{
    Node* siblingChild;
    int siblingKey, parentKey;
    int mergedNodeMaxKey;
    int isRightSibling;

    // Get max value from mergedNode
    mergedNodeMaxKey = getLastIntNode(mergedNode->keys)->value;

    // If max value from mergedNode is smaller that the first value from currentNode (receiverNode) => merged node is left sibling
    if(mergedNodeMaxKey < receiverNode->keys->value)
    {
        // Get correct key from parent (for left sibling)
        parentKey = getIndexIntNode(parent->keys, parentSeparatorIndex - 1)->value;
        isRightSibling = 0;
    }
    else // => merged node is right sibling
    {
        // Get correct key from parent (for right sibling)
        parentKey = getIndexIntNode(parent->keys, parentSeparatorIndex)->value;
        isRightSibling = 1;
    }

    // Get values from mergedNode
    while(mergedNode->keysNr > 0)
    {
        siblingKey = mergedNode->keys->value;

        receiverNode->keys = listIntAddSorted(receiverNode->keys, siblingKey);
        receiverNode->keysNr += 1;

        mergedNode->keys = listIntRemove(mergedNode->keys, siblingKey);
        mergedNode->keysNr -= 1;
    }

    // Get childs from sibling (mergedNode) (IF THEY EXIST)
    while(mergedNode->childs)
    {
        if(isRightSibling)
        {
            // Get first child
            siblingChild = mergedNode->childs->address;

            // Add children at the end of the list.
            receiverNode->childs = listNodeAdd(receiverNode->childs, siblingChild);
        }
        else
        {
            // Get last child
            siblingChild = getLastNodeNode(mergedNode->childs)->address;

            // Add children at beginning of list.
            receiverNode->childs = listNodeAddBeginning(receiverNode->childs, siblingChild);
        }

        mergedNode->childs = listNodeRemove(mergedNode->childs, siblingChild);
    }

    // Remove parentKey separator value from parent node
    parent->keys = listIntRemove(parent->keys, parentKey);
    parent->keysNr -= 1;

    if(parent->keysNr + 1 < MIN_KEYS && parent->keysNr + 1 == 1) // parent is root and with a single key => create new root from merged nodes
    {
        // Free memory of parent (root)
        free(parent);

        // receiverNode becomes root
        parent = NULL;
    }
    else
    {
        // Remove mergedNode from parent node childs list
        parent->childs = listNodeRemove(parent->childs, mergedNode);
    }

    // Add parentKey separator to receiverNode
    receiverNode->keys = listIntAddSorted(receiverNode->keys, parentKey);
    receiverNode->keysNr += 1;

    // Free memory of mergedNode
    free(mergedNode);

    return parent;
}

// Remove cases
// Case 1: Remove from leaf
//      Case 1A: Remove from leaf without rebalancing required
//      Case 1B: Remove from leaf with rebalancing
//              Case 1B-1: Rebalance by values rotation
//              Case 1B-2: Rebalance by merging
// Case 2: Remove from middle (always required rebalancing)
//      Case 2A: Children count is synced with number of keys
//              Case 2A-1: Rebalance by values rotation
//              Case 2A-2: Rebalance by merging
//      Case 2B: Children count is NOT synced with number of keys => Transfer key from child to current node
// Case 3: Remove all nodes from root => Create new root from merged children
Node* treeRemove(Node* tree, Node* parent, int value)
{
    Node* currentNode, *childNode;
    ListNodeInt* valueNode;
    int currentSeparatorIndex;

    if(tree == NULL) return NULL;

    currentNode = tree;

    // Search for value in current tree node
    valueNode = listIntFind(currentNode->keys, value);
    if(valueNode != NULL) // value found
    {
        // Check if currentNode is leaf node
        if(currentNode->childs == NULL) // is leaf
        {
            // Remove key and decrement counter [Case 1A]
            currentNode->keys = listIntRemove(currentNode->keys, value);
            currentNode->keysNr -= 1;

            if(currentNode->keysNr < MIN_KEYS) // Requires rebalancing [Case 1B]
            {
                parent = treeRemoveRebalanceLeaf(currentNode, parent, value);
            }
        }
        else // is NOT leaf => requires rebalancing
        {
            // Remove key and decrement counter
            currentNode->keys = listIntRemove(currentNode->keys, value);
            currentNode->keysNr -= 1;

            // If currentNode is root && is empty => remove root node [Case 3]
            if(parent == NULL && currentNode->keysNr == 0)
            {
                currentNode = treeRemoveRebalanceRoot(currentNode, value);
            }
            else // [Case 2]
            {
                parent = treeRemoveRebalanceMiddle(currentNode, parent, value);
            }
        }
    }
    else
    {
        // Search for value in appropriate subtree
        currentSeparatorIndex = getSortedIndexOfValue(currentNode->keys, value);
        childNode = getIndexNodeNode(currentNode->childs, currentSeparatorIndex)->address;
        currentNode = treeRemove(childNode, currentNode, value);
    }

    // Rebalance tree when ascending from recursive call if not root node (root node can have fewer that MIN_KEYS values).
    if(currentNode->keysNr <= MIN_KEYS && parent != NULL)
        parent = treeRemoveRebalanceMiddle(currentNode, parent, value);

    
    if(parent == NULL) return currentNode;
    return parent;
}

Node* treeFind(Node* tree, int value)
{
    Node* currentNode;
    ListNodeInt* valueNode;
    int valueSortedIndex;

    if(tree == NULL) return NULL;

    currentNode = tree;

    // Search for value in current tree node
    valueNode = listIntFind(currentNode->keys, value);
    if(valueNode != NULL) return currentNode;

    // Search for value in appropriate subtree
    valueSortedIndex = getSortedIndexOfValue(currentNode->keys, value);
    return treeFind(getIndexNodeNode(currentNode->childs, valueSortedIndex)->address, value);
}