1

我不知道如何解决这个问题。

返回指向 NAME_VAL 对的指针，这是排序序列中的第 n 个条目。

如果 i=1，则返回最小条目

如果 i=n，则返回最大条目

如果 n=n/2 你返回中位数条目（或关闭）

if(i < 1 || i > n) 返回 NULL；

运行时间必须是 O(log n)

有人可以为我指出解决这个问题的基本思路的正确方向吗？谢谢！

我的结构：

typedef struct name_val 
{
    char *name;
    double value;
}NAME_VAL;

typedef struct node
{
    NAME_VAL *nV;
    struct node *left;
    struct node *right;
}NODE;
4

2 回答 2

0

如果树是完全平衡的（任何必要的不平衡都限制在序列的末尾），您可以通过使用 n 的二进制表示的位模式来指导遍历节点来做到这一点。由于您只要求一般指导，因此我将保留它而不是提供代码。

如果树不完全平衡，则必须执行 O(n) 深度优先遍历。或者添加一个索引（它有自己的维护成本）。

于 2013-05-01T03:17:37.993 回答
0

BST 中最小的元素在哪里？它是没有左孩子的最左边的节点。因此，请遵循左侧链接，直到您点击 NULL 并且这是您的第一个元素。如果您的树（或多或少）平衡，则运行时间为 O(log n)，在最坏的情况下（完全左倾的树）为 O(n)。同样，最大的元素在最右边的节点中，没有右子节点。

中位数是位于中间的元素，即在它的左边和右边有相同数量的元素。除非您的节点带有子节点数量的注释，否则我看不到在 O(log n) 中实现中位数的方法。CLRS：Introduction to Algorithms 会给你完整的帐户。

于 2013-05-01T03:25:03.530 回答