具有序號索引的訪問樹

我有一個右偏的紅黑樹形結構，它在給定元素總數的情況下始終是某種形狀。具有序號索引的訪問樹

給定元素k的大小和序數元素n，如何編寫函數來獲取大小爲k的樹中的第n個元素？

(size:1) 
black { 1, 1 }(d:1) 
+ 
+ 


(size:2) 
black { 1, 1 }(d:1) 
+ 
+ red { 2, 2 }(d:1) 
    + 
    + 


(size:3) 
black { 2, 2 }(d:2) 
+ black { 1, 1 }(d:1) 
    + 
    + 
+ black { 3, 3 }(d:1) 
    + 
    + 


(size:4) 
black { 2, 2 }(d:2) 
+ black { 1, 1 }(d:1) 
    + 
    + 
+ black { 3, 3 }(d:1) 
    + 
    + red { 4, 4 }(d:1) 
    + 
    + 


(size:5) 
black { 2, 2 }(d:2) 
+ black { 1, 1 }(d:1) 
    + 
    + 
+ red { 4, 4 }(d:2) 
    + black { 3, 3 }(d:1) 
    + 
    + 
    + black { 5, 5 }(d:1) 
    + 
    + 


(size:6) 
black { 2, 2 }(d:2) 
+ black { 1, 1 }(d:1) 
    + 
    + 
+ red { 4, 4 }(d:2) 
    + black { 3, 3 }(d:1) 
    + 
    + 
    + black { 5, 5 }(d:1) 
    + 
    + red { 6, 6 }(d:1) 
     + 
     + 


(size:7) 
black { 4, 4 }(d:3) 
+ black { 2, 2 }(d:2) 
    + black { 1, 1 }(d:1) 
    + 
    + 
    + black { 3, 3 }(d:1) 
    + 
    + 
+ black { 6, 6 }(d:2) 
    + black { 5, 5 }(d:1) 
    + 
    + 
    + black { 7, 7 }(d:1) 
    + 
    + 


(size:8) 
black { 4, 4 }(d:3) 
+ black { 2, 2 }(d:2) 
    + black { 1, 1 }(d:1) 
    + 
    + 
    + black { 3, 3 }(d:1) 
    + 
    + 
+ black { 6, 6 }(d:2) 
    + black { 5, 5 }(d:1) 
    + 
    + 
    + black { 7, 7 }(d:1) 
    + 
    + red { 8, 8 }(d:1) 
     + 
     + 


(size:9) 
black { 4, 4 }(d:3) 
+ black { 2, 2 }(d:2) 
    + black { 1, 1 }(d:1) 
    + 
    + 
    + black { 3, 3 }(d:1) 
    + 
    + 
+ black { 6, 6 }(d:2) 
    + black { 5, 5 }(d:1) 
    + 
    + 
    + red { 8, 8 }(d:2) 
    + black { 7, 7 }(d:1) 
     + 
     + 
    + black { 9, 9 }(d:1) 
     + 
     + 


(size:10) 
black { 4, 4 }(d:3) 
+ black { 2, 2 }(d:2) 
    + black { 1, 1 }(d:1) 
    + 
    + 
    + black { 3, 3 }(d:1) 
    + 
    + 
+ black { 6, 6 }(d:2) 
    + black { 5, 5 }(d:1) 
    + 
    + 
    + red { 8, 8 }(d:2) 
    + black { 7, 7 }(d:1) 
     + 
     + 
    + black { 9, 9 }(d:1) 
     + 
     + red { 10, 10 }(d:1) 
     + 
     +

來源

2017-05-25 Ricky Han

而不是存儲每個節點的深度，嘗試存儲的大小（或左孩子的數量）。 – Bergi

只是想通了。原來你不需要存儲大小（可以根據深度信息計算） –

@Bergi這隻適用於紅黑樹。對於其他樹，您必須存儲節點數。 –

我把所有東西都寫在餐巾紙上，然後想通了。對於紅黑樹，你不需要跟蹤左邊節點的數量，因爲如果它是正確的偏差（應該是），那麼左節點的數量將總是形成一個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:28:05

具有序號索引的訪問樹

回答

相關問題