C语言 B树的右下界 _大数据知识库

我有一个B树，我想，给定一个任意的参数键，找出小于或等于参数键的最大数据键，换句话说，我想让它看左边，找出在O(log n)中应该使用的键。
我已经用C代码修改了implementation of lower_bound。

#define ORDER 3
static int compare(const int a, const int b) { return a > b; }
struct node { unsigned size; int key[ORDER - 1]; };
struct branch { struct node base, *child[ORDER]; };
struct ref { struct node *node; unsigned height, idx; };
struct tree { struct node *node; unsigned height; };

static struct ref lower(const struct tree tree, const int x) {
    struct ref lo, found;
    found.node = 0;
    if(!tree.node) return found;
    for(lo.node = tree.node, lo.height = tree.height; ;
        lo.node = ((const struct branch *)(const void *)lo.node)->child[lo.idx],
        lo.height--) {
        unsigned hi = lo.node->size; lo.idx = 0;
        if(!hi) continue;
        do {
            const unsigned mid = (lo.idx + hi) / 2; /* Will not overflow. */
            if(compare(x, lo.node->key[mid]) > 0) lo.idx = mid + 1;
            else hi = mid;
        } while(lo.idx < hi);
        if(lo.idx < lo.node->size) { /* Within bounds, record the current. */
            found = lo;
            if(compare(x, lo.node->key[lo.idx]) > 0) break;
        }
        if(!lo.height) break;
    }
    return found;
}

static int tree_lower_or(const struct tree tree,
    const int key, const int default_value) {
    struct ref ref;
    return (ref = lower(tree, key)).node
        && ref.idx < ref.node->size ? ref.node->key[ref.idx] : default_value;
}

#include <stdio.h>

int main(void) {
    struct node node[] = { { 2, {1,2} }, { 2, {5, 6} } };
    struct branch root = { { 1, {4} }, {node, node+1} };
    const struct tree tree = { &root.base, 1 };
    int i;
    for(i = 0; i < 8; i++)
        printf("%d->%d%s", i, tree_lower_or(tree, i, 0), i < 7 ? ", " : "\n");
    return 0;
}

这里使用了std::lower_bound中的例子，data = {1，2，4，5，5，6}（注意，我的B树的键是急剧增加的，所以我不能有两个5），它打印出 0-〉1，1-〉1，2-〉2，3-〉4，4-〉4，5-〉5，6-〉6，7-〉0，即x->next x in set or 0。

这不完全是我想要的。X1 E2 F1 X也不完全是我想要的，但是很接近。

我想要从右边而不是左边得到一个下界，x->last x in set or 0。

这个函数有名字吗？如何修改上面的lower来给予这个结果？

按照upper_bound的建议，我能够通过保留一个适当更新的返回变量来获得所需的行为，而不需要两次。我发现我有点草率。lower_bound只是正确地排列，但我发现upper_bound并不明显。

我做的第一件事是设计出一个更好的例子，在这个例子中，什么在范围内，什么在域中是非常明显的。在这个例子中，我认为字母键是域，节点索引是范围，（就像我的问题一样）。
这里，key和x是字母域中的任意元素。对每个node应用upper_bound过程，得到范围中的hi。如果hi.idx非零，则found.idx = hi.idx - 1是范围中的一个元素和有效的数据引用。我们沿着树向下，并允许在适当的情况下覆盖它。最后，在tree_left_or和tree_right_or中，我们将范围元素found（它仅仅是不稳定的内部指针索引）变换为键集中有意义的对应字母域键。

/* https://github.com/neil-edelman/orcish needed for Graphviz names. */
/*#include "orcish.h"*/
#include <stdio.h>
#include <assert.h>

#define ORDER 3
static int compare(const char a, const char b) { return a > b; }
struct node { unsigned size; char key[ORDER - 1]; };
struct branch { struct node base, *child[ORDER]; };
struct ref { struct node *node; unsigned height, idx; };
struct tree { struct node *node; unsigned height; };

/** @return A reference the element at the greatest lower bound of `x` in
 `tree`, or if the element doesn't exist, `node` will be null. */
static struct ref right(const struct tree tree, const char x) {
    struct ref lo, found;
    found.node = 0;
    if(!tree.node) return found;
    for(lo.node = tree.node, lo.height = tree.height; ;
        lo.node = ((const struct branch *)(const void *)lo.node)->child[lo.idx],
        lo.height--) {
        unsigned hi = lo.node->size; lo.idx = 0;
        if(!hi) continue;
        do {
            const unsigned mid = (lo.idx + hi) / 2; /* Will not overflow. */
            if(compare(x, lo.node->key[mid]) > 0) lo.idx = mid + 1;
            else hi = mid;
        } while(lo.idx < hi);
        if(lo.idx < lo.node->size) { /* Within bounds, record the current. */
            found = lo;
            if(compare(x, lo.node->key[lo.idx]) > 0) break;
        }
        if(!lo.height) break;
    }
    return found;
}

/** @return Minimum element equal to or greater then `key` in `tree`, or, if
 the `key` is larger than any in the set, `default_value`. */
static char tree_right_or(const struct tree tree,
    const char key, const char default_value) {
    struct ref ref;
    return (ref = right(tree, key)).node
        && ref.idx < ref.node->size ? ref.node->key[ref.idx] : default_value;
}

/** @return A reference to the predecessor of the element at the least upper
 bound of `x` in `tree`, or `node` will be null if the predecessor doesn't
 exist. */
static struct ref left(const struct tree tree, const char x) {
    struct ref hi, found;
    found.node = 0;
    if(!tree.node) return found;
    for(hi.node = tree.node, hi.height = tree.height; ;
        hi.node = ((const struct branch *)(const void *)hi.node)->child[hi.idx],
        hi.height--) {
        unsigned lo = 0;
        if(!(hi.idx = hi.node->size)) continue;
        do { /* Upper-bound. */
            const unsigned mid = (lo + hi.idx) / 2; /* Will not overflow. */
            if(compare(hi.node->key[mid], x) <= 0) lo = mid + 1;
            else hi.idx = mid;
        } while(lo < hi.idx);
        if(hi.idx) {
            found = hi, found.idx--;
            /* Equal elements. */
            if(compare(x, found.node->key[found.idx]) <= 0) break;
        }
        if(!hi.height) break; /* Reached the bottom. */
    }
    return found;
}

/** @return Maximum element equal to or smaller then `key` in `tree`, or, if
 the `key` is smaller than any in the set, `default_value`. */
static char tree_left_or(const struct tree tree,
    const char key, const char default_value) {
    const struct ref ref = left(tree, key);
    return ref.node ? ref.node->key[ref.idx] : default_value;
}

#if 0
static void subgraph(const struct tree *const sub, FILE *fp) {
    const struct branch *branch;
    unsigned i;
    assert(sub->node && fp);
    fprintf(fp, "\ttrunk%p [label = <\n"
        "<table border=\"0\" cellspacing=\"0\">\n"
        "\t<tr><td border=\"0\" port=\"0\">"
        "<font color=\"Gray75\">%s</font></td></tr>\n",
        (const void *)sub->node, orcify(sub->node));
    if(sub->node->size) fprintf(fp, "\t<hr/>\n");
    for(i = 0; i < sub->node->size; i++) {
        const char *const bgc = i & 1 ? " bgcolor=\"Gray95\"" : "";
        fprintf(fp, "\t<tr><td border=\"0\" align=\"left\""
            " port=\"%u\"%s>%c</td></tr>\n", i + 1, bgc, sub->node->key[i]);
    }
    fprintf(fp, "\t<hr/>\n"
        "\t<tr><td></td></tr>\n"
        "</table>>];\n");
    if(!sub->height) return;
    /* Draw the lines between trees. */
    branch = (struct branch *)(void *)sub->node;
    for(i = 0; i <= branch->base.size; i++)
        fprintf(fp, "\ttrunk%p:%u:se -> trunk%p;\n",
        (const void *)sub->node, i, (const void *)branch->child[i]);
    /* Recurse. */
    for(i = 0; i <= branch->base.size; i++) {
        struct tree child;
        child.node = branch->child[i], child.height = sub->height - 1;
        subgraph(&child, fp);
    }
}
/** <https://graphviz.org/> */
static void graph(const struct tree *const tree,
    const char *const fn) {
    FILE *fp;
    assert(tree && fn);
    if(!(fp = fopen(fn, "w"))) { perror(fn); return; }
    fprintf(fp, "digraph {\n"
        "\tgraph [rankdir=LR, truecolor=true, bgcolor=transparent,"
        " fontname=modern, splines=false];\n"
        "\tnode [shape=none, fontname=modern];\n");
    if(!tree->node)
        fprintf(fp, "\tidle [shape=plaintext];\n");
    else subgraph(tree, fp);
    fprintf(fp, "\tnode [color=\"Red\"];\n"
        "}\n");
    fclose(fp);
}
#endif

int main(void) {
    struct node node[] = { { 2, {'b','d'} }, { 2, {'h','j'} } };
    struct branch root = { { 1, {'f'} }, {node, node+1} };
    const struct tree tree = { &root.base, 1 };
    const int expected[] = { 'z', 'b', 'b', 'd', 'd', 'f',
        'f', 'h', 'h', 'j', 'j', 'j' };
    char left[sizeof expected / sizeof *expected];
    char i;
    int passed;
    /*graph(&tree, "graph.gv");
    printf("nodes in B-tree:\n"
        "%s:(b,d), %s:(f), %s:(h,j)\n\n",
        orcify(&node[0]), orcify(&root), orcify(&node[1]));*/
    printf("right or z\n");
    for(i = 'a'; i < 'm'; i++)
        printf("%c\t%c\n", i, tree_right_or(tree, i, 'z'));
    printf("\n"
        "left or z\n");
    for(i = 'a'; i < 'm'; i++)
        printf("%c\t%c\n", i, left[i-'a'] = tree_left_or(tree, i, 'z'));
    printf("\n"
        "supposed to be...\n");
    for(passed = 1, i = 'a'; i < 'm'; i++) {
        printf("%c\t%c\n", i, expected[i-'a']);
        if(left[i-'a'] != expected[i-'a']) passed = 0;
    }
    printf("\n"
        "%s.\n", passed ? "PASSED" : "failed");
    return 0;
}

C语言 B树的右下界

2条答案

相关问题

热门标签

最新问答