Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #5875
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Newsgroups | comp.programming |
| Subject | Re: Splay trees |
| Date | 2015-09-18 14:03 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <mth1uo$15v$1@dont-email.me> (permalink) |
| References | <mtccfq$4b3$1@dont-email.me> <20150916205922.39163e69@maxa-pc> <mteoiq$7f2$1@dont-email.me> <20150918131218.5d20466d@maxa-pc> |
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. Consider, for example, a tree that uses a postcode (or zipcode, if you prefer) as its key. Let's say, for the sake of argument, that we don't envisage creating or deleting any postcodes before going-home time, so we're only concerned about retrieval. There are around 1.7 million post codes in the UK. So we can readily see that a perfectly balanced binary search tree will have a depth of ceil(log2(1700000)), i.e. 21. But if most of our customers are local, we are likely to need only a few hundred postcodes that we access frequently (but randomly!), with the rest of the postcodes being used hardly at all - just an occasional long-distance customer. In a perfectly balanced binary tree, a good few of those postcodes are going to be in the very bottom branches of the tree. In a splay tree, they will quickly be brought close to the root, where they will (more or less) stay, thus resulting in significantly quicker searches. So a splay tree can actually be an excellent choice for random access. There is no substitute, however, for Knowing Your Data, and choosing data structures and algorithms that are an appropriate match for the characteristics of your data. -- 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