Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #5874

Re: Splay trees

From Melzzzzz <mel@zzzzz.com>
Newsgroups comp.programming
Subject Re: Splay trees
Date 2015-09-18 13:12 +0200
Organization albasani.net
Message-ID <20150918131218.5d20466d@maxa-pc> (permalink)
References <mtccfq$4b3$1@dont-email.me> <20150916205922.39163e69@maxa-pc> <mteoiq$7f2$1@dont-email.me>

Show all headers | View raw

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.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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