如何有效地找到 GTree 中的最后一个键和值

Question

我需要开发一组函数来扩展 glib2 GTree 具有：

找到第一个元素
找到最后一个
查找最近的（floor、ceil、最大小于、最小大于）

首先找到很容易。您只需在 first 之后停止 g_tree_foreach() 回调。但是如何在不遍历整个树的情况下找到最后一个元素？

我想我可以将 g_tree_search() 与一个回调一起使用，该回调在找到之前一直返回正值，但我怎么知道我当前在最后一个元素上？

#include <stdio.h> #include <sys/types.h> #include <string.h> #include <glib.h> static gint compare_int(gconstpointer p1, gconstpointer p2) { int i1 = GPOINTER_TO_INT(p1); int i2 = GPOINTER_TO_INT(p2); //printf("%d %d\n", i1, i2); return i1 == i2 ? 0 : i1 > i2 ? 1 : -1; } static gboolean traverse(gpointer key, gpointer value, gpointer data) { //int ikey = GPOINTER_TO_INT(key); const char *sval = (const char *)value; printf("%s\n", sval); return FALSE; } static gint find_last(gconstpointer p, gpointer user_data) { return 1; } static inline const char *NULS(const char *s) { return s ? s : "NULL"; } int main(int argc, char *argv[]) { GTree *tree = g_tree_new(compare_int); g_tree_insert(tree, GINT_TO_POINTER(10), "ten"); g_tree_insert(tree, GINT_TO_POINTER(-99), "minus ninety-nine"); g_tree_insert(tree, GINT_TO_POINTER(8), "eight"); g_tree_foreach(tree, traverse, NULL); printf("=======\n%s\n", NULS((const char*)g_tree_search(tree, (GCompareFunc)find_last, NULL))); return 0; }

Answer 1

我不想完全实现自己的树，因为我想对从第 3 方代码收到的 GTree 个实例执行高级搜索。

相反，我认为这些天 Glib 作者几乎不会改变他们的内部结构，我可以直接使用他们的字段。

结果是 gtree.c. I added two parameters to control whether I want first, last or nearest node. The algorithm for nearest nodes differs from java's TreeMap, because our node doesn't have a pointer to its parent. Full code with the unit test is here: gtreeex.c 的内部函数 g_tree_find_node() 的扩展版本。

typedef enum {
    FIND_EXACT = 0,
    FIND_FLOOR = 0x2,
    FIND_CEIL  = 0x20,
    FIND_LOWER = (FIND_FLOOR + 1),
    FIND_HIGHER = (FIND_CEIL + 1)
} find_mode;

static GTreeNode *
g_tree_find_node_ex (GTree        *tree,
                  gconstpointer key,
                  GCompareDataFunc key_compare,
                  find_mode mode
                  )
{
    GTreeNode *node;
    gint cmp;
    GTreeNode *last_lesser_node = NULL;
    GTreeNode *last_greater_node = NULL;

    node = tree->root;
    if (!node)
        return NULL;

    while (1)
        {
            cmp = key_compare (key, node->key, tree->key_compare_data);
            if (cmp == 0) {
                if (mode == FIND_LOWER) {
                    cmp = -1;
                } else if (mode == FIND_HIGHER) {
                    cmp = 1;
                } else {
                    return node;
                }
            }

            if (cmp < 0)
                {
                    if (!node->left_child) {
                        if ( (mode & FIND_FLOOR) ) {
                            return last_lesser_node; /* can be null */
                        }
                        if ( (mode & FIND_CEIL) ) {
                            return node;
                        }
                        return NULL;
                    }

                    last_greater_node = node;
                    node = node->left;
                }
            else
                {
                    if (!node->right_child) {
                        if ( (mode & FIND_CEIL) ) {
                            return last_greater_node; /* can be null */
                        }
                        if ( (mode & FIND_FLOOR) ) {
                            return node;
                        }
                        return NULL;
                    }

                    last_lesser_node = node;
                    node = node->right;
                }
        }
}

为了获得更好的性能，可以使用预处理器宏代替两个新参数，将 if 替换为 #if 并多次包含位 header。

如何有效地找到 GTree 中的最后一个键和值

How to efficiently find last key and value in GTree

c

glib

binary-search-tree