如何找到 RB 树中的最大值
How to find the maximum value(s) in a RB tree
我正在从事一个项目，该项目要求我使用 search.h 中的 glibc 函数创建并经常搜索 RB 树。
创建树或搜索树都没有问题；但是，我只是想不出一种在 O(log n) 时间内找到树的最大值的方法。 AFAIK 正确的方法是沿着树的右翼一直走到第一片叶子；实在想不通怎么实现。
I have no problem creating the tree nor searching it; however, I just
can't figure out a way of finding the maximum value of the tree in
O(log n) time. AFAIK the right way is to just walk all the way down
the right wing of the tree up until the first leaf; I really can't
figure out how to implement it.
恐怕你运气不好。 (POSIX) search.h 的 tree-manipulation 函数不提供直接服务于 find-maximum（或 find-minimum）操作的接口，以及它们使用的内部数据结构表示树不公开，所以你不能手动实现通常的方法。您可以使用 twalk() 找到最大值，但这样做需要遍历整棵树，因此将扩展为 O(n)。即使找到最小值也会花费 O(n)，尽管 depth-first 步行将在 O(log n) 步中到达最小元素，因为它不会停在那里。
我正在从事一个项目，该项目要求我使用 search.h 中的 glibc 函数创建并经常搜索 RB 树。 创建树或搜索树都没有问题；但是，我只是想不出一种在 O(log n) 时间内找到树的最大值的方法。 AFAIK 正确的方法是沿着树的右翼一直走到第一片叶子；实在想不通怎么实现。
I have no problem creating the tree nor searching it; however, I just can't figure out a way of finding the maximum value of the tree in O(log n) time. AFAIK the right way is to just walk all the way down the right wing of the tree up until the first leaf; I really can't figure out how to implement it.
恐怕你运气不好。 (POSIX) search.h 的 tree-manipulation 函数不提供直接服务于 find-maximum（或 find-minimum）操作的接口，以及它们使用的内部数据结构表示树不公开，所以你不能手动实现通常的方法。您可以使用 twalk() 找到最大值，但这样做需要遍历整棵树，因此将扩展为 O(n)。即使找到最小值也会花费 O(n)，尽管 depth-first 步行将在 O(log n) 步中到达最小元素，因为它不会停在那里。