B-Tree.h

#include "Linked-List-Int.h"
#include "Linked-List-Node.h"

// !! ORDER can only be an even number
#define ORDER 6 // max ORDER childs per node; max ORDER - 1 keys per node; min (ORDER - 1)/2 childs per node
#define MAX_KEYS (ORDER-1)
#define MIN_KEYS (MAX_KEYS/2)
#define MIN_CHILDS (MIN_KEYS+1)

#define TRUE 1
#define FALSE 0

// Constants that determines if further merging will be done in a valid tree to minimize number of nodes, at the expense of fuller nodes.
#define MINIMIZE_MIDDLE_NODES 1     // Minimize nodes in the middle of the tree (non-leaf nodes)
#define MINIMIZE_LEAF_NODES 0       // Minimize number of leaf nodes (not optimal as insertion is done at leaf)


struct Node
{
    int keysNr;
    ListNodeInt *keys;
    ListNodeNode *childs;
};

typedef struct Node Node;


/// @brief Traverses the tree in preorder and prints all values.
/// @param tree Pointer to the root of the tree.
void treeTraverse(Node* tree);

/// @brief Adds a value to the tree.
/// @param tree Pointer to the root of the tree.
/// @param value The value to be added.
/// @return The address of the root of the tree.
Node* treeAdd(Node* tree, int addValue);

/// @brief Splits the child tree root node into two nodes, pushing median value to root (parent) node.
/// @param parent Pointer to the parent (root) node of the child.
/// @param child Pointer to the full node of the tree.
/// @return The address of the root of the new subtree.
Node* treeSplit(Node* parent, Node* child);

/// @brief Rebalance tree after a key deletion from leaf.
/// @param tree Pointer to the root of the tree.
/// @param parent Pointer to the parent of current node (equal to root for external call).
/// @param removedValue The value that was removed from tree (used for establishind correct tree branches).
/// @return The address of the parent of the "tree" node.
Node* treeRemoveRebalanceLeaf(Node* tree, Node* parent, int removedValue);

/// @brief Rebalance tree after a key deletion from middle.
/// @param tree Pointer to the root of the tree.
/// @param parent Pointer to the parent of current node (equal to root for external call).
/// @param removedValue The value that was removed from tree (used for establishind correct tree branches).
/// @return The address of the parent of the "tree" node.
Node* treeRemoveRebalanceMiddle(Node* tree, Node* parent, int removedValue);

/// @brief Rebalance tree after last root key was deleted.
/// @param rootNode Pointer to the root of the tree.
/// @param removedValue The value that was removed from tree (used for establishind correct tree branches).
/// @return The address of the new root of the tree.
Node* treeRemoveRebalanceRoot(Node* rootNode, int removedValue);

/// @brief Key rotation (left) function used for rebalancing after deletion.
/// @param receiverSibling The sibling that will receive a key from the rotation.
/// @param parent The parent node of the two siblings.
/// @param donorSibling The sibling that will donate a key from the rotation.
/// @param parentSeparatorIndex The index of the key in the parent node that separates the two siblings.
/// @return The root node of the modified subtree (receiverSibling node).
Node* treeRemoveRebalanceRotateLeft(Node* receiverSibling, Node* parent, Node* donorSibling, int parentSeparatorIndex);

/// @brief Key rotation (right) function used for rebalancing after deletion.
/// @param receiverSibling The sibling that will receive a key from the rotation.
/// @param parent The parent node of the two siblings.
/// @param donorSibling The sibling that will donate a key from the rotation.
/// @param parentSeparatorIndex The index of the key in the parent node that separates the two siblings.
/// @return The root node of the modified subtree (receiverSibling node).
Node* treeRemoveRebalanceRotateRight(Node* receiverSibling, Node* parent, Node* donorSibling, int parentSeparatorIndex);

/// @brief Transfers key from a child to the parent node (receiverNode).
/// @param receiverNode The node that will receive the child's value.
/// @param child The child of receiverNode that will donate a value.
/// @param isRightChild Value that indicates whether child node is right child or not.
/// @return The root node of the modified subtree (receiverNode).
Node* treeRemoveRebalanceTransfer(Node* receiverNode, Node* child, int isRightChild);

/// @brief Merges two sibling nodes together.
/// @param receiverNode The node that will receive the other values (final node).
/// @param mergedNode The node that will be merged into receiverNode and will cease to exist.
/// @param parent The parent node of the two nodes.
/// @param isRightChild Value that indicates whether mergedNode is right child or not.
/// @return The address of the parent of receiverNode or NULL if parent was dealocated.
Node* treeRemoveRebalanceMerge(Node* receiverNode, Node* mergedNode, Node* parent, int isRightChild);

/// @brief Merges two sibling nodes and the parent seperator value together.
/// @param receiverNode The node that will receive the other values (final node).
/// @param mergedNode The node that will be merged into receiverNode and will cease to exist.
/// @param parent The parent node of the two nodes.
/// @param parentSeparatorIndex The index of the key in the parent node that separates the two siblings.
/// @return The address of the parent of receiverNode or NULL if parent was dealocated.
Node* treeRemoveRebalanceMergeParent(Node* receiverNode, Node* mergedNode, Node* parent, int parentSeparatorIndex);

/// @brief Removes a value from the tree.
/// @param tree Pointer to the root of the tree.
/// @param parent Pointer to the parent of "tree" node (equal to NULL if "tree" is root).
/// @param value The value to be removed from tree.
/// @return The address of the parent or NULL if "tree" is the root node.
Node* treeRemove(Node* tree, Node* parent, int value);

/// @brief Finds the node containing the given value, if it exists.
/// @param tree Pointer to the root of the tree.
/// @param value The value that is to be found.
/// @return The address of the node containing the given value, or NULL if it doesn't exist.
Node* treeFind(Node* tree, int value);