答复: 答复: 答复: [PATCH] rbtree: stop iteration early in rb_find_first
Date: Thu Aug 26 2021 - 01:05:15 EST
> 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
> 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:
> / \
> 5 10(c)
> 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.