top down 2-3-4 mode does not correctly delete

[kortschak]

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?

[petar]

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
reply@reply.github.com
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:
#7

[kortschak]

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.

[kortschak]

I have a failing case for GoLLRB here https://gist.github.com/3505575