Re: Missing Tomes of Data Structures

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

jehugaleahsa@xxxxxxxxx wrote:
I have spent the last week or more looking for an implementation (open
source) for a deterministic skip lists. I am currently approaching the
completion of a data structure library I am implementing.

I have a randomized skip list completed; however, I require a
deterministic skip list. No matter how hard I look I can't seem to
find an implementation, or even the details to make my own.

In addition, there is a data structure called a forward-balancing B-
Tree that lets implementors lock sub-trees instead of the entire tree
itself. It does this by ensuring the tree is balanced ahead of time so
it can lock as little as possible.

Any ideas?

Google?

I admit, I had not heard of either. Google provides nothing relevant when using "forward-balancing b-tree" as the search time, so I'm wondering if you got the term right. You say one exists; why do you think it does? Why does it appear that there's no one else on the Internet who's ever heard of it?

As far as the skip-list goes, as near as I can tell from the descriptions of the algorithm (including Pugh's own paper where he published it), randomization is a key element of the data structure. When you write "deterministic", what exactly is it that you want to be deterministic about the skip-list? And what sort of trouble are you having in applying that goal to your current implementation?

For both of your questions above, it's almost as if you are asking for help implementing something that doesn't (or can't) exist. If that's actually what's going on, then obviously you won't get an answer. If it's not what's going on, then at the very least there seems to be some ambiguities and/or inaccuracies in your question that you might want to explore, to see if you can rephrase the question in a way more likely to get the help you need.

Pete
.

Relevant Pages

  • Re: Link List
    ... finished the linked list data structure. ... might do a tree. ... was on Linked Lists, ...
    (comp.lang.cpp)
  • Re: ADTs
    ... That's a pretty fundamental description of how lists ... as an abstract data type before; it was to me simply a data structure ... you'd use a "tree" ADT. ...
    (comp.programming)
  • Missing Tomes of Data Structures
    ... source) for a deterministic skip lists. ... there is a data structure called a forward-balancing B- ... Tree that lets implementors lock sub-trees instead of the entire tree ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Why cons *pairs*?
    ... So why are lists used as the basis of program representation, ... a legal data structure isomorphic to the parse tree of the program, ... structures are most naturally expressed by that syntax?" ... CONS-based lists support these fairly well. ...
    (comp.lang.scheme)
  • Re: terminological obscurity
    ... anomolous why Guido didn't say what he meant himself. ... the distinction between homogenous data and a homogenous ... >> that at the Object level, we are at lists of Objects and tuples of ... >in Python but a recursive data structure. ...
    (comp.lang.python)