平衡二叉树的索引函数

Question

我有问题，我不知道如何决定我的函数indexJ必须在每个步骤中选择什么子树遍历我的平衡二叉树 - JoinList。

这个想法是给缓存每个子树的大小（数据元素的数量）。然后可以在每个步骤中使用它来确定所需的索引是在左边还是右边。

我有这样的代码：

data JoinList m a = Empty 
        | Single m a 
        | Append m (JoinList m a) (JoinList m a) 
        deriving (Eq, Show) 

newtype Size = Size Int 
    deriving (Eq, Ord, Show, Num) 

getSize :: Size -> Int 
getSize (Size i) = i 

class Sized a where 
    size :: a -> Size 

instance Sized Size where 
    size = id 

instance Monoid Size where 
    mempty = Size 0 
    mappend = (+) 

我写功能：

tag :: Monoid m => JoinList m a -> m 
tag Empty = mempty 
tag (Single x dt) = x 
tag (Append x l_list r_list) = x 

(+++) :: Monoid m => JoinList m a -> JoinList m a -> JoinList m a 
(+++) jl1 jl2 = Append (mappend (tag jl1) (tag jl2)) jl1 jl2 

indexJ :: (Sized b, Monoid b) => Int -> JoinList b a -> Maybe a 
indexJ _ Empty = Nothing 
indexJ i jl | i < 0 || (i+1) > (sizeJl jl) = Nothing 

    where sizeJl = getSize . size . tag 

indexJ 0 (Single m d) = Just d 
indexJ 0 (Append m (Single sz1 dt1) jl2) = Just dt1 
indexJ i (Append m jl1 jl2) = if (sizeJl jl1) >= (sizeJl jl2) 
           then indexJ (i-1) jl1 
           else indexJ (i-1) jl2 

    where sizeJl = getSize . size . tag 

功能tag和(+++)运作良好，但我需要完成indexJ功能，它必须返回从第i个元素我的JoinList树，i = [0..n]

我的功能indexJ working wrong =） 如果我有空树 - 它是（大小0） 如果我有单一（大小1）“数据” - 它的（大小1） 但如果我有附加（大小2）（单（大小1）'k '）（单（1）''''）我必须选择哪个分支？ i-1 = 1，我有两个分支，每个分支有1个数据元素。

UPDATE：如果有人需要采取抗摔功能JoinList的树木 我让它：

dropJ :: (Sized b, Monoid b) => Int -> JoinList b a -> JoinList b a 
dropJ _ Empty = Empty 
dropJ n jl | n <= 0 = jl 
dropJ n jl | n >= (getSize . size $ tag jl) = Empty 
dropJ n (Append m jL1 jL2) 
    | n == s1 = jL2 
    | n < s1 = (dropJ n jL1) +++ jL2 
    | otherwise = dropJ (n - s1) jL2 
       where s1 = getSize . size $ tag jL1 

takeJ :: (Sized b, Monoid b) => Int -> JoinList b a -> JoinList b a 
takeJ _ Empty = Empty 
takeJ n jl | n <= 0 = Empty 
takeJ n jl | n >= (getSize . size $ tag jl) = jl 
takeJ n (Append m jL1 jL2) 
    | n == s1 = jL1 
    | n < s1 = (takeJ n jL1) 
    | otherwise = jL1 +++ takeJ (n - s1) jL2 
       where s1 = getSize . size $ tag jL1 

Answer 1

我想在

Append m joinList1 joinList2 

的joinList1的元素是为了占据第一指标，其次是joinList2的元素。

然后，索引

indexJ i (Append m jL1 jL2) 

你要比较i到jL1大小的时候 - 我们称之为s1。然后的jL1元素占据索引0到s1 - 1，和jL2元件占据的索引从s1到s1 + s2 - 1，因此

indexJ :: (Sized b, Monoid b) => Int -> JoinList b a -> Maybe a 
indexJ _ Empty = Nothing 
indexJ i (Single m d) 
    | i == 0 = Just d 
    | otherwise = Nothing 
indexJ i (Append m jL1 jL2) 
    | i < 0  = Nothing 
    | i >= getSize (size m) = Nothing  -- optional, more efficient to have it 
    | i < s1 = indexJ i jL1 
    | otherwise = indexJ (i - s1) jL2 
     where 
     s1 = getSize . size $ tag jL1 

如果指数比s1较小，我们期待在第一子列表，否则在第二。

Answer 2

通常你会用数字的序列，而不仅仅是一个单一的编码在树形结构中的位置数。例如（假设索引从0开始）：

[] -- empty sequence = root of tree 
[0,1] -- first follow the first child, then the second child 
[0,0,0] -- go 3 levels down in the leftmost branch 

这会使索引函数的实现更加简单。