在BST中找到「nth」值（C）

我不知道如何解決這個問題。在BST中找到「nth」值（C）

返回指向NAME_VAL對的指針，它是排序序列中第n個條目的。

若設爲i = 1，返回最小條目

如果i = N時，返回的最大條目

如果n = N/2返回位數條目（或接近）

if（i < 1 || i> n）return 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;

來源

2013-05-01 juice

如果樹是完全平衡（與限制在序列的末尾任何必要的不平衡），您可以通過使用位模式對於n的二進制表示，以指導這樣做走下節點。由於您只是要求提供一般指導，所以我會放棄它，而不是提供代碼。

如果樹不完全平衡，則必須先執行O（n）深度第一步。或者添加一個索引（它有自己的維護成本）。

來源

2013-05-01 03:17:37

BST中最小的元素在哪裏？它是沒有離開孩子的最左邊的節點。所以請按照左邊的鏈接，直到你點擊NULL，這是你的第一個元素。運行時間是O（log n），如果你的樹是（或多或少）平衡的，在最壞的情況下（完全左傾的樹）是O（n）。同樣，最大的元素位於沒有正確孩子的最右側節點中。

中位數是位於中間的元素，即在它的左側和右側具有相同數量的元素。除非你的節點用孩子的數量註釋，否則我看不到在O（log n）中實現中位數的方法。 CLRS：算法介紹將給你完整的帳戶。

來源

2013-05-01 03:25:03 user1666959

在BST中找到「nth」值（C）

回答

相關問題