紅黑樹訪問按順序索引

我有一個紅黑樹（二叉樹，所有的葉子都在2級）。我可以瀏覽節點：向左，向右或父母。我知道節點的全部數目。紅黑樹訪問按順序索引

我必須找到樹中第N個最小的元素。有沒有辦法比O（n）更快地做到這一點？任何通過索引優化訪問的想法？

2012-03-31 Dmitry Fedorkov

在你應該存儲的每個節點X中，有多少個節點在以X爲根的子樹中。

count(LEAF) = 1 
count(NODE) = count(NODE->LEFT) + count(NODE->RIGHT) + 1

在每次插入/刪除您應該使用這個公式來更新受旋轉節點計數。

該解決方案之後是簡單的

NODE nth(NODE root, int n) { 
    if (root->left->count <= n) return nth(root->left, n); 
    if (root->left->count + 1 == n) return root; 
    return nth(root->right, n - root->left->count - 1); 
}

來源

2012-03-31 06:49:14

謝謝。其實我正在修改.NET的'SortedDictionary'來訂購，但現在我發現沒有簡單的方法。 – 2012-03-31 08:50:41

此實現不正確。標誌被切換。請參閱下面的答案。 – 2017-05-25 05:19:52

您可以在顯示此節點的子節點數的每個節點中添加一個屬性。使用此屬性，您可以找到具有O（lgn）的第N個最小節點。

現在只需在插入（或刪除）任何節點到樹中時處理此屬性。如果沒有旋轉，那麼它很容易處理，但是當你旋轉時有點困難，但你可以做到。

來源

2012-03-31 06:47:36 Divuneh

對於紅黑樹，你不需要跟蹤的節點數目的離開，因爲如果它是正確的偏置（應該是），然後左節點的數量始終形成一個mersenne系列（1,3,7,15,31 ...）或2^depth -1。

考慮到這一點，我們可以寫下遞歸獲取節點的邏輯。 上面接受的答案已將其符號切換爲。這是靈藥的正確實施。對於package

def nth(%Rbtree{node: r}, n), do: do_nth(r, n) 
defp do_nth({_,h,k,v,l,r}, n) do 
    l_count = left_count(h) 
    cond do 
    l_count > n -> 
     case l do 
     nil -> {k,v} 
     _ -> do_nth(l, n) 
     end 
    l_count == n -> {k,v} 
    true -> 
     case r do 
     nil -> {k,v} 
     _ -> do_nth(r, n - l_count - 1) 
     end 
    end 
end 
defp left_count(1), do: 0 
defp left_count(0), do: 0 
defp left_count(h), do: :math.pow(2,h-1)-1 |> round

來源

2017-05-25 05:23:46

紅黑樹訪問按順序索引

回答

相關問題