Lec 2: Red-Black Trees and B+ Trees⚓︎

Btree Insert(ElementType X, Btree T) {
    Search from root to leaves for X and find the the proper leaf node;
    Insert X;
    while (this node has M+1 keys) {
        split it into 2 nodes with RoundUp((M+1) / 2) and RoundDown((M+1) / 2) keys respectively;
        if (this node is the root)
            create a new root with two children;
        check its parent;
    } 
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ORDER 3
#define LEAFCUT (ORDER / 2 + 1)
#define NONLEAFCUT (ORDER / 2)
#define SIZE 20000

typedef struct node * Node;
typedef struct node * BplusTree;

struct node {
    int size;
    int childrenSize;
    int data[ORDER + 1];
    Node children[ORDER + 1];
    Node parent;
};

typedef struct queue * Queue;

struct queue {
    int size;
    int front;
    int rear;
    Node data[SIZE];
};


BplusTree Create();
Node Find(int x, BplusTree T, bool * flag);
void Insert(int x, Node node);
void Split(Node node);
void PrintTree(BplusTree T);

Queue CreateQueue();
void Enqueue(Node node, Queue Q);
Node Dequeue(Queue Q);

int cmp(const void * a, const void * b);
int cmpNode(const void * a, const void * b);

BplusTree Tree;

int main() {
    int n;
    int x;
    int i, j, k;
    bool isDuplicated = false;

    Node tmp;
    Tree = Create();

    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        isDuplicated = false;

        scanf("%d", &x);

        tmp = Find(x, Tree, &isDuplicated);
        if (isDuplicated) {
            printf("Key %d is duplicated\n", x);
        } else {
            Insert(x, tmp);
        }
    }

    PrintTree(Tree);

    return 0;
}

BplusTree Create() {
    BplusTree T = (BplusTree)malloc(sizeof(struct node));
    if (T == NULL) {
        printf("Failed to create a B+ Tree!\n");
        return T;
    }

    int i;
    // T->data = (int *)malloc(sizeof(int) * (ORDER + 1));
    for (i = 0; i <= ORDER; i++) {
        T->children[i] = (Node)malloc(sizeof(struct node));
    }

    T->size = 0;
    T->childrenSize = 0;
    T->parent = NULL;

    return T;
}

Node Find(int x, BplusTree T, bool * flag) {
    int i;

    if (!T) {
        return T;
    } else if (!T->childrenSize) {
        if (T->size) {
            for (i = 0; i < T->size; i++) {
                if (x == T->data[i]) {
                    *flag = true;
                    break;
                }
            }
        }
        return T;
    }


    int pos = -1;

    for (i = 0; i < T->size; i++) {
        if (x < T->data[i]) {
            pos = i;
            break;
        }
    }
    if (pos == -1) {
        pos = i;
    }

    return Find(x, T->children[pos], flag);
}

void Insert(int x, Node node) {
    int i;

    node->data[node->size++] = x;
    qsort(node->data, node->size, sizeof(int), cmp);

    Split(node);
}

void Split(Node node) {
    if (!node->childrenSize && node->size <= ORDER 
    || node->childrenSize && node->size < ORDER) {
        return;
    }

    Node lnode, rnode, tmpNode;
    int cut;
    int i, j;

    if (!node->parent) {
        tmpNode = Create();
        node->parent = (Node)malloc(sizeof(struct node));
        Tree = node->parent = tmpNode;
    }

    lnode = Create();
    rnode = Create();
    lnode->parent = rnode->parent = node->parent;

    if (!node->childrenSize) {
        cut = LEAFCUT;

        for (i = 0; i < cut; i++) {
            lnode->data[i] = node->data[i];
        }
        lnode->size = cut;

        for (j = cut; j < node->size; j++) {
            rnode->data[j - cut] = node->data[j];
        }
        rnode->size = node->size - cut;

    } else {
        cut = NONLEAFCUT;

        for (i = 0; i <= cut; i++) {
            if (i != cut) 
                lnode->data[i] = node->data[i];
            lnode->children[i] = node->children[i];
            lnode->children[i]->parent = lnode;
        }
        lnode->size = cut;
        lnode->childrenSize = cut + 1;

        for (j = cut + 1; j < node->size; j++) {
            rnode->data[j - cut - 1] = node->data[j];
        }
        for (j = cut + 1; j < node->childrenSize; j++) {
            rnode->children[j - cut - 1] = node->children[j];
            rnode->children[j - cut - 1]->parent = rnode;
        }     
        rnode->size = node->size - cut - 1;
        rnode->childrenSize = node->childrenSize - cut - 1;
    }

    node->parent->data[node->parent->size++] = node->data[cut];
    if (node->parent->childrenSize) {
        for (i = 0; i < node->parent->childrenSize; i++) {
            if (node->parent->children[i] == node) {
                node->parent->children[i] = lnode;
                break;
            }
        }
    } else {
        node->parent->children[node->parent->childrenSize++] = lnode;
    }
    node->parent->children[node->parent->childrenSize++] = rnode;

    qsort(node->parent->data, node->parent->size, sizeof(node->parent->data[0]), cmp);
    qsort(node->parent->children, node->parent->childrenSize, sizeof(node->parent->children[0]), cmpNode);

    free(node);

    Split(node->parent);
}

void PrintTree(BplusTree T) {
    int i;
    int flag;
    Node node;
    Queue q;

    q = CreateQueue();
    Enqueue(T, q);
    Enqueue(NULL, q);

    while (q->size) {
        node = Dequeue(q);
        if (!node) {
            printf("\n");
            if (q->size) {
                Enqueue(NULL, q);
            }
        } else {
            printf("[");
            for (i = 0; i < node->size; i++) {
                if (!i) {
                    printf("%d", node->data[i]);
                } else {
                    printf(",%d", node->data[i]);
                }
            }
            printf("]");
        }

        if (node) {
            for (i = 0; i < node->childrenSize; i++) {
                Enqueue(node->children[i], q);
            }
        }

    }

}

Queue CreateQueue() {
    Queue Q = (Queue)malloc(sizeof(struct queue));
    Q->size = 0;
    Q->front = Q->rear = 0;

    return Q;
}

void Enqueue(Node node, Queue Q) {
    Q->data[Q->rear++] = node;
    Q->size++;
}

Node Dequeue(Queue Q) {
    Node returnNode = Q->data[Q->front++];
    Q->size--;
    return returnNode;
}

int cmp(const void * a, const void * b) {
    return *(int *)a - *(int *)b ;
}

int cmpNode(const void * a, const void * b) {
    const Node nodeA = *(const Node*)a;
    const Node nodeB = *(const Node*)b;

    return nodeA->data[0] - nodeB->data[0];
}