From a60aa6bebc8cc1d72e89be6b9cfb7338f092158d Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Mon, 25 Jul 2016 19:14:21 -0700 Subject: [PATCH 1/1] avl_tree: add avl_tree_prev_in_order() --- include/wimlib/avl_tree.h | 5 ++++- src/avl_tree.c | 32 ++++++++++++++++++++++++++------ 2 files changed, 30 insertions(+), 7 deletions(-) diff --git a/include/wimlib/avl_tree.h b/include/wimlib/avl_tree.h index ddc1ba7c..2e07e03c 100644 --- a/include/wimlib/avl_tree.h +++ b/include/wimlib/avl_tree.h @@ -262,7 +262,10 @@ extern struct avl_tree_node * avl_tree_first_in_order(const struct avl_tree_node *root); extern struct avl_tree_node * -avl_tree_next_in_order(const struct avl_tree_node *prev); +avl_tree_next_in_order(const struct avl_tree_node *node); + +extern struct avl_tree_node * +avl_tree_prev_in_order(const struct avl_tree_node *node); extern struct avl_tree_node * avl_tree_first_in_postorder(const struct avl_tree_node *root); diff --git a/src/avl_tree.c b/src/avl_tree.c index 208880eb..de95270e 100644 --- a/src/avl_tree.c +++ b/src/avl_tree.c @@ -41,23 +41,43 @@ avl_tree_first_in_order(const struct avl_tree_node *root) /* Continues an in-order traversal of the tree: returns the next-greatest-valued * node, or NULL if there is none. */ struct avl_tree_node * -avl_tree_next_in_order(const struct avl_tree_node *prev) +avl_tree_next_in_order(const struct avl_tree_node *node) { const struct avl_tree_node *next; - if (prev->right) - for (next = prev->right; + if (node->right) + for (next = node->right; next->left; next = next->left) ; else - for (next = avl_get_parent(prev); - next && prev == next->right; - prev = next, next = avl_get_parent(next)) + for (next = avl_get_parent(node); + next && node == next->right; + node = next, next = avl_get_parent(next)) ; return (struct avl_tree_node *)next; } +/* Continues a *reverse* in-order traversal of the tree: returns the + * previous-greatest-valued node, or NULL if there is none. */ +struct avl_tree_node * +avl_tree_prev_in_order(const struct avl_tree_node *node) +{ + const struct avl_tree_node *prev; + + if (node->left) + for (prev = node->left; + prev->right; + prev = prev->right) + ; + else + for (prev = avl_get_parent(node); + prev && node == prev->left; + node = prev, prev = avl_get_parent(prev)) + ; + return (struct avl_tree_node *)prev; +} + /* Starts a postorder traversal of the tree. */ struct avl_tree_node * avl_tree_first_in_postorder(const struct avl_tree_node *root) -- 2.43.0