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

Groups > comp.programming > #5870

Re: Splay trees

Path csiph.com!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From "James Harris" <james.harris.1@gmail.com>
Newsgroups comp.programming
Subject Re: Splay trees
Date Thu, 17 Sep 2015 17:10:52 +0100
Organization A noiseless patient Spider
Lines 33
Message-ID <mteoiq$7f2$1@dont-email.me> (permalink)
References <mtccfq$4b3$1@dont-email.me> <20150916205922.39163e69@maxa-pc>
Mime-Version 1.0
Content-Type text/plain; format=flowed; charset="iso-8859-1"; reply-type=original
Content-Transfer-Encoding 7bit
Injection-Date Thu, 17 Sep 2015 16:08:58 +0000 (UTC)
Injection-Info mx02.eternal-september.org; posting-host="5e0a710bc226c10c29b9c915709f9d40"; logging-data="7650"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19NQSw9eorGAmf5QvymjkXhtf/Hu3qdkaQ="
X-MimeOLE Produced By Microsoft MimeOLE V6.00.2900.6157
X-Newsreader Microsoft Outlook Express 6.00.2900.5931
Cancel-Lock sha1:NXTJomKaYiYSjNMRzIEA3aFef8M=
X-Priority 3
X-MSMail-Priority Normal
Xref csiph.com comp.programming:5870

Show key headers only | View raw

"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.

I would have thought that splaying a node up just a level or two would 
work fairly well for sequential/local access (though not as well as 
splaying it to the root) but it would work better for random access. It 
would keep the tree balanced but not restructure it each time. Or so it 
seems....

James

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