Path: csiph.com!news.mixmin.net!news.albasani.net!.POSTED!not-for-mail
From: Melzzzzz <mel@zzzzz.com>
Newsgroups: comp.programming
Subject: Re: Splay trees
Date: Fri, 18 Sep 2015 13:12:18 +0200
Organization: albasani.net
Lines: 31
Message-ID: <20150918131218.5d20466d@maxa-pc>
References: <mtccfq$4b3$1@dont-email.me> <20150916205922.39163e69@maxa-pc> <mteoiq$7f2$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
X-Trace: news.albasani.net 4+/mA+uvwr58ZkUXg90oSVAmPhxAnv9319e9ouIAERFx081RQD+7KO1501B+PNgEHwnDD/30rE499zqs9FcosVoFl3KjH2/ZgQFuXGli8gyxk/8uJXDWds/vHrbvJmLi
NNTP-Posting-Date: Fri, 18 Sep 2015 11:12:18 +0000 (UTC)
Injection-Info: news.albasani.net; logging-data="DV/Zy/IIed6Df5+H9TJx0OruPp6Zu3s5jam7VaHLJTQ+hzABoAGgj5BIKk13N7eTy8QcWODKn7a8t3k8pn1r9nrW8m6nO4XFmWnGHBMc3jvffeWFhiJI1ItwitVeVPg1"; mail-complaints-to="abuse@albasani.net"
X-Newsreader: Claws Mail 3.12.0 (GTK+ 2.24.28; x86_64-unknown-linux-gnu)
Cancel-Lock: sha1:iaTJslDKajJkeJe95kwII8ZMkvg=
Xref: csiph.com comp.programming:5874

On Thu, 17 Sep 2015 17:10:52 +0100
"James Harris" <james.harris.1@gmail.com> wrote:

> "Melzzzzz" <mel@zzzzz.com> wrote in message 
> news:20150916205922.39163e69@maxa-pc...
> > On Wed, 16 Sep 2015 19:32:12 +0100
> > "James Harris" <james.harris.1@gmail.com> wrote:
> >
> >> Anyone here using splay trees?
> >>
> >>   https://en.wikipedia.org/wiki/Splay_tree
> >>   https://www.youtube.com/watch?v=G5QIXywcJlY
> 
> ...
> 
> > When tree is in the form of linked list (in order insert) moving up
> > to the root has better access performance for sure...
> 
> AIUI that would result in a well-balanced tree but it is a special
> case. I suppose a full tree traversal would also benefit from the
> standard splaying of each referenced node right up to the root. In
> fact, any access which is near a previous access would probably
> benefit from that action.
> 
> However, for random access having to splay each node up to the root
> may be unnecessarily slow because the tree is being widely
> restructured each time.

Splay tree is not good choice for random access, anyway.