在节点中有多个元素的 B 树中递归查找第 k 个最小元素

Question

假设我们有如下的b-tree

我想创建一个算法来找到第 k 个最小的元素。我试图实现此中所写的内容，但我发现 none 的解决方案似乎适用于这种树。

到目前为止我已经完成了这个，它对最后一个分支的元素运行良好

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);
}

你能建议我应该解决什么问题才能为每个第 k 个最小元素提供有效输出吗？我倾向于认为这个问题不能递归解决，因为我们在每个节点中有多个条目。像这样 link?

把它变成堆树是明智的

Answer 1

递归访问每个节点并将当前节点的 k 个最小元素添加到列表中。最后排序得到第k个数。

您也可以尝试比较 2 个列表并每次都保留 k 个最小的列表，但我认为这会使代码看起来更复杂并且最终会以大致相同或更差的速度结束，但肯定会占用更少的内存。

Answer 2

这个问题可以递归求解。您所需要的只是函数 return 2 件事：

第 k 个最小键（或指向它的指针）如果它有 k 个或更多键。
如果树的键少于 k 个，则为树的大小。

递归通过在（根）节点的每个子树上连续调用函数，从最左边到最右边，并使用不同的（递减）参数 k:

设 original/current 树为 R，通过调用 R 最左边的子树上的函数开始递归，其 k 与 R 接收的相同。
如果在 R 的子树上调用函数成功 return 是第 k 个最小的键，那么这就是答案 return 它。
如果在 R 的某个子树 T 上调用函数找不到第 k 个最小键，而是 returns 是 T 的大小，比如 n (< k)，那么：
- 如果 T 是最右边的子树，那么 R 的项目少于 k，returns 是 R 的大小（通过将其所有子树的大小和R 根中的键）。
- 如果n == k-1，那么第k小的键就是紧邻T
- 如果n < k-1，则以参数k-n-1递归T右边的子树S（即找到S中第（k-n-1）个最小键）

显然，您必须处理树的根没有更多子树的终止条件。从概念上讲，允许包含 0 个键的 NULL 子树可能更容易处理。

在节点中有多个元素的 B 树中递归查找第 k 个最小元素

Find the k-th smallest element recursively in a B-tree with more than one elements in a node

c

algorithm

b-tree

data-structures