> For the complete documentation index, see [llms.txt](https://book.bsdcn.org/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://book.bsdcn.org/man/misc/tree.3.md). # tree.3 `SPLAY_PROTOTYPE` — 伸展树和秩平衡（wavl）树的实现 ## 名称 `SPLAY_PROTOTYPE`, `SPLAY_GENERATE`, `SPLAY_ENTRY`, `SPLAY_HEAD`, `SPLAY_INITIALIZER`, `SPLAY_ROOT`, `SPLAY_EMPTY`, `SPLAY_NEXT`, `SPLAY_MIN`, `SPLAY_MAX`, `SPLAY_FIND`, `SPLAY_LEFT`, `SPLAY_RIGHT`, `SPLAY_FOREACH`, `SPLAY_INIT`, `SPLAY_INSERT`, `SPLAY_REMOVE`, `RB_PROTOTYPE`, `RB_PROTOTYPE_STATIC`, `RB_PROTOTYPE_INSERT`, `RB_PROTOTYPE_INSERT_COLOR`, `RB_PROTOTYPE_REMOVE`, `RB_PROTOTYPE_REMOVE_COLOR`, `RB_PROTOTYPE_FIND`, `RB_PROTOTYPE_NFIND`, `RB_PROTOTYPE_NEXT`, `RB_PROTOTYPE_PREV`, `RB_PROTOTYPE_MINMAX`, `RB_PROTOTYPE_REINSERT`, `RB_GENERATE`, `RB_GENERATE_STATIC`, `RB_GENERATE_INSERT`, `RB_GENERATE_INSERT_COLOR`, `RB_GENERATE_REMOVE`, `RB_GENERATE_REMOVE_COLOR`, `RB_GENERATE_FIND`, `RB_GENERATE_NFIND`, `RB_GENERATE_NEXT`, `RB_GENERATE_PREV`, `RB_GENERATE_MINMAX`, `RB_GENERATE_REINSERT`, `RB_ENTRY`, `RB_HEAD`, `RB_INITIALIZER`, `RB_ROOT`, `RB_EMPTY`, `RB_NEXT`, `RB_PREV`, `RB_MIN`, `RB_MAX`, `RB_FIND`, `RB_NFIND`, `RB_LEFT`, `RB_RIGHT`, `RB_PARENT`, `RB_FOREACH`, `RB_FOREACH_FROM`, `RB_FOREACH_SAFE`, `RB_FOREACH_REVERSE`, `RB_FOREACH_REVERSE_FROM`, `RB_FOREACH_REVERSE_SAFE`, `RB_INIT`, `RB_INSERT`, `RB_INSERT_NEXT`, `RB_INSERT_PREV`, `RB_REMOVE`, `RB_REINSERT`, `RB_AUGMENT`, `RB_AUGMENT_CHECK`, `RB_UPDATE_AUGMENT` ## 概要 ```c #include ``` ## 描述 这些宏定义了不同类型的树数据结构：伸展树和秩平衡（wavl）树。 在宏定义中，`TYPE` 是用户定义结构的名称标签，该结构必须包含一个类型为 `SPLAY_ENTRY` 或 `RB_ENTRY`、名为 `ENTRYNAME` 的字段。参数 `HEADNAME` 是用户定义结构的名称标签，必须使用宏 `SPLAY_HEAD()` 或 `RB_HEAD()` 声明。参数 `NAME` 对于定义的每棵树必须是唯一的名称前缀。 函数原型通过 `SPLAY_PROTOTYPE()`、`RB_PROTOTYPE()` 或 `RB_PROTOTYPE_STATIC()` 声明。函数体通过 `SPLAY_GENERATE()`、`RB_GENERATE()` 或 `RB_GENERATE_STATIC()` 生成。有关这些宏使用方法的进一步说明，请参见下面的示例。 ## 伸展树 伸展树是一种自组织数据结构。对树的每次操作都会导致伸展发生。伸展将请求的节点移动到树的根部，并部分重新平衡它。 这样做的好处是请求局部性会导致更快的查找，因为请求的节点会移动到树的顶部。另一方面，每次查找都会导致内存写入。 平衡定理将 `m` 次操作和 `n` 次插入在初始空树上的总访问时间限定为 O(m + n lg n)。对伸展树进行 `m` 次访问序列的摊还成本为 O(lg n)。 伸展树以由 `SPLAY_HEAD()` 宏定义的结构作为头部。结构声明如下： `SPLAY_HEAD(HEADNAME, TYPE)` `head`; 其中 `HEADNAME` 是要定义的结构名称，struct `TYPE` 是要插入树中的元素类型。 `SPLAY_ENTRY()` 宏声明允许元素在树中连接的结构。 为了使用操作树结构的函数，需要使用 `SPLAY_PROTOTYPE()` 宏声明其原型，其中 `NAME` 是此特定树的唯一标识符。`TYPE` 参数是树管理的结构类型。`FIELD` 参数是由 `SPLAY_ENTRY()` 定义的元素名称。 函数体通过 `SPLAY_GENERATE()` 宏生成。它接受与 `SPLAY_PROTOTYPE()` 宏相同的参数，但只应使用一次。 最后，`CMP` 参数是用于比较树节点的函数名称。该函数接受两个 `struct TYPE *` 类型的参数。如果第一个参数小于第二个，函数返回小于零的值。如果相等，函数返回零。否则，应返回大于零的值。比较函数定义了树元素的顺序。 `SPLAY_INIT()` 宏初始化由 `head` 引用的树。 伸展树也可以使用 `SPLAY_INITIALIZER()` 宏静态初始化，如下所示： `SPLAY_HEAD(HEADNAME, TYPE)` `head` = `SPLAY_INITIALIZER(&head)`; `SPLAY_INSERT()` 宏将新元素 `elm` 插入树中。 `SPLAY_REMOVE()` 宏从 `head` 指向的树中删除元素 `elm`。 `SPLAY_FIND()` 宏可用于在树中查找特定元素。 ```c struct TYPE find, *res; find.key = 30; res = SPLAY_FIND(NAME, head, &find); ``` `SPLAY_ROOT()`、`SPLAY_MIN()`、`SPLAY_MAX()` 和 `SPLAY_NEXT()` 宏可用于遍历树： ```c for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np)) ``` 或者，为简便起见，可以使用 `SPLAY_FOREACH()` 宏： `SPLAY_FOREACH(np, NAME, head)` 应使用 `SPLAY_EMPTY()` 宏检查伸展树是否为空。 ## 秩平衡树 秩平衡（RB）树是定义高度平衡二叉搜索树（包括 AVL 和红黑树）的框架。每个树节点都有相关的秩。平衡条件通过任何节点与其子节点之间的秩差条件表示。秩差存储在每个树节点中。 RB 宏实现的平衡条件产生弱 AVL（wavl）树，结合了 AVL 和红黑树的最佳特性。wavl 树在插入后的重新平衡方式与 AVL 树相同，具有与红黑树相同的最坏情况时间，并且生成的树具有更好的平衡性。wavl 树在删除后的重新平衡方式所需的重构比 AVL 或红黑树都少。删除可能导致树几乎像红黑树一样不平衡；插入导致树变得像 AVL 树一样平衡。 秩平衡树以由 `RB_HEAD()` 宏定义的结构作为头部。结构声明如下： `RB_HEAD(HEADNAME, TYPE)` `head`; 其中 `HEADNAME` 是要定义的结构名称，struct `TYPE` 是要插入树中的元素类型。 `RB_ENTRY()` 宏声明允许元素在树中连接的结构。 为了使用操作树结构的函数，需要使用 `RB_PROTOTYPE()` 或 `RB_PROTOTYPE_STATIC()` 宏声明其原型，其中 `NAME` 是此特定树的唯一标识符。`TYPE` 参数是树管理的结构类型。`FIELD` 参数是由 `RB_ENTRY()` 定义的元素名称。如果并非所有函数都需要，可以使用 `RB_PROTOTYPE_INSERT()`、`RB_PROTOTYPE_INSERT_COLOR()`、`RB_PROTOTYPE_REMOVE()`、`RB_PROTOTYPE_REMOVE_COLOR()`、`RB_PROTOTYPE_FIND()`、`RB_PROTOTYPE_NFIND()`、`RB_PROTOTYPE_NEXT()`、`RB_PROTOTYPE_PREV()`、`RB_PROTOTYPE_MINMAX()` 和 `RB_PROTOTYPE_REINSERT()` 声明单个原型。单个原型宏需要 `NAME`、`TYPE` 和 `ATTR` 参数。`ATTR` 参数对于全局函数必须为空，对于静态函数必须为 `static`。 函数体通过 `RB_GENERATE()` 或 `RB_GENERATE_STATIC()` 宏生成。这些宏接受与 `RB_PROTOTYPE()` 和 `RB_PROTOTYPE_STATIC()` 宏相同的参数，但只应使用一次。作为替代，可以通过 `RB_GENERATE_INSERT()`、`RB_GENERATE_INSERT_COLOR()`、`RB_GENERATE_REMOVE()`、`RB_GENERATE_REMOVE_COLOR()`、`RB_GENERATE_FIND()`、`RB_GENERATE_NFIND()`、`RB_GENERATE_NEXT()`、`RB_GENERATE_PREV()`、`RB_GENERATE_MINMAX()` 和 `RB_GENERATE_REINSERT()` 宏生成单个函数体。 最后，`CMP` 参数是用于比较树节点的函数名称。该函数接受两个 `struct TYPE *` 类型的参数。如果第一个参数小于第二个，函数返回小于零的值。如果相等，函数返回零。否则，应返回大于零的值。比较函数定义了树元素的顺序。 `RB_INIT()` 宏初始化由 `head` 引用的树。 秩平衡树也可以使用 `RB_INITIALIZER()` 宏静态初始化，如下所示： `RB_HEAD(HEADNAME, TYPE)` `head` = `RB_INITIALIZER(&head)`; `RB_INSERT()` 宏将新元素 `elm` 插入树中。 `RB_INSERT_NEXT()` 宏将新元素 `elm` 紧接在给定元素之后插入树中。 `RB_INSERT_PREV()` 宏将新元素 `elm` 紧接在给定元素之前插入树中。 `RB_REMOVE()` 宏从 `head` 指向的树中删除元素 `elm`。 `RB_FIND()` 和 `RB_NFIND()` 宏可用于在树中查找特定元素。 `RB_FIND()` 宏返回树中等于所提供键的元素，如果没有这样的元素则返回 `NULL`。 `RB_NFIND()` 宏返回大于或等于所提供键的最小元素，如果没有这样的元素则返回 `NULL`。 ```c struct TYPE find, *res, *resn; find.key = 30; res = RB_FIND(NAME, head, &find); resn = RB_NFIND(NAME, head, &find); ``` `RB_ROOT()`、`RB_MIN()`、`RB_MAX()`、`RB_NEXT()` 和 `RB_PREV()` 宏可用于遍历树： ```c for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np)) ``` 或者，为简便起见，可以使用 `RB_FOREACH()` 或 `RB_FOREACH_REVERSE()` 宏： `RB_FOREACH(np, NAME, head)` `RB_FOREACH_SAFE()` 和 `RB_FOREACH_REVERSE_SAFE()` 宏分别正向和反向遍历由 head 引用的树，依次将每个元素赋值给 np。然而，与它们的不安全对应版本不同，它们允许在循环内安全地删除 np 并释放它，而不会干扰遍历。 `RB_FOREACH_FROM()` 和 `RB_FOREACH_REVERSE_FROM()` 都可用于在中断的正向或反向遍历中继续。不需要头指针。应将恢复遍历的节点指针作为它们的最后一个参数传递，该指针将被覆盖以提供安全遍历。 应使用 `RB_EMPTY()` 宏检查秩平衡树是否为空。 `RB_REINSERT()` 宏更新元素 `elm` 在树中的位置。如果以影响比较的方式修改了 `tree` 的成员（例如修改节点键），则必须调用此宏。这是删除元素并重新插入的更低开销替代方案。 `RB_AUGMENT()` 宏更新树中元素 `elm` 的增强数据。默认情况下，它没有任何效果。不打算由 RB 用户调用。如果 `RB_AUGMENT()` 由 RB 用户定义，则当从树中插入或删除元素时，它会被树中作为已更改子树根的每个元素调用，从树底部向上工作。它通常用于维护树元素的某些关联累积，如总和、最小值、最大值等。 `RB_AUGMENT_CHECK()` 宏更新树中元素 `elm` 的增强数据。默认情况下，它什么也不做并返回 false。如果 `RB_AUGMENT_CHECK()` 已定义，则当从树中插入或删除元素时，它会被树中作为已更改子树根的每个元素调用，从树底部向上工作，直到它返回 false 表示未更改元素，因此进一步向上工作树不会更改任何内容。它通常用于维护树元素的某些关联累积，如总和、最小值、最大值等。 `RB_UPDATE_AUGMENT()` 宏更新树中元素 `elm` 及其祖先的增强数据。如果 `RB_AUGMENT()` 由 RB 用户定义，则当树中的元素被更改（不改变树中项的顺序）时，对该元素调用此函数会恢复树增强状态的一致性，如同该元素已被删除并重新插入。 ## 实例 以下示例演示如何声明一个持有整数的秩平衡树。向其中插入值，并按顺序打印树的内容。为维护树中值的总和，每个元素维护其值及其左右子树的总和。最后，打印树的内部结构。 ```c #define RB_AUGMENT(entry) sumaug(entry) #include #include #include #include struct node { RB_ENTRY(node) entry; int i, sum; }; int intcmp(struct node *e1, struct node *e2) { return (e1->i < e2->i ? -1 : e1->i > e2->i); } void sumaug(struct node *e) { e->sum = e->i; if (RB_LEFT(e, entry) != NULL) e->sum += RB_LEFT(e, entry)->sum; if (RB_RIGHT(e, entry) != NULL) e->sum += RB_RIGHT(e, entry)->sum; } RB_HEAD(inttree, node) head = RB_INITIALIZER(&head); RB_GENERATE(inttree, node, entry, intcmp) int testdata[] = { 20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18, 7, 11, 14 }; void print_tree(struct node *n) { struct node *left, *right; if (n == NULL) { printf("nil"); return; } left = RB_LEFT(n, entry); right = RB_RIGHT(n, entry); if (left == NULL && right == NULL) printf("%d", n->i); else { printf("%d(", n->i); print_tree(left); printf(","); print_tree(right); printf(")"); } } int main(void) { int i; struct node *n; for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) { if ((n = malloc(sizeof(struct node))) == NULL) err(1, NULL); n->i = testdata[i]; RB_INSERT(inttree, &head, n); } RB_FOREACH(n, inttree, &head) { printf("%d\n", n->i); } print_tree(RB_ROOT(&head)); printf("\nSum of values = %d\n", RB_ROOT(&head)->sum); return (0); } ``` ## 注释 以下方式释放树是一个常见错误： ```c SPLAY_FOREACH(var, NAME, head) { SPLAY_REMOVE(NAME, head, var); free(var); } free(head); ``` 由于 `var` 被释放，`FOREACH()` 宏引用的指针可能已被重新分配。正确的代码需要第二个变量。 ```c for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) { nxt = SPLAY_NEXT(NAME, head, var); SPLAY_REMOVE(NAME, head, var); free(var); } ``` `RB_INSERT()` 和 `SPLAY_INSERT()` 在元素成功插入树中时返回 `NULL`，否则返回具有冲突键的元素指针。 相应地，`RB_REMOVE()` 和 `SPLAY_REMOVE()` 返回被删除元素的指针，否则返回 `NULL` 表示错误。 ## 参见 [arb(3)](/man/misc/arb.3.md), [queue(3)](/man/misc/queue.3.md) > Bernhard Haeupler, Siddhartha Sen, Robert E. Tarjan, "Rank-Balanced Trees", *ACM Transactions on Algorithms*, 11, 4, June 2015。 ## 历史 树宏首次出现于 FreeBSD 4.6。 ## 作者 树宏的作者是 Niels Provos。 --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://book.bsdcn.org/man/misc/tree.3.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.