stathat重疊treap包？

根據這一link stathat採用與他們treap重疊：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]

來源

2013-04-18 Alfred

我找到了一個解決方案，使用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的treap。

來源

2013-04-19 04:27:38 Alfred

我開始會爲stathat樹堆代碼測試第一名： 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-28 16:20:25 lizard

stathat重疊treap包？

回答

相關問題