红黑树中从节点A走到节点B的最快方法
Fastest way to walk from node A to node B in a red-black tree
假设我想从节点 #154 步行到节点 #254 以尽可能最快：
我能得到的最好的是：获取范围内的第一个节点并从该节点开始按顺序走：
/*
* Look for a node matching a key range in tree.
* Returns a pointer to the node if found, else NULL.
*/
struct rb_node *rb_range(struct rb_tree *tree, void *data, int (*func)(const void *, const void *))
{
struct rb_node *node = rb_first(tree);
int res;
while (node != rb_nil(tree)) {
if ((res = func(data, node->data)) == 0) {
return node;
}
node = res < 0 ? node->left : node->right;
}
return NULL;
}
比较函数如下所示：
static int range_comp(const void *range, const void *data)
{
const long ele = *(const long *)data;
const long *arr = range;
if ((ele >= arr[0]) && (ele <= arr[1])) {
return 0;
}
if (ele > arr[0]) {
return -1;
} else {
return +1;
}
}
以及遍历结果的回调（有注释可以查看有多少节点被发送到回调）：
static int print_data(void *data, void *cookie)
{
long value = *(long *)data;
const long *arr = cookie;
if (cookie != NULL) {
if (value > arr[1]) {
return 1;
}
// if (value >= arr[0]) {
printf("%ld\n", value);
// }
}
return 0;
}
中序遍历：
/*
* Call func() for each node, passing it the node data and a cookie;
* If func() returns non-zero for a node, the traversal stops and the
* error value is returned. Returns 0 on successful traversal.
*/
int rb_apply_node(struct rb_tree *tree, struct rb_node *node,
int (*func)(void *, void *), void *cookie, enum rb_traversal order)
{
int error;
if (node != rb_nil(tree)) {
if (order == preorder)
if ((error = func(node->data, cookie)) != 0)
return error;
if ((error = rb_apply_node(tree, node->left, func, cookie, order)) != 0)
return error;
if (order == inorder)
if ((error = func(node->data, cookie)) != 0)
return error;
if ((error = rb_apply_node(tree, node->right, func, cookie, order)) != 0)
return error;
if (order == postorder)
if ((error = func(node->data, cookie)) != 0)
return error;
}
return 0;
}
long x = rand() % n;
printf("%d) Printing from %ld to %ld\n", i, x, x + 100);
long arr[] = {x, x + 100};
node = rb_range(tree, arr, range_comp);
if (node != NULL) {
/* Iterate from node A to node B INORDER */
rb_apply_node(tree, node, print_data, arr, inorder);
}
但是我得到的结果太多了：
0 2 3 4 5 6 8 10 12 13 14 16 17 18 19 20 21 22 23 25 26 27 28 29 31 32
35 36 38 39 40 41 42 43 44 45 47 48 50 51 53 57 59 60 61 62 63 64 65
67 68 72 75 76 77 78 80 81 82 83 85 88 90 91 93 95 96 98 100 101 102
108 109 111 112 113 115 116 117 118 121 122 123 124 125 126 127 128
129 131 132 135 136 137 138 141 143 145 146 148 149 150 153 157 158
161 163 166 168 169 170 172 173 174 175 176 177 178 179 180 182 183
186 188 189 190 192 193 194 195 196 197 198 199 200 201 202 203 205
206 210 212 216 217 218 219 220 221 222 223 225 226 227 228 229 230
231 233 234 235 236 238 239 240 241 244 245 249 252 253 254
如何（尽可能）将结果限制在所选范围内（154 到 254）？
您的函数 rb_apply_node() 接受一个 node 参数，然后将 func() 应用于树中该节点及其下方的每个节点。这与从某个节点开始并按排序顺序迭代不同。为了进行说明，请使用以下包含元素 1 到 7 的树：
4
/ \
2 6
/ \ / \
1 3 5 7
在您的实现中，如果您想查看范围 2 到 6，那么您首先搜索包含 2 的节点。到目前为止一切顺利。但是 rb_apply_node() 只会从那个节点开始，并且会像 2 是树的根，并且只会在那个子树中下降，导致：
1 2 3
如果您恰好想要范围 4 到 5，那么它将从 4 开始并下降：
1 2 3 4 5
它会在 5 处停止的唯一原因是您的 print_data() 有一个检查以跳过任何大于所需范围末尾的内容；但是 rb_apply_node() 仍会继续迭代 6 和 7。
一个快速的解决方案是将 rb_apply_node() 更改为始终从 tree 的根开始，但快速跳过第一个节点，直到到达所需的开始 node。
首先，只考虑你正在尝试做什么，而不是你是如何开始尝试解决它的（这是错误的，因为你错误地假设 next 节点总是在右子树中，这是不正确的）在你的树上得到某种迭代器并找到一条记录，然后去下一步，再下一步，直到你到达另一端。
由于二叉树不是这种结构，所以按照其他答案中暴露的简单树：
4
/ \
2 6
/ \ / \
1 3 5 7
假设您必须从节点 3 转到节点 6。我会尝试提供一个
通过仅考虑我现在所在节点的特征，允许我从一个节点旅行到下一个节点的算法。节点3的下一个节点4需要我们爬左parents（左parent将是一个节点我们是正确的 child) 直到我们到达 正确的 parent （类似地，正确的 parent 是我们是左边 child)。这将我们引向下一个没有右子树的节点。
在节点 4 上，我们有一个右子树，因此下一个节点将是这棵右子树的第一个节点，它是通过跟随右子树的左 child 找到的，直到我们不要再得到 left children。然后我们到达节点 5.
在节点5中我们没有右子树，所以我们必须向上爬树寻找第一个右parent。这将我们交易到节点 6。在此之后，所有节点都大于限制，所以我们完成搜索。
在一个结构中，你已经包含了一个 parent 节点（如果你没有，你必须从树的根部包含一堆节点以获得 parent)你可以有如下功能（这里写的没有测试过，只是提示，还得测试，留给reader)
struct node {
int key;
struct node *parent, *left, *right;
/* ... more stuff */
};
/* this routine returns the parent node if it is a left
* parent, NULL otherwise (covers the no parent case for
* the root node */
struct node *left_parent(struct node *n)
{
if (!n->parent) return NULL; /* no parent */
if (n->parent->left == n) return NULL; /* this is a right parent */
return n->parent;
}
/* this routine returns the parent node if it is a right
* parent, NULL otherwise (covers the no parent case for
* the root node */
struct node *right_parent(struct node *n)
{
if (!n->parent) return NULL;
if (n->parent->right == n) return NULL; /* this is a left parent */
return n->parent;
}
/* get the first key node of the tree rooted at n */
struct node *first(struct node *n)
{
while (n->left) n = n->left;
return n; /* this is the first node of the subtree rooted at n */
}
/* get the last key node of the tree rooted at n */
struct node *last(struct node *n)
{
while (n->right) n = n->right;
return n; /* this is the last node of the subtree rooted at n */
}
/* finds the next node, with the algorithm described in the text */
struct node *next(struct node *n)
{
if (n->right) /* we have subnodes */
return first(n->right);
else { /* on the parents */
struct node *nxt;
while ((nxt = left_parent(n)) != NULL) n = nxt;
return n->parent; /* can be a right parent or NULL only */
}
}
/* finds the prev node, with the algorithm described in the text */
struct node *prev(struct node *n)
{
if (n->left) /* we have subnodes */
return last(n->left);
else {
struct node *prv;
while ((prv = right_parent(n)) != NULL) n = prv;
return n->parent; /* can be a left parent or NULL only */
}
}
最后；
int first, last;
struct node *iterator, *root;
...
for (iterator = find(root, first);
iterator && iterator.key <= last;
iterator = next(iterator))
{
do_something_to_iterator_node(iterator);
}
好吧，这不如按照链表快，但也差不多，而且你的优势是对整棵树进行了排序。
注意
以防万一你想保存 space 并且不包括 parent 指针，迭代器从单个指针转换为一堆节点指针，从我们现在访问的指针到树的根节点，我们检查 left_parent 和 right_parent，方法是查看顶部节点（或顶部旁边的节点，具体取决于是否将访问的节点压入堆栈）节点。
假设我想从节点 #154 步行到节点 #254 以尽可能最快：
我能得到的最好的是：获取范围内的第一个节点并从该节点开始按顺序走：
/*
* Look for a node matching a key range in tree.
* Returns a pointer to the node if found, else NULL.
*/
struct rb_node *rb_range(struct rb_tree *tree, void *data, int (*func)(const void *, const void *))
{
struct rb_node *node = rb_first(tree);
int res;
while (node != rb_nil(tree)) {
if ((res = func(data, node->data)) == 0) {
return node;
}
node = res < 0 ? node->left : node->right;
}
return NULL;
}
比较函数如下所示：
static int range_comp(const void *range, const void *data)
{
const long ele = *(const long *)data;
const long *arr = range;
if ((ele >= arr[0]) && (ele <= arr[1])) {
return 0;
}
if (ele > arr[0]) {
return -1;
} else {
return +1;
}
}
以及遍历结果的回调（有注释可以查看有多少节点被发送到回调）：
static int print_data(void *data, void *cookie)
{
long value = *(long *)data;
const long *arr = cookie;
if (cookie != NULL) {
if (value > arr[1]) {
return 1;
}
// if (value >= arr[0]) {
printf("%ld\n", value);
// }
}
return 0;
}
中序遍历：
/*
* Call func() for each node, passing it the node data and a cookie;
* If func() returns non-zero for a node, the traversal stops and the
* error value is returned. Returns 0 on successful traversal.
*/
int rb_apply_node(struct rb_tree *tree, struct rb_node *node,
int (*func)(void *, void *), void *cookie, enum rb_traversal order)
{
int error;
if (node != rb_nil(tree)) {
if (order == preorder)
if ((error = func(node->data, cookie)) != 0)
return error;
if ((error = rb_apply_node(tree, node->left, func, cookie, order)) != 0)
return error;
if (order == inorder)
if ((error = func(node->data, cookie)) != 0)
return error;
if ((error = rb_apply_node(tree, node->right, func, cookie, order)) != 0)
return error;
if (order == postorder)
if ((error = func(node->data, cookie)) != 0)
return error;
}
return 0;
}
long x = rand() % n;
printf("%d) Printing from %ld to %ld\n", i, x, x + 100);
long arr[] = {x, x + 100};
node = rb_range(tree, arr, range_comp);
if (node != NULL) {
/* Iterate from node A to node B INORDER */
rb_apply_node(tree, node, print_data, arr, inorder);
}
但是我得到的结果太多了：
0 2 3 4 5 6 8 10 12 13 14 16 17 18 19 20 21 22 23 25 26 27 28 29 31 32 35 36 38 39 40 41 42 43 44 45 47 48 50 51 53 57 59 60 61 62 63 64 65 67 68 72 75 76 77 78 80 81 82 83 85 88 90 91 93 95 96 98 100 101 102 108 109 111 112 113 115 116 117 118 121 122 123 124 125 126 127 128 129 131 132 135 136 137 138 141 143 145 146 148 149 150 153 157 158 161 163 166 168 169 170 172 173 174 175 176 177 178 179 180 182 183 186 188 189 190 192 193 194 195 196 197 198 199 200 201 202 203 205 206 210 212 216 217 218 219 220 221 222 223 225 226 227 228 229 230 231 233 234 235 236 238 239 240 241 244 245 249 252 253 254
如何（尽可能）将结果限制在所选范围内（154 到 254）？
您的函数 rb_apply_node() 接受一个 node 参数，然后将 func() 应用于树中该节点及其下方的每个节点。这与从某个节点开始并按排序顺序迭代不同。为了进行说明，请使用以下包含元素 1 到 7 的树：
4
/ \
2 6
/ \ / \
1 3 5 7
在您的实现中，如果您想查看范围 2 到 6，那么您首先搜索包含 2 的节点。到目前为止一切顺利。但是 rb_apply_node() 只会从那个节点开始，并且会像 2 是树的根，并且只会在那个子树中下降，导致：
1 2 3
如果您恰好想要范围 4 到 5，那么它将从 4 开始并下降：
1 2 3 4 5
它会在 5 处停止的唯一原因是您的 print_data() 有一个检查以跳过任何大于所需范围末尾的内容；但是 rb_apply_node() 仍会继续迭代 6 和 7。
一个快速的解决方案是将 rb_apply_node() 更改为始终从 tree 的根开始，但快速跳过第一个节点，直到到达所需的开始 node。
首先，只考虑你正在尝试做什么，而不是你是如何开始尝试解决它的（这是错误的，因为你错误地假设 next 节点总是在右子树中，这是不正确的）在你的树上得到某种迭代器并找到一条记录，然后去下一步，再下一步，直到你到达另一端。
由于二叉树不是这种结构，所以按照其他答案中暴露的简单树：
4
/ \
2 6
/ \ / \
1 3 5 7
假设您必须从节点 3 转到节点 6。我会尝试提供一个
通过仅考虑我现在所在节点的特征，允许我从一个节点旅行到下一个节点的算法。节点3的下一个节点4需要我们爬左parents（左parent将是一个节点我们是正确的 child) 直到我们到达 正确的 parent （类似地，正确的 parent 是我们是左边 child)。这将我们引向下一个没有右子树的节点。
在节点 4 上，我们有一个右子树，因此下一个节点将是这棵右子树的第一个节点，它是通过跟随右子树的左 child 找到的，直到我们不要再得到 left children。然后我们到达节点 5.
在节点5中我们没有右子树，所以我们必须向上爬树寻找第一个右parent。这将我们交易到节点 6。在此之后，所有节点都大于限制，所以我们完成搜索。
在一个结构中，你已经包含了一个 parent 节点（如果你没有，你必须从树的根部包含一堆节点以获得 parent)你可以有如下功能（这里写的没有测试过，只是提示，还得测试，留给reader)
struct node {
int key;
struct node *parent, *left, *right;
/* ... more stuff */
};
/* this routine returns the parent node if it is a left
* parent, NULL otherwise (covers the no parent case for
* the root node */
struct node *left_parent(struct node *n)
{
if (!n->parent) return NULL; /* no parent */
if (n->parent->left == n) return NULL; /* this is a right parent */
return n->parent;
}
/* this routine returns the parent node if it is a right
* parent, NULL otherwise (covers the no parent case for
* the root node */
struct node *right_parent(struct node *n)
{
if (!n->parent) return NULL;
if (n->parent->right == n) return NULL; /* this is a left parent */
return n->parent;
}
/* get the first key node of the tree rooted at n */
struct node *first(struct node *n)
{
while (n->left) n = n->left;
return n; /* this is the first node of the subtree rooted at n */
}
/* get the last key node of the tree rooted at n */
struct node *last(struct node *n)
{
while (n->right) n = n->right;
return n; /* this is the last node of the subtree rooted at n */
}
/* finds the next node, with the algorithm described in the text */
struct node *next(struct node *n)
{
if (n->right) /* we have subnodes */
return first(n->right);
else { /* on the parents */
struct node *nxt;
while ((nxt = left_parent(n)) != NULL) n = nxt;
return n->parent; /* can be a right parent or NULL only */
}
}
/* finds the prev node, with the algorithm described in the text */
struct node *prev(struct node *n)
{
if (n->left) /* we have subnodes */
return last(n->left);
else {
struct node *prv;
while ((prv = right_parent(n)) != NULL) n = prv;
return n->parent; /* can be a left parent or NULL only */
}
}
最后；
int first, last;
struct node *iterator, *root;
...
for (iterator = find(root, first);
iterator && iterator.key <= last;
iterator = next(iterator))
{
do_something_to_iterator_node(iterator);
}
好吧，这不如按照链表快，但也差不多，而且你的优势是对整棵树进行了排序。
注意
以防万一你想保存 space 并且不包括 parent 指针，迭代器从单个指针转换为一堆节点指针，从我们现在访问的指针到树的根节点，我们检查 left_parent 和 right_parent，方法是查看顶部节点（或顶部旁边的节点，具体取决于是否将访问的节点压入堆栈）节点。