> You're right that rb_add() does a tail-add for elements it considers equal -- there
> is actually code in the tree that relies on this.
>
> But that doesn't mean rb_find_first() should go right, it *must*not*, because
> then it wouldn't find the 'first' aka 'leftmost' instance of the equal elements.
>
> Also, you're only considering building the tree in-order with rb_add(), trees get
> modified all the time and the pattern Michel gave is perfectly valid (also see
> rb_prev()).
>
> Sure the snippet is not a balanced tree, but you can construct the pattern as
> part of a larger tree just fine, just add some elements:
>
>
> 10(b)
> / \
> 5 10(c)
> \
> 10(a)
>
> is a tree that is balanced (remember, RB trees only require the left and right
> depths to no more than double -- as opposed to AVL trees, which have a tighter
> constraint). This tree has order: 5, 10(a), 10(b), 10(c).
> Also note that the tree rotations are stable -- they must be since they do not
> refence the order function.
>
> As such, if we rb_find_first() for 10, we must find 10(a), the leftmost
> 10 in the tree.
I see, Thanks for the explanation. Sorry for the noise.
-Li