4

根据此链接stathat 使用与他们的treap重叠：

GoLLRB 很棒，您没有理由切换。我们认为 treaps 背后的想法是解决我们问题的优雅方案，因此我们实现了它。我们喜欢 GoLLRB 提供的接口，所以我们在实现中模仿了它。

我们添加到 treap 包中的一件事是允许您使用重叠函数进行迭代，例如，您可以获得 [3,9) 中的所有键。我们经常使用它，通常以结构作为键。

帕特里克

我正在使用以下代码，不知道如何继续：

package main

import(
    "reflect"
    "fmt"
    "github.com/stathat/treap"
)

func IntLess(p, q interface{}) bool {
        return p.(int) < q.(int)
}

func BucketOverlap(a, b interface{}) bool {
    return false
}

func main() {
    tree := treap.NewOverlapTree(IntLess, BucketOverlap)
    tree.Insert(5, "a")
    tree.Insert(7, "b")
    tree.Insert(2, "c")
    tree.Insert(1, "d")

    for v := range tree.IterateOverlap([]int{2,5}) {
        fmt.Printf("val: %v\n", v)
    }
}

假设我想获得范围内的键[2,5]=>[c,a]

4

2 回答 2

1

我要开始的第一个地方是 stathat treap 代码的测试： https ://github.com/stathat/treap/blob/master/treap_test.go#L164

似乎您正在做的是在期望一个键时尝试传递一个键。您还尝试对标量（即 int）值进行矢量运算（即范围重叠）。

也许我误解了重叠的点，但我的理解是它的用途是作为区间树：

key1 := []int{1, 3}
key2 := []int{2, 4}
key3 := []int{5, 6}

这些是间隔（低和高）。key1 与 key2 重叠，反之亦然。既不重叠key3。在这种情况下，重叠将很有用（即IterateOverlap([]int{2,3})会给我 key1 和 key2，而IterateOverlap([]int{3,5})将返回所有）。

我不确定您将如何迭代这些条目。也许是这样：

for i := 2; i <= 5; i++ {
  fmt.Printf("val: %v\n", tree.Get(i))
}

再说一次，我没有使用过这个实现，所以如果我叫错了树，请原谅我。

于 2013-04-28T16:20:25.023 回答
0

我找到了使用GoLLRB的解决方案：

package main

import (
    "fmt"
    "github.com/petar/GoLLRB/llrb"
)

type Item struct {
    key     int
    value   string
}

func lessInt(a, b interface{}) bool {
    aa := a.(*Item)
    bb := b.(*Item)
    return aa.key < bb.key
}

func main() {
    tree := llrb.New(lessInt)
    tree.ReplaceOrInsert(&Item{5, "a"})
    tree.ReplaceOrInsert(&Item{7, "b"})
    tree.ReplaceOrInsert(&Item{2, "c"})
    tree.ReplaceOrInsert(&Item{1, "d"})
    //tree.DeleteMin()

    c := tree.IterRangeInclusive(&Item{key: 2}, &Item{key: 5})
    for item := <-c; item != nil; item = <-c {
        i := item.(*Item)
        fmt.Printf("%s\n", i.value)
    }
}

我仍然想知道这是否也可以使用 stathat's treap。

于 2013-04-19T04:27:38.207 回答