CODEWITHSUNDEEP
calgorithmdata-structuresb-tree
Vassilis De
Vassilis De

Reputation: 373

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

Suppose we have the following b-tree

b-tree

I would like to create an algorithm in order to find the k-th smallest element. I tried to implement what was written in this link but I found out that none of the solutions seem to work for this kind of tree.

So far I have done this, which runs fine for the elements of the last branch

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

I have implemented the algorithm using 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);
}

Could you please suggest what should I fix in this in order to have a valid output for every kth smallest element? I tend to believe that this problem cannot be solved recursively, since we have more than one entries in each node. Would be wise to make it a heap tree like in this link?

Upvotes: 2

Views: 1129

Answers (2)

Edy
Edy

Reputation: 470

This problem can be solve recursively. All you need is for the function to return 2 things:

  1. The k-th smallest key (or a pointer to it) if it has k or more keys.
  2. The size of the tree if it has less than k keys.

The recursion occurs by calling the function on every subtree of the (root) node, consecutively, from the left-most to the right-most, and with different (decreasing) parameter k:

  • Let the original/current tree be R, starts recursion by calling the function on R's left-most subtree with the same k as R receives.
  • If calling the function on a subtree of R successfully returns the k-th smallest key, then that's the answer and return it.
  • If calling the function on some subtree T of R couldn't find the k-th smallest key, but instead returns a the size of T, say n (< k), then:
    • If T is the right-most subtree, then R has fewer than k items, returns the size of R (which would have been found by summing the sizes of all its subtrees and the number of keys in R's root).
    • If n == k-1, then the k-th smallest key is the key immediately to the right of T
    • If n < k-1, then recurse on the subtree S immediately to the right of T with argument k-n-1 (i.e., to find the (k-n-1)-th smallest key in S)

Obviously you'd have to take care of the terminal condition where a tree's root has no more subtree. Conceptually it may be more easily handled by allowing a NULL subtree, which contains 0 key.

Upvotes: 2

Khepu
Khepu

Reputation: 310

Recursively visit every node and add to a list the k smallest elements of the current node. In the end sort it and get the k-th number.

You could also try comparing the 2 list and keeping the k smallest ones each time but i think it's gonna make the code look more complicated and will end up with roughly the same or worse speed but for sure less memory occupied.

Upvotes: 1

Related Questions