关于GLIB中GTree的几个问题

unicorns

GLIB的在线文档很简单.
但基本信息还是有.
GTree就是一棵按照g_tree_new 时给定的比较函数构造
的平衡二叉树.

GLIB对此提供了几个用于查找的函数
其中一个是

1. 
   
2. gpointer    g_tree_lookup    (GTree *tree,gconstpointer key);
   
3. 
   
4. Gets the value corresponding to the given key. Since a GTree is automatically balanced as key/value pairs are added, key lookup is very fast.
   

复制代码

这个很明白,他用构造这棵树时使用的比较函数作为默认的比较函数来进行查找.

但是另一个就让我有点困惑了.

1. 
   
2. gpointer    g_tree_search                   (GTree *tree,
   
3.                                              GCompareFunc search_func,
   
4.                                              gconstpointer user_data);
   
5. 
   
6. The search_func is called with a pointer to the key of a key/value pair in the tree, and the passed in user_data. If search_func returns 0 for a key/value pair, then g_tree_search_func() will return the value of that pair. If search_func returns -1, searching will proceed among the key/value pairs that have a smaller key; if search_func returns 1, searching will proceed among the key/value pairs that have a larger key.
   

复制代码

这个函数允许使用者提供一个比较函数来进行查找.
这个比较函数显然可以不同于构造该树时使用的那个,否则就没有这个必要了.
在线文档里说的也有点含混,所谓"smaller"和"larger"是针对原来的构造比较函数而言还是对使用者提供的新的比较函数而言.

如果指的是原来构造树用的比较函数,那显然说不太通.
所以我还是倾向于认为他指的是使用者提供的新的比较函数.

这样就有个问题,调用这个函数的查找效率能得到保证吗?
这种怀疑的依据是
显然调用该函数不会针对新的比较函数构造一棵新的平衡二叉树.因为这样做会产生巨大的开销;
那要实现查找功能只能遍历整棵树?想想也不可能,如果要遍历整棵树查找某个KEY值的话只需要给出KEY值就行了,又何必多出一个比较函数.

难道调用该函数会对树针对新的比较函数做某些优化还是别的什么.

真的想不通了.

unicorns

上面写的认识有点错误.
遍历整棵树来查找某个KEY值也需要比较函数.
比较函数用来定义两个KEY相等的条件.

但我还是想g_tree_search这函数不会真的去遍历整棵树吧.
但除此之外还有什么办法在一棵按照其他比较函数建立的平衡二叉树上实现查找功能呢?

在讲到g_tree_lookup    函数时,用了"very fast".
在讲g_tree_search时没用.
可想效率肯定存在很大区别.但会不会慢到O(n)那样呢.

unicorns

临走前顶一下.
没有哪位用过这东西吗
谈谈实际效率如何.

unicorns

UP