Sign in to follow this  
Henrip

Deterministic Skip List

Recommended Posts

Henrip    116
One of my professors had briefly mentioned that no one has ever written, or at least posted to the internet, code for the delete function for a deterministic skip list. He says some other professors "say" they have, but have never actually produced the code for it. Is this true? Has the delete function code ever been written or posted somewhere? Thanks, Henri

Share this post


Link to post
Share on other sites
frob    44969
You need to go have some discussions with your professor.

There is some subtlety and nuance in his claim, and you either did not understand it or did not quote it. Either that or he got the claim wrong, which I doubt.

Very important words you are missing are "amortized", "demonstrated", and "expected". You also forgot the details of logarithmic costs.




Yes, it is true that there are some theories about skip lists which have not been implemented and/or published yet. It is a fun data structure with some interesting properties. It is fairly new, so it shouldn't be surprising that it isn't fully researched.

Share this post


Link to post
Share on other sites
Henrip    116
I think you misunderstand the depth of the question. I was merely pondering whether deletion code for the d. skip list has been published on the internet or a journal; In one of my books, Weiss implemented everything but the deletion function.

Thanks,
Henri

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this