Golang LLRB (左傾紅黑樹) 範例與 B-Tree (B 樹) 範例

最近在研究 Golang 剛好紀錄一下 Sample Code 給需要使用的人

LLRB (左傾紅黑樹)

GoLLRB Library https://pkg.go.dev/github.com/petar/GoLLRB

如果想要直接執行也可以使用 Go Playground

package main

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

func main() {
	tr := llrb.New()

	for i := llrb.Int(0); i < 10; i++ {
		tr.ReplaceOrInsert(i)
	}

	fmt.Println("len:       ", tr.Len())
	fmt.Println("get3:      ", tr.Get(llrb.Int(3)))
	fmt.Println("get100:    ", tr.Get(llrb.Int(100)))
	fmt.Println("del4:      ", tr.Delete(llrb.Int(4)))
	fmt.Println("del100:    ", tr.Delete(llrb.Int(100)))
	fmt.Println("replace5:  ", tr.ReplaceOrInsert(llrb.Int(5)))
	fmt.Println("replace100:", tr.ReplaceOrInsert(llrb.Int(100)))
	fmt.Println("min:       ", tr.Min())
	fmt.Println("delmin:    ", tr.DeleteMin())
	fmt.Println("max:       ", tr.Max())
	fmt.Println("delmax:    ", tr.DeleteMax())
	fmt.Println("len:       ", tr.Len())
}

執行結果

len:        10
get3:       3
get100:     <nil>
del4:       4
del100:     <nil>
replace5:   5
replace100: <nil>
min:        0
delmin:     0
max:        100
delmax:     100
len:        8

Program exited.

B-Tree (B 樹)

Google 開源的 Golang BTree https://pkg.go.dev/github.com/google/btree

如果想要直接執行也可以使用 Go Playground

package main

import (
	"fmt"
	"github.com/google/btree"
	"flag"
)

var btreeDegree = flag.Int("degree", 32, "B-Tree degree")

func main() {
	tr := btree.New(*btreeDegree)
	for i := btree.Int(0); i < 10; i++ {
		tr.ReplaceOrInsert(i)
	}
	fmt.Println("len:       ", tr.Len())
	fmt.Println("get3:      ", tr.Get(btree.Int(3)))
	fmt.Println("get100:    ", tr.Get(btree.Int(100)))
	fmt.Println("del4:      ", tr.Delete(btree.Int(4)))
	fmt.Println("del100:    ", tr.Delete(btree.Int(100)))
	fmt.Println("replace5:  ", tr.ReplaceOrInsert(btree.Int(5)))
	fmt.Println("replace100:", tr.ReplaceOrInsert(btree.Int(100)))
	fmt.Println("min:       ", tr.Min())
	fmt.Println("delmin:    ", tr.DeleteMin())
	fmt.Println("max:       ", tr.Max())
	fmt.Println("delmax:    ", tr.DeleteMax())
	fmt.Println("len:       ", tr.Len())
}

執行結果

len:        10
get3:       3
get100:     <nil>
del4:       4
del100:     <nil>
replace5:   5
replace100: <nil>
min:        0
delmin:     0
max:        100
delmax:     100
len:        8

參考資料

• https://pkg.go.dev/github.com/petar/GoLLRB
• https://pkg.go.dev/github.com/google/btree
• https://zh.wikipedia.org/wiki/左倾红黑树
• https://zh.wikipedia.org/wiki/B树