Advertisement
despores

b tree bugged

Jan 22nd, 2022
1,164
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. class Node {
  4. public:
  5.     int *key_;
  6.     Node **children_;
  7.     bool is_leaf_;
  8.     int size_;
  9.  
  10.     Node();
  11.  
  12.     explicit Node(int, bool);
  13.  
  14.     ~Node();
  15.  
  16.     size_t countSize();
  17.  
  18.     int64_t countSum();
  19.  
  20.     bool find(int);
  21. };
  22.  
  23. class BTree {
  24. public:
  25.     explicit BTree(int);
  26.  
  27.     ~BTree();
  28.  
  29.     void insert(int);
  30.  
  31.     size_t size() const;
  32.  
  33.     int64_t sum() const;
  34.  
  35. private:
  36.     int t_;
  37.     Node *head_;
  38.  
  39.     void insertInFreeNode(int, Node *);
  40.  
  41.     void splitChild(int, Node *) const;
  42. };
  43.  
  44. Node::Node(int times, bool is_leaf) {
  45.     is_leaf_ = is_leaf;
  46.     key_ = new int[2 * times - 1];
  47.     children_ = new Node *[2 * times];
  48.     for (int i = 0; i < 2 * times; ++i) {
  49.         children_[i] = nullptr;
  50.     }
  51.     size_ = 0;
  52. }
  53.  
  54. Node::Node() {
  55.     key_ = nullptr;
  56.     children_ = nullptr;
  57. }
  58.  
  59. Node::~Node() {
  60.     delete[] key_;
  61.     delete[] children_;
  62. }
  63.  
  64. size_t Node::countSize() {
  65.     size_t sz = 1;
  66.     if (!is_leaf_) {
  67.         for (int i = 0; i < size_ + 1; ++i) {
  68.             sz += children_[i]->countSize();
  69.         }
  70.     }
  71.     return sz;
  72. }
  73.  
  74. int64_t Node::countSum() {
  75.     int64_t sum = 0;
  76.     for (int i = 0; i < size_; ++i) {
  77.         if (!is_leaf_) {
  78.             sum += children_[i]->countSum();
  79.         }
  80.         sum += key_[i];
  81.     }
  82.     if (!is_leaf_) {
  83.         sum += children_[size_]->countSum();
  84.     }
  85.     return sum;
  86. }
  87.  
  88. bool Node::find(int key) {
  89.     if (this == nullptr) {
  90.         return false;
  91.     }
  92.     int index = 0;
  93.     while (index < size_ && key > key_[index]) {
  94.         index++;
  95.     }
  96.     if (index < size_ && key_[index] == key) {
  97.         return true;
  98.     }
  99.     if (is_leaf_) {
  100.         return false;
  101.     }
  102.     return children_[index]->find(key);
  103. }
  104.  
  105. BTree::BTree(int times) {
  106.     t_ = times;
  107.     head_ = nullptr;
  108. }
  109.  
  110. BTree::~BTree() {
  111.     delete head_;
  112. }
  113.  
  114. void BTree::splitChild(int child_index, Node *node) const {
  115.     Node *child = node->children_[child_index];
  116.     Node *new_child = new Node(t_, child->is_leaf_);
  117.     new_child->size_ = t_ - 1;
  118.     child->size_ = t_ - 1;
  119.     for (int i = 0; i < t_ - 1; ++i) {
  120.         new_child->key_[i] = child->key_[i + t_];
  121.     }
  122.     for (int i = 0; i < t_; ++i) {
  123.         new_child->children_[i] = child->children_[i + t_];
  124.         child->children_[i + t_] = nullptr;
  125.     }
  126.     for (int i = node->size_; i > child_index; --i) {
  127.         node->children_[i + 1] = node->children_[i];
  128.         node->children_[i] = nullptr;
  129.     }
  130.     node->children_[child_index + 1] = new_child;
  131.     for (int i = node->size_ - 1; i > child_index - 1; --i) {
  132.         node->key_[i + 1] = node->key_[i];
  133.     }
  134.     node->key_[child_index] = child->key_[t_ - 1];
  135.     node->size_++;
  136. }
  137.  
  138. void BTree::insertInFreeNode(int key, Node *node) {
  139.     int last_index = node->size_ - 1;
  140.     if (node->is_leaf_) {
  141.         while (last_index >= 0 && node->key_[last_index] > key) {
  142.             node->key_[last_index + 1] = node->key_[last_index];
  143.             last_index--;
  144.         }
  145.         node->key_[last_index + 1] = key;
  146.         node->size_++;
  147.     } else {
  148.         while (last_index >= 0 && node->key_[last_index] > key) {
  149.             last_index--;
  150.         }
  151.         if (node->children_[last_index + 1]->size_ == 2 * t_ - 1) {
  152.             splitChild(last_index + 1, node);
  153.             if (node->key_[last_index + 1] < key) {
  154.                 last_index++;
  155.             }
  156.         }
  157.         insertInFreeNode(key, node->children_[last_index + 1]);
  158.     }
  159. }
  160.  
  161. void BTree::insert(int key) {
  162.     if (head_ == nullptr) {
  163.         head_ = new Node(t_, true);
  164.         head_->key_[0] = key;
  165.         head_->size_ = 1;
  166.         return;
  167.     }
  168.     if (head_->find(key)) {
  169.         return;
  170.     }
  171.     if (head_->size_ < 2 * t_ - 1) {
  172.         insertInFreeNode(key, head_);
  173.     } else {
  174.         Node *new_root = new Node(t_, false);
  175.         new_root->children_[0] = head_;
  176.         splitChild(0, new_root);
  177.         if (key < new_root->key_[0]) {
  178.             insertInFreeNode(key, new_root->children_[0]);
  179.         } else {
  180.             insertInFreeNode(key, new_root->children_[1]);
  181.         }
  182.         head_ = new_root;
  183.     }
  184. }
  185.  
  186. size_t BTree::size() const {
  187.     size_t size = 0;
  188.     if (head_ != nullptr) {
  189.         size += head_->countSize();
  190.     }
  191.     return size;
  192. }
  193.  
  194. int64_t BTree::sum() const {
  195.     int64_t sum = 0;
  196.     if (head_ != nullptr) {
  197.         sum += head_->countSum();
  198.     }
  199.     return sum;
  200. }
  201.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement