Найти k-й наименьший элемент рекурсивно в B-дереве с более чем одним элементом в узле - PullRequest
Новая
       25

Найти k-й наименьший элемент рекурсивно в B-дереве с более чем одним элементом в узле

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

Предположим, у нас есть следующее b-дерево

b-tree

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

До сих пор я делал это, что работает нормальнодля элементов последней ветви 

i <-0
function kthSmallestElement(Node node, int k)
    if(branch[i] != NULL) then
        size<-branch[i].size();
    if(k < size) then
        i++;
        call the function recursively for new branch[i], k
    else if(k > size) then
        k-=size
        i++;
        call the function recursively for new branch[i], k
    else if (k==size) then
        print branch[i]->entry[k-1]
    else
        print brach[i-1]->entry[k-1]
end function

Я реализовал алгоритм, используя C 

#define MAX 4      /* maximum number of keys in node. */
#define MIN 2      /* minimum number of keys in node */

typedef int Key;

typedef struct {
   Key key;
   int value;     /* values can be arbitrary */
} Treeentry;


typedef enum {FALSE, TRUE} Boolean;

typedef struct treenode Treenode;

struct treenode {
  int count;     /* denotes how many keys there are in the node */
    /*
        The entries at each node are kept in an array entry 
          and the pointers in an array branch
    */
  Treeentry entry[MAX+1];
  Treenode *branch[MAX+1];
};

int i = 0;
int size = 0;
void FindKthSmallestElement(Treenode *rootNode, int k){
  if(branch[i] != NULL) //since the node has a child
    size = branch[i] ->count;
    if(k < size){
      i++;
      FindKthSmallestElement(branch[i], k);
    }else if(k > size){
      k-=size;
      i++;
      FindKthSmallestElement(branch[i], k);
    }else if (k==size)
      printf ("%d", branch[i]->entry[k-1].key);
    else
      printf ("%d", brach[i-1]->entry[k-1].key);
}

Не могли бы вы предложить, что я должен исправить в этом, чтобы иметь действительный вывод длякаждый kth самый маленький элемент?Я склонен полагать, что эта проблема не может быть решена рекурсивно, так как у нас есть более одной записи в каждом узле.Было бы разумно сделать это деревом кучи, как в этой ссылке ?

Ответы [ 2 ]

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

Эту проблему можно решить рекурсивно.Все, что вам нужно, это чтобы функция возвращала 2 вещи:

  1. k-й наименьший ключ (или указатель на него), если он имеет k или более клавиш.
  2. Размердерева, если в нем меньше k ключей.

Рекурсия происходит путем последовательного вызова функции на каждом поддереве (корневого) узла, от самого левого до самого правого,и с другим (убывающим) параметром k:

  • Пусть исходное / текущее дерево будет R, запускает рекурсию, вызывая функцию в самом левом поддереве R с тем же k, что и R, которое получает.
  • Если вызов функции на поддереве R успешно возвращает k-й наименьший ключ, то это ответ и вернуть его.
  • Если вызов функции на некотором поддереве T из R не может найтиk-й наименьший ключ, но вместо этого возвращает a размер T, скажем, n (
  • Если T - самое правое поддерево, то R имеет меньше k элементов, возвращает размерR (который был бы найден путем суммирования размеров всех егоподдеревья и количество ключей в корне R).
  • Если n == k-1, то k-тый наименьший ключ - это ключ непосредственно справа от T
  • Если n

Очевидно, вам нужно позаботиться о терминальном условии, когда корень дерева не имеет поддерева.Концептуально это может быть легче обработано, если использовать поддерево NULL, которое содержит клавишу 0.

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

Рекурсивно посещать каждый узел и добавлять в список k наименьших элементов текущего узла.В конце разбери его и получи k-й номер.

Вы также можете попробовать сравнить список 2 и сохранить k наименьших значений каждый раз, но я думаю, что это сделает код более сложным и в итоге будет иметь примерно такую ​​же или худшую скорость, но наверняка будет занимать меньше памяти.

...