數據結構來保持數

請提出一個數據結構來維護這樣的方式，我可以回答下面的查詢號碼 -數據結構來保持數

查找（INT N） - （的log（n））

計數Ø小於K = O（日誌（n））的

插入數數 - O（日誌（n））的

這不是功課，而是我遇到解決一個更大的一個小問題 - Number of students with better grades and lower jee rank

我雖然有一棵avl樹，每個節點在子樹上都有維護節點數。但是當插入完成並重新平衡完成時，我不知道如何在每個節點維護此計數。

2011-11-08 Nitin Garg

聞到家庭作業......你到目前爲止想過什麼？ – m0skit0

@ m0skit0查看已編輯的問題。 –

我也會嘗試使用AVL樹。沒有深入研究，我認爲這不會太難補充。在AVL樹的情況下，總是需要知道每個節點的每個子樹的深度（或者至少是平衡因子）。因此，傳播子樹的大小不應該太難。在輪換的情況下，你知道每個節點和每個子樹都會在哪裏着陸，所以它應該只是簡單地重新計算那些被旋轉的節點。

2011-11-08 09:23:59 LiKao

在二叉樹中查找O（log（n）），也插入。如果存儲在節點的子樹的大小：

因此，子樹大小就像一個find，O（log（n））。

2011-11-08 08:51:37

這些操作僅在平衡二叉搜索樹中記錄（n）。以及如何在我的問題中更新其中的相關節點。 –

@NitinGarg：無論何時，當有人提到一棵二叉樹時，它們最有可能是一棵平衡的樹。在節點上進行任何操作時，節點上的額外數量信息只是維護不變式的問題 – hugomg

-1

查看堆數據結構的不同變體，例如， here。

2011-11-08 09:05:42 jmg

堆只適用於查找最大值/最小值元素。 – hugomg

堆也很適合找到n個最小的數字。 OP要求「計數小於k的數字」。我明白他對小於k的元素數目感興趣。通過重複採用最小的元素或通過檢查堆數據結構可以解決這個問題。 – jmg

回答