petar
top down 2-3-4 mode does not correctly delete
Hi,
I noticed this because I've been writing an llrb, and on my own project I can't get deletion to test as correct when using top down 2-3-4 insertion (see post on golang-nuts).
I wanted to check my sanity (I've pored over the code so many times to see if I'm doing something stupid), so I inserted one of my failing deletion tests into GoLLRB and it gives equivalent behaviour (passes on bottom up 2-3 and fails catastrophically on top down 2-3-4).
func TestRandomInsertionDeletion(t *testing.T) {
count, max := 100000, 1000
tree := New(IntLess)
for i := 0; i < count; i++ {
if rand.Float64() < 0.5 {
tree.ReplaceOrInsert(rand.Intn(max))
}
if rand.Float64() < 0.5 {
tree.Delete(rand.Intn(max))
}
}
}
The test is obviously very vicious, but is fine with the standard 2-3 GoLLRB insertion mode.
Any ideas?
Sorry I've taken awhile.
I am currently too busy to look into this. Mainly because if 2-3 trees work, I can't justify the time to look into 2-3-4 trees, unless you can tell me some reason why one might prefer them.
Otherwise, I should say that the 2-3 version has been in production for months know, processing gigabytes per day. So we know that is solid.
P
On 3 July 2012 17:58, kortschak [email protected] wrote:
Hi,
I noticed this because I've been writing an llrb, and on my own project I can't get deletion to test as correct when using top down 2-3-4 insertion (see post on golang-nuts).
I wanted to check my sanity (I've pored over the code so many times to see if I'm doing something stupid), so I inserted one of my failing deletion tests into GoLLRB and it gives equivalent behaviour (passes on bottom up 2-3 and fails catastrophically on top down 2-3-4).
func TestRandomInsertionDeletion(t *testing.T) { count, max := 100000, 1000 tree := New(IntLess) for i := 0; i < count; i++ { if rand.Float64() < 0.5 { tree.ReplaceOrInsert(rand.Intn(max)) } if rand.Float64() < 0.5 { tree.Delete(rand.Intn(max)) } } }The test is obviously very vicious, but is fine with the standard 2-3 GoLLRB insertion mode.
Any ideas?
Reply to this email directly or view it on GitHub: https://github.com/petar/GoLLRB/issues/7
I have a fix implemented in biogo.llrb that is a relatively minor change. It may well not be worth the effort though - inserts and deletes are worse, though retrieval is very slightly faster (benchmark comparisons are available in the commit message).
Can I suggest that if you don't implement the fix, code referring to TD2-3-4 be removed or marked as unsafe for use with deletion?
Also, I have found in by own implementation that deletion from non-uniquely inserted tree results in tree invariant contradiction. I haven't found a way around this except to make all insertions unique by adding a unique identifier as a tie-breaker. This bug is noted here.
Since your delete code is substantively algorithmically identical to mine, and the effective approach to non-replacing insertion is similar to mine, GoLLRB probably will have the same behaviour in this case.
Initially, breaking the tree invariants does not cause a problem, but will eventually result in nil pointer dereference in flipColor or the rotate operations because they assume the invariants hold. You may want to have a look at this since you provide explicit non-replacing insertion.