我正在做一个项目，它要求我使用 search.h 中的 glibc 函数创建并经常搜索 RB 树。我在创建树或搜索它都没有问题;但是，我只是想不出在 O(log n( 时间内找到树最大值的方法。AFAIK 正确的方法是沿着树的右翼一直走到第一片叶子;我真的不知道如何实现它。
我创建树或搜索它都没有问题;但是，我只是 无法找到查找树最大值的方法 O(log n( 时间。AFAIK 正确的方法是一直走下去 树的右翼直到第一片叶子;我真的不能 弄清楚如何实现它。
恐怕你运气不好。 (POSIX( search.h的树操作函数不提供直接服务于查找最大值(或查找最小值(操作的接口，并且它们用于表示树的内部数据结构不会公开，因此您无法手动实现常用方法。 您可以使用 twalk() 找到最大值，但这样做需要遍历整个树，因此将缩放为 O(n(。 即使找到最小值也会花费 O(n(，尽管深度优先步行将以 O(log n( 步长达到最小元素，因为它不会止步于此。