访问具有序号索引的树 [英] Access tree with ordinal index

问题描述

考虑到元素<$ c的大小，我们有一个右偏的红黑树结构，它总是有一定的形状。 $ c> k 和一个序数元素 n ，如何编写一个函数来获取大小为<$ c的树中的第n个元素
$ b

 （size：1）
 black {1，1 }（d：1）
 + 
 + 
 
 
（size：2）
 black {1，1}（d：1）
 + 
 + red {2,2}（d：1）
 + 
 + 
 
 
（size：3）
黑色{2,2}（d：2）
 +黑色{1,1}（d：1）
 + 
 + 
 +黑色{3,3}（d ：1）
 + 
 + 
 
 
（大小：4）
黑色{2,2}（d：2）
 +黑色{1,1}（d：1）
 + 
 + 
 +黑色{3,3}（d：1）
 + 
 +红色{4 ，4}（d：1）
 + 
 + 
 
 
（大小：5）
 black {2,2}（d：2） 
 + black {1,1}（d：1）
 + 
 + 
 + red {4,4}（d：2）
 + black {3 ，3}（d：1）
 + 
 + 
 + bla ck {5,5}（d：1）
 + 
 + 
 
 
（size：6）
 black {2,2}（d ：2）
 + black {1,1}（d：1）
 + 
 + 
 + red {4,4}（d：2）
 +黑色{3,3}（d：1）
 + 
 + 
 +黑色{5,5}（d：1）
 + 
 + red {6 ，6}（d：1）
 + 
 + 
 
 
（大小：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）
 + 
 + 
 
 $ b $（尺码：9）
黑色{4，4}（d：3）
 +黑色{2,2}（d：2）
 +黑色{1，1}（d：1）
 + 
 + 
 +黑色{3，3}（d：1）
 + 
 + 
 +黑色{6,6}（d：2）
 +黑色{5,5}（d：1）
 + 
 + 
 +红色{8,8}（ d：2）
 + black {7,7}（d：1）
 + 
 + 
 + black {9，9}（d：1）
 + 
 + 
 
 
（尺码：10）
黑色{4，4}（d：3）
 +黑色{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）
 + 
 + 
  

解决方案

我把所有东西都写在一张餐巾纸上，然后想出来。对于红黑树，你不需要跟踪左边节点的数量，因为如果它是正确的偏差（应该是），那么左节点的数量将总是形成一个mersenne系列（1,3,7,15,31 .. 。）或 2 ^ depth -1 。

记住这一点，我们可以写下递归获得的逻辑节点。这是灵药的正确实施。对于包裹

  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）
结束
 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 |>一轮
  

I have a right-biased red-black tree structure that will always be some shape given the total number of elements.

Given the size of elements k and an ordinal element n, how to write a function to get the n-th element in the tree of size k?

(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)
        + 
        + 

解决方案

I wrote everything down on a napkin and figured it out. For red black tree you do not need to track the number of nodes on the left because if it's right biased (should be) then the number of left nodes will always form a mersenne series ( 1, 3, 7, 15, 31 ...) or 2^depth -1.

With that in mind we can write down the logic to recursively get the node. This is the correct implementation in elixir. For 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

这篇关于访问具有序号索引的树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！