Messages in this thread | | | From | "Li,Rongqing" <> | Subject | 答复: 答复: 答复: [PATCH] rbtree: stop iterat ion early in rb find first | Date | Thu, 26 Aug 2021 05:03:54 +0000 |
| |
> 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
| |