B+树

#include <cstddef>
#include <vector>
#include <deque>
#include<iostream>
#include<queue>
#include <sys/types.h>

using namespace std;
int MAX = 3;
// num_key [MAX / 2] - [MAX - 1]
class Node{
public:
    bool IS_LEAF;
    int *key;
    Node **pointer;
    int size;
    Node():key(new int[MAX]),pointer(new Node*[MAX + 1]),size(0){}
    friend class BPTree;
};

class BPTree{
public:
    Node *root;
    deque<Node*> parent;
    BPTree():root(nullptr){};
    int find(int);
    vector<int> find_range(int,int);
    Node* get_leaf_node(int);
    Node* copy_node(Node*);
    int get_pos(Node *node,Node*);
    void display();
    void insert(int key);
    void insert_in_leaf(int key,Node *);
    void insert_internal(Node*,int,Node *);
    void insert_in_parent(Node*,int key,Node*);
    void Delete(int);
    void delete_internal(int,Node*,Node*);
    void Mergeleaf(Node*,Node*);
    void Mergeinternal(Node*,int,Node*);
    void RedistributeFromLeft(Node*,Node*,Node*,int);
    void RedistributeFromRight(Node*,Node*,Node*,int);
    void RedistributeFromLeftinternal(Node*,Node*,Node*,int);
    void RedistributeFromRightinternal(Node*,Node*,Node*,int);
};

void BPTree::insert_internal(Node *node, int key, Node *Rpointer){
    int pos = 0;
    while(pos < node->size && node->key[pos] <= key) pos += 1; 
    node->pointer[node->size + 1] = node->pointer[node->size];
    for(int i = node->size - 1; i >= pos; i--) {
        node->key[i + 1] = node->key[i]; 
        node->pointer[i + 1] = node->pointer[i];
    }//向后移动一位
    node->key[pos] = key;
    node->pointer[pos + 1] = Rpointer;
    node->size += 1;
}

Node *BPTree::get_leaf_node(int key){
    Node* node = root;
    while (!node->IS_LEAF) {
        int pos = 0;
        while (pos < node->size && node->key[pos] <= key) pos += 1;
        node = node->pointer[pos];
    }
    return node;
}

int BPTree::find(int key){
    Node* node = get_leaf_node(key);
    for(int i = 0;i < node->size && node->key[i] <= key; i++){
        if(node->key[i] == key)  return key;
    }
    return -1;
}

vector<int> BPTree::find_range(int a,int b){
    vector<int> result;
    Node *node = get_leaf_node(a);
    int pos = 0;
    while(pos < node->size && node->key[pos] < a) pos += 1;
    bool done = false;
    while(!done){
        int n = node->size;
        if(pos < n && node->key[pos] <= b) { result.push_back(node->key[pos]); pos += 1;}
        else if(pos < n && node->key[pos] > b) done = true;
        else if(pos >= n && node->pointer[MAX-1] != nullptr) {node = node->pointer[MAX-1]; pos = 0;}
        else done = true;
    }
    return result;
}

void BPTree::insert_in_leaf(int key, Node *node){
    int pos = 0;
    while(pos < node->size && node->key[pos] <= key) pos += 1; //找到插入的位置
    if(node->key[pos] == key) return ;
    for(int i = node->size - 1; i >= pos; i--) {
        node->key[i + 1] = node->key[i]; 
    }//向后移动一位
    node->key[pos] = key;
    node->size += 1;
}

void BPTree::insert_in_parent(Node *node, int key, Node *node1){
    if(node == root){
        Node *new_root = new Node();
        new_root->key[0] = key;
        new_root->pointer[0] = node;
        new_root->pointer[1] = node1;
        new_root->IS_LEAF = false;
        new_root->size = 1;
        root = new_root;
        return ;
    }
    Node *p =parent.back();
    parent.pop_back();
    if(p->size < MAX - 1){
        insert_internal(p,key,node1);
    }else{
        Node *temp = copy_node(p);
        insert_internal(temp,key,node1);
        for(int i = 0; i < p->size; i++){ p->key[i] = 0;p->pointer[i] = nullptr;}
        p->pointer[p->size] = nullptr;
        Node *p1 = new Node();
        p1->IS_LEAF = false;
        p->size = MAX / 2;
        p1->size = MAX - (MAX / 2 + 1);
        for(int i = 0; i < p->size; i++){
            p->key[i] = temp->key[i];
            p->pointer[i] = temp->pointer[i];
        }
        p->pointer[p->size] = temp->pointer[p->size];
        int key_ = temp->key[MAX / 2];
        for(int i = 0; i < p1->size; i++){
            p1->key[i] = temp->key[i + p->size + 1];
            p1->pointer[i] = temp->pointer[i + p->size + 1];
        }
        p1->pointer[p1->size] = temp->pointer[p1->size + p->size + 1];
        insert_in_parent(p,key_,p1);
    }
}

Node *BPTree::copy_node(Node *node){
    Node* temp = new Node();
    for(int i = 0;i < node->size; i++) {
        temp->key[i] = node->key[i]; 
        temp->pointer[i] = node->pointer[i];
    }
    temp->pointer[node->size] = node->pointer[node->size];
    temp->IS_LEAF = node->IS_LEAF;
    temp->size = node->size;
    return temp;
}

void BPTree::insert(int key){
    //根节点为空，创建一个新的节点。
    if(root == nullptr){
        root = new Node();
        root->key[0] = key;
        root->size = 1;
        root->IS_LEAF = true;
        return ;
    }else{
        if(find(key) != -1) return ;
        Node *node = root;
        parent.clear();
        while(node->IS_LEAF == false){
            int pos = 0;
            while(pos < node->size && node->key[pos] <= key) pos += 1;
            parent.push_back(node);
            node = node->pointer[pos];
        }//找到要插入的叶子节点
        if(node->size < MAX - 1){
            insert_in_leaf(key,node);
        }else{
            Node* temp = copy_node(node);
            insert_in_leaf(key,temp);
            Node *node1 = new Node();
            node1->IS_LEAF = true;
            node1->pointer[MAX - 1] = node->pointer[MAX - 1];
            node->pointer[MAX - 1] = node1;
            //情空原节点的数据。
            for(int i = 0; i < node->size; i++){ node->key[i] = 0; node->pointer[i] = nullptr; }
            node->size = MAX / 2; node1->size = MAX - MAX / 2;
            for(int i = 0; i < node->size; i++){ node->key[i] = temp->key[i]; node->pointer[i] = temp->pointer[i]; }
            for(int i = 0; i < node1->size; i++){ node1->key[i] = temp->key[i + MAX / 2]; node1->pointer[i] = temp->pointer[i + MAX / 2];}
            int key_ = node1->key[0];
            insert_in_parent(node,key_,node1);
        }
    }
}

void BPTree::display() {
    queue<Node*>q;
    q.push(root);
    while(!q.empty()){
        int size_=q.size();
        while(size_--){
            auto t=q.front();
            for(int i=0;i<t->size+1;i++){
                if(!t->IS_LEAF){
                    q.push(t->pointer[i]);
                }
            }
            for(int i=0;i<t->size;i++){
                cout<<t->key[i]<<",";
            }
            cout<<"  ";
            q.pop();
        }
        cout<<endl;
    }
}

void BPTree::RedistributeFromLeft(Node *l_node,Node *node,Node *p_node,int index){
    for(int i = node->size - 1; i >= 0; i--) node->key[i + 1] = node->key[i];
    node->key[0] = l_node->key[l_node->size - 1];
    node->size += 1; l_node->size -= 1;
    p_node->key[index - 1] = node->key[0];
}

void BPTree::RedistributeFromRight(Node* r_node,Node *node,Node *p_node,int index){
    cout<<"fuuuuuuuk"<<endl;
    node->key[node->size] = r_node->key[0];
    node->size += 1;
    for(int i = 0; i < r_node->size - 1; i++) r_node->key[i] = r_node->key[i + 1];
    r_node->size -= 1;
    p_node->key[index] = r_node->key[0];
}

void BPTree::RedistributeFromLeftinternal(Node *l_node,Node *node,Node *p_node,int index){
    for (int i = node->size - 1; i >= 0; i--) {
        node->key[i + 1] = node->key[i];
        node->pointer[i + 2] = node->pointer[i + 1];
    }
    // 将父节点的分隔 key 下移到当前节点
    node->key[0] = p_node->key[index - 1];
    node->pointer[1] = node->pointer[0];
    node->pointer[0] = l_node->pointer[l_node->size];

    // 更新父节点 key
    p_node->key[index - 1] = l_node->key[l_node->size - 1];

    node->size++;
    l_node->size--;
}

void BPTree::RedistributeFromRightinternal(Node* r_node,Node *node,Node *p_node,int index){
    node->key[node->size] = p_node->key[index];
    node->pointer[node->size + 1] = r_node->pointer[0];
    node->size += 1;
    p_node->key[index] = r_node->key[0];
    // 右兄弟 key 和 pointer 向左移动一位
    for (int i = 0; i < r_node->size - 1; i++) {
        r_node->key[i] = r_node->key[i + 1];
        r_node->pointer[i] = r_node->pointer[i + 1];
    }
    r_node->pointer[r_node->size - 1] = r_node->pointer[r_node->size];
    r_node->size -= 1;
}

void BPTree::Mergeleaf(Node *l_node,Node *node){
    for(int i = 0; i < node->size; i++) l_node->key[i + l_node->size] = node->key[i];
    l_node->size += node->size;
    l_node->pointer[MAX - 1] = node->pointer[MAX - 1];
}

void BPTree::Delete(int key){
    Node *node = root;
    parent.clear();
    while(node->IS_LEAF == false){
        int index = 0;
        while(index < node->size && node->key[index] <= key) index += 1;
        parent.push_back(node);
        node = node->pointer[index];
    }
    //找到叶子节点
    int pos = 0;
    while(pos < node->size && node->key[pos] < key) pos += 1;
    if(node->key[pos] != key) return ;
    for(int i = pos; i < node->size - 1; i++) node->key[i] =node->key[i + 1];
    node->size -= 1;
    //删除键值
    if(node->size >= MAX / 2) return ;
    else{
        Node *p_node = parent.back();
        parent.pop_back();
        int index = get_pos(node, p_node);
        Node *l_node = (index > 0)?p_node->pointer[index - 1]:nullptr;
        Node *r_node = (index < p_node->size)?p_node->pointer[index + 1]:nullptr;

        if(l_node && l_node->size >= MAX / 2 + 1){
            RedistributeFromLeft(l_node,node,p_node,index);           
        }else if(r_node && r_node->size >= MAX / 2 + 1){
            RedistributeFromRight(r_node,node,p_node,index);
        }else if(l_node != nullptr){
            Mergeleaf(l_node,node);
            delete_internal(p_node->key[index-1], node, p_node);
        }else{
            Mergeleaf(node,r_node);
            delete_internal(p_node->key[index],r_node,p_node);
        }
    }
}

int BPTree::get_pos(Node *node,Node *parent){
    for (int i = 0; i <= parent->size; i++) {
        if (parent->pointer[i] == node) {
            return i;
        }
    }
    return -1;
}

void BPTree::Mergeinternal(Node *l_node,int key,Node *node){
    l_node->key[l_node->size] = key;
    l_node->size += 1;
    for (int i = 0; i < node->size; i++) {
        l_node->key[l_node->size + i] = node->key[i];
        l_node->pointer[l_node->size + i] = node->pointer[i];
    }
    l_node->size += node->size;
    l_node->pointer[l_node->size] = node->pointer[node->size];
}

void BPTree::delete_internal(int key, Node *Rpointer, Node *node){
    int pos = 0;
    while(pos < node->size && node->key[pos] < key) pos += 1;
    for(int i = pos; i < node->size - 1; i++) {
        node->key[i] =node->key[i + 1];
        node->pointer[i + 1] = node->pointer[i + 2];
    } 
    node->pointer[node->size] = nullptr;
    node->size -= 1;
    if(node == root){
        if(root->size == 0){
            root = node->pointer[0];
            delete node;
            return ;  
        }
        return ;
    }
    if(node->size >= MAX / 2) return ;
    else{
        Node *p_node = parent.back();
        parent.pop_back();
        int index = get_pos(node, p_node);
        Node *l_node = (index > 0)?p_node->pointer[index - 1]:nullptr;
        Node *r_node = (index < p_node->size)?p_node->pointer[index + 1]:nullptr;

        if(l_node && l_node->size >= MAX / 2 + 1){
            RedistributeFromLeftinternal(l_node,node,p_node,index);
        }else if(r_node && r_node->size >= MAX / 2 + 1){
            RedistributeFromRightinternal(r_node,node,p_node,index);
        }else if(l_node){
            Mergeinternal(l_node,p_node->key[index - 1],node);
            delete_internal(p_node->key[index - 1], node, p_node);
        }else {
            Mergeinternal(node,p_node->key[index],r_node);
            delete_internal(p_node->key[index],r_node, p_node);
        }
    }
}

Node* get_left(Node *root){
    Node *node = root;
    while(node->IS_LEAF==false) node = node->pointer[0];
    return node;
}

int main(){
    BPTree* tree = new BPTree();
    tree->insert(2);
    tree->insert(9);
    tree->insert(3);
    tree->insert(1);
    tree->insert(4);
    tree->insert(8);
    tree->insert(11);
    tree->insert(5);
    tree->insert(7);
    tree->display();
    tree->Delete(3);
    tree->display();
    tree->Delete(1);
    tree->display();
    tree->Delete(9);
    tree->display();
    tree->Delete(11);
    tree->display();
    tree->Delete(8);
    tree->display();
    tree->Delete(7);
    tree->display();
    tree->Delete(4);
    tree->display();
    tree->Delete(5);
    tree->display();
    return 0;
}