Comments (3)
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:
#7
from gollrb.
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.
from gollrb.
I have a failing case for GoLLRB here https://gist.github.com/3505575
from gollrb.
Related Issues (16)
- Sedgewick's misnaming
- I've forked GoLLRB to be quasi-immutable.
- Still active? HOT 4
- Particular data sequence causes inconsistency & panic in llrb
- Anybody who wants to follow this project can reference my fork HOT 4
- please tag formal releases
- please clarify license and copyright of files in "doc" HOT 1
- IterRange can never include the last (Max) element HOT 3
- panic at GoLLRB/llrb/llrb.go:426
- LLRB merge/union algorithm
- Example docs became invalid
- Panic in Delete HOT 1
- Example Code does not compile HOT 1
- serializing llrb with gob causes a runtime error: invalid memory address HOT 4
- Code assumes root node has been set HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from gollrb.