Thread: [HACKERS] Red-black trees: why would anyone want preorder or postorder traversal?

There is quite a bit of code in src/backend/lib/rbtree.c that is currently
dead according to the code coverage report, but we're hanging onto it
with the thought that somebody might use it later.  That's fine as long as
there is a plausible use-case for it ... but I have to wonder what is the
argument that anyone would ever want pre-order or post-order traversal of
one of these trees (ie, the DirectWalk or InvertedWalk options to
rb_begin_iterate).  Those orderings give semantic meaning to purely
accidental aspects of the tree shape, such as which specific node happens
to be the root at the moment.  You could maybe argue for using them if
you didn't care about the visitation order and just wanted the cheapest,
quickest way of visiting all the nodes --- but these methods are not
cheaper, or simpler, than the left-to-right or right-to-left tree walks.
In fact, the InvertedWalk logic requires its very own extra field in
the iterator state.

Also, the reason I noticed this in the first place is that
I was working on Victor Drobny's submission in the current CF
https://commitfest.postgresql.org/14/1225/
to add a test harness for rbtree.c.  That harness currently expends
much more code, and many more cycles, on testing preorder/postorder
traversal than anything else.  It also has to make several assumptions
about the implementation of red-black trees that I would rather it
didn't.

In short, therefore, I propose we rip out the DirectWalk and InvertedWalk
options along with their support code, and then drop the portions of
test_rbtree that are needed to exercise them.  Any objections?
        regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Hi Tom,

> In short, therefore, I propose we rip out the DirectWalk and InvertedWalk
> options along with their support code, and then drop the portions of
> test_rbtree that are needed to exercise them.  Any objections?

Doesn't sound like something that will be used any time soon. When and
if it will happen nothing prevents us from adding this code back. So
it's +1.

--
Best regards,
Aleksander Alekseev