具有序号索引的访问树

我有一个右偏的红黑树形结构，它在给定元素总数的情况下始终是某种形状。具有序号索引的访问树

给定元素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

具有序号索引的访问树

回答

相关问题