Как реализовать алгоритм b-tree на c++?

@jakayla 

B-tree - это структура данных, которая обычно используется для ускорения поиска, вставки и удаления в больших коллекциях данных.

Для реализации B-tree в C++ вам нужно будет написать класс или структуру, которая будет описывать узел B-tree, и реализовать функции для вставки, поиска и удаления элементов.

Вот пример базовой реализации B-tree в C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <vector>
#include <iostream>

const int t = 3;

struct Node {
  std::vector<int> keys;
  std::vector<Node*> children;
  bool isLeaf;

  Node() : isLeaf(true) {}
};

class BTree {
 public:
  BTree() { root = new Node(); }

  void insert(int key) {
    Node* r = root;
    if (r->keys.size() == 2 * t - 1) {
      Node* s = new Node();
      root = s;
      s->children.push_back(r);
      splitChild(s, 0);
      insertNonFull(s, key);
    } else {
      insertNonFull(r, key);
    }
  }

  void splitChild(Node* x, int i) {
    Node* y = x->children[i];
    Node* z = new Node();
    z->isLeaf = y->isLeaf;
    z->keys.resize(t - 1);
    for (int j = 0; j < t - 1; j++) {
      z->keys[j] = y->keys[j + t];
    }
    if (!y->isLeaf) {
      z->children.resize(t);
      for (int j = 0; j < t; j++) {
        z->children[j] = y->children[j + t];
      }
    }
    y->keys.resize(t - 1);
    y->children.resize(t);
    for (int j = x->keys.size(); j >= i + 1; j--) {
      x->children[j +

@jakayla 

1] = x->children[j]; } x->children[i + 1] = z; x->keys.insert(x->keys.begin() + i, y->keys[t - 1]); }

void insertNonFull(Node* x, int k) { int i = x->keys.size() - 1; if (x->isLeaf) { x->keys.resize(x->keys.size() + 1); while (i >= 0 && k < x->keys[i]) { x->keys[i + 1] = x->keys[i]; i--; } x->keys[i + 1] = k; } else { while (i >= 0 && k < x->keys[i]) { i--; } i++; if (x->children[i]->keys.size() == 2 * t - 1) { splitChild(x, i); if (k > x->keys[i]) { i++; } } insertNonFull(x->children[i], k); } }

Node* search(int k) { return searchHelper(root, k); }

Node* searchHelper(Node* x, int k) { int i = 0; while (i < x->keys.size() && k > x->keys[i]) { i++; } if (i < x->keys.size() && k == x->keys[i]) { return x; } else if (x->isLeaf) { return nullptr; } else { return searchHelper(x->children[i], k); } }

void remove(int k) { Node* r = root; removeHelper(r, k); if (r->keys.size() == 0) { root = r->children[0]; delete r; } }

void removeHelper(Node* x, int k) { int i = 0; while (i < x->keys.size() && k > x->keys[i]) { i++; } if (x->isLeaf) { if (i < x->keys.size() && x->keys[i] == k) { x->keys.erase(x->keys.begin() + i); } } else { if (i < x->keys.size() && x->keys[i] == k) { removeInternal(x, i); } else { i++; } removeHelper(x->children[i], k); } }

void removeInternal(Node* x, int i) { Node* y = x->children[i]; Node* z = x->children[i + 1]; if (y->keys.size() >= t) { int pred = getPredecessor(y); x->keys[i] = pred; removeHelper(y, pred); } else if (z->keys.size() >= t) { int succ = getSuccessor(z); x->keys[i] = succ; removeHelper(z, succ); } else { mergeNodes(y, x, z, i); removeHelper(y, x->keys[i]); } }

int getPredecessor(Node* x) { while (!x->isLeaf) { x = x->children[x->children.size() - 1]; } return x->keys[x->keys.size() - 1]; }

int getSuccessor(Node* x) { while (!x->isLeaf) { x = x->children[0]; } return x->keys[0]; }

void mergeNodes(Node* y, Node* x, Node* z, int i) { y->keys.resize(2 * t - 1); y->keys[t - 1] = x->keys[i]; for (int j = t; j < z->keys.size(); j++) { y->keys.push_back(z->keys[j]); } if (!y->isLeaf) { for (int j = t; j <= z->children.size(); j++) { y->children.push_back(z->children[j]); } } x->keys.erase(x->keys.begin() + i); x->children.erase(x->children.begin() + i + 1); delete z; }

private: Node* root; };

int main() { BTree tree; tree.insert(2); tree.insert(5); tree.insert(1); tree.insert(8); tree.insert(10);

Node* found = tree.search(5); if (found) { std::cout << "Found" << std::endl; } else { std::cout << "Not found" << std::endl; }

tree.remove(5);

found = tree.search(5); if (found) { std::cout << "Found" << std::endl; } else { std::cout << "Not found" << std::endl; }

return 0; }