Beyond the Void
BYVoid
Treap 查找第K小的數
本文正體字版由OpenCC轉換

排序二叉樹能解決好多問題,除了基本的插入、刪除、遍歷、查找鍵值以外,還有查找第K小(大)的數的操作。看了一天程序,總算明白了,其實本質和二分查找相似。

從根節點開始查找第r小的數,如果r<=(k的左子樹節點的總個數),那麼第r小的節點一定在k的左子樹,在k的左子樹繼續查找第r小的節點。 如果r>(k的左子樹節點的總個數+節點k的重複單元個數),那麼第r小的節點一定在k的右子樹,在k的右子樹繼續查找第r-(k的左子樹節點的總個數+節點k的重複單元個數)小的節點。 如果以上都不滿足,那麼k就是第r小的數,返回k的鍵值。

(其實我很不習慣用靜態數據存儲二叉樹,但考慮到效率和iRachex大牛的建議,還是使用了靜態存儲)

查找以k爲根的樹中,第r小的節點的值:

int find(int k,int r)
{
    if (r<=p[p[k].l].size)
        return find(p[k].l,r);
    else if (r> p[p[k].l].size+p[k].cnt)
        return find(p[k].r,r-(p[p[k].l].size+p[k].cnt));
    return p[k].key;
}

上次修改時間 2017-02-03

相關日誌