Модифицированный алгоритм BTree в C ++ - PullRequest
Новая
       15

Модифицированный алгоритм BTree в C ++

0 голосов
/ 06 июня 2018

Я пишу структуру, аналогичную Btree, где каждый узел состоит из ключа и указателя на следующий узел, значения которого равны или больше этого элемента.Это должно быть примерно так на картинке.

enter image description here

Количество ключей и дочерних указателей одинаковое.Мне нужно реализовать вставку, поиск и удаление, но количество элементов в узле должно оставаться между k / 2 и k.Если узел заполнен, вставляемое значение должно быть вставлено в родительский узел, а родительский узел должен быть разделен.

Мой код: 

template <class T>
class Tree;

template <class T>
class Node {
private:
  int maxElements;            //Maksymalna liczba elementów w węźle. El. = [key, childPointer]
  Node <T> **childPointers;   //Tablica wskaźników na potomków
  T *keys;                    //Tablica kluczy
  bool leaf;                  //Czy węzeł jest liściem.
  int n;                     //Obecna liczba kluczy.

public:
  Node();
  Node(int _maxElements, bool _leaf) : maxElements(_maxElements), leaf(_leaf) {
    //Zaalokuj pamięć na maksymalną liczbę możliwych kluczy i wskaźników na potomków
    keys = new int[maxElements];
    childPointers = new Node<T> *[maxElements];
    n = 0; //Początkowa liczba kluczy.
  }

  void insertNonFull(int k); //Wstaw nowy klucz w poddrzewie(jeśli węzeł nie jest pełny)
  void splitChild(int i, Node *y); //Podziel potomka y tego węzła; i - indeks 'y' w tablicy childPointers
  void traverse();
  Node<T> *search(int k);  //Szukaj klucza w poddrzewie wskazanego węzła.

  friend Tree<T>;
};
template<class T>
void Node<T>::traverse(){
  int i;
  //n kluczy i  n potomków
  for (i = 0; i < n; i++) {
      //Jesli nie jest liściem to przed wydrukowaniem key[i] przejdź potomka childPointer[i]
    if (leaf == false)  {
      childPointers[i]->traverse();

      } 
template <class T>
class Tree {
private:
  Node <T> *root;           //Wskaźnik na roota(korzeń).
  int maxNodeElements;      //k (maks. liczba elementów)

public:
  Tree();
  Tree(int _maxNodeElements) : maxNodeElements(_maxNodeElements){
    //root = new Node<T>(maxNodeElements);
    root = nullptr;
  }

  ////Moje/////
  void traverse() {
    if(root != nullptr)   root->traverse();
  }

  Node<T>* search(int k){
    return (root == nullptr)? nullptr : root->search(k);
  }
  void insert(int k);

};

template <class T>
void Tree<T>::insert(int k){
  //Drzewo puste
  if(root == nullptr) {
      //Zaalokuj pamięć dla roota
      root = new Node<T>(maxNodeElements, true);
      root->keys[0] = k; //wstaw klucz
      root->n = 1; //zaktualizuj liczbę kluczy roota
    }
  else {        //Drzewo nie jest puste
      //Jeśli root pełny
      //Dzielimy za wczasu, by ułatwić obsługę w przyszłości
      if(root->n == maxNodeElements) {
          //Zaalokuj pamięć dla nowego roota
          Node<T> *s = new Node<T>(maxNodeElements, false);

          //Stary root staje się potomkiem nowego(przestaw wskaźnik)
          s->childPointers[0]  = root;

          //Podziel starego roota i przesuń jeden klucz do nowego
          s->splitChild(0, root);

          //Nowy root ma dwoje potomków
          int i = 0;
          if(s->keys[0] < k)
            i++;
          s->childPointers[i]->insertNonFull(k);

          root = s; //zamiana roota
        }
      else //root nie jest pełny
        root->insertNonFull(k);
  }

}

`

Мой вопрос заключается в том, как правильно реализовать реализацию вставки - что я должен изменить в своем коде, чтобы childPointers указывали на новые узлы со значениямибольше или равно родителю.Теперь первый узел имеет ключи, которые меньше или равны.

...