sakeven/rbtree

Red-Black Tree written in Go with generics(100% test coverage)

rbtree's Issues

范围查询如何支持

获取 values = fn（start，end）

2 little mistakes

Hi, I think I found 2 little mistakes in your code

line 281: t.root = x
should be: t.root = y

line 153: z.parent.parent.color = BLACK
should be: z.parent.parent.color = RED

panic: runtime error: invalid memory address or nil pointer dereference

// this code crash -- randomly add and remove keys

ltree := NewTree();
var larr [] int;

for i := 0; i < 1000000; i++ {
lrand := rand.Intn(30);
if (lrand > 25) {
if len(larr) > 0 {
lrand1 := rand.Intn(len(larr));
ltree.Delete(key(larr[lrand1]));
larr = remove(larr, lrand1);
fmt.Printf("delete:[%d] len:[%d]\n", lrand1, len(larr))
}
} else {
lrand1 := rand.Intn(1000000);
larr = append(larr, lrand1);
ltree.Insert(key(lrand1), lrand1);
fmt.Printf("insert:[%d] len:[%d]\n", lrand1, len(larr));
}
}

Test coverage

For algorithms I expect test coverage to be about 100%. However current test coverage is 74.4%. Looking at more detailed output you can see some algorithm branches are untested. This is a huge factor when you choose a library on GitHub.

go test -coverprofile=coverage.out
go tool cover -html=coverage.out

Segfault during Delete

Try this test:

tree := NewTree()
tree.Insert(key(4), "1qa")
tree.Insert(key(2), "2ws")
tree.Insert(key(3), "3ed")
tree.Insert(key(1), "4rf")
tree.Insert(key(8), "5tg")
tree.Insert(key(5), "6yh")
tree.Insert(key(7), "7uj")
tree.Insert(key(9), "8ik")
tree.Delete(key(1))
tree.Delete(key(2))

We will receive runtime error at line 197 because x is nil.