Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5877
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: Splay trees |
| Date | 2015-09-18 17:30 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <mthe2l$ia8$1@dont-email.me> (permalink) |
| References | (1 earlier) <20150916205922.39163e69@maxa-pc> <mteoiq$7f2$1@dont-email.me> <20150918131218.5d20466d@maxa-pc> <mth1uo$15v$1@dont-email.me> <20150918081935.613@kylheku.com> |
On 18/09/15 16:32, Kaz Kylheku wrote: > On 2015-09-18, Richard Heathfield <rjh@cpax.org.uk> wrote: >> On 18/09/15 12:12, Melzzzzz wrote: >> >>> Splay tree is not good choice for random access, anyway. >> >> It depends what you mean by "random", really. >> >> Generally, when we say "random access", we don't actually mean it. We >> mean "arbitrary access" - that is, data-driven access. > > Richard, it is this: when we say "random access" it is simply a phrase > that we invented out of the need to have a contrast with "sequential access". Yes, I know, but I felt it worth clarifying because, to at least some people, the word "random" does convey the idea of, well, rand() (although yes I know, that isn't random either!). > Sequential access is a situation whereby we must visit all of the predecessors > of the elements of a sequence before obtaining the one we want. > > Random access is any retrieval situation in which ... that isn't the case. Agreed. <snip> > Also, the main point, really, is not that the splay tree brings frequently > accessed items toward the root (which undeniably does shave cycles > when there is locality of reference) but that this continuous "hemming > up of the skirt" of the splay tree prevents it from becoming unbalanced, You see? I learned something, which is nice. <snip> -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-16 19:32 +0100
Re: Splay trees Melzzzzz <mel@zzzzz.com> - 2015-09-16 20:59 +0200
Re: Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-17 17:10 +0100
Re: Splay trees Melzzzzz <mel@zzzzz.com> - 2015-09-18 13:12 +0200
Re: Splay trees Richard Heathfield <rjh@cpax.org.uk> - 2015-09-18 14:03 +0100
Re: Splay trees Kaz Kylheku <kaz@kylheku.com> - 2015-09-18 15:32 +0000
Re: Splay trees Richard Heathfield <rjh@cpax.org.uk> - 2015-09-18 17:30 +0100
Re: Splay trees Melzzzzz <mel@zzzzz.com> - 2015-09-19 01:10 +0200
Splay trees Chad <cdalten@gmail.com> - 2015-09-17 21:32 -0700
Re: Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-18 11:28 +0100
Re: Splay trees Chad <cdalten@gmail.com> - 2015-09-18 15:59 -0700
Re: Splay trees "A. Bolmarcich" <aggedor@earl-grey.cloud9.net> - 2015-09-21 13:33 -0500
Re: Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-22 18:41 +0100
Re: Splay trees "A. Bolmarcich" <aggedor@earl-grey.cloud9.net> - 2015-09-23 13:03 -0500
Re: Splay trees "James Harris" <james.harris.1@gmail.com> - 2015-09-23 19:20 +0100
Re: Splay trees "A. Bolmarcich" <aggedor@earl-grey.cloud9.net> - 2015-09-23 15:33 -0500
Re: Splay trees James Harris <james.harris.1@gmail.com> - 2015-09-25 13:29 +0100
csiph-web