Как реализовать алгоритм 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 +