From: Hans Reiser <reiser@namesys.com>
To: "Alexander G. M. Smith" <agmsmith@rogers.com>
Cc: reiserfs-list@namesys.com
Subject: Re: Split Trees (my design, similar to binary treaps)
Date: Thu, 22 May 2003 21:16:15 +0400 [thread overview]
Message-ID: <3ECD05DF.8090107@namesys.com> (raw)
In-Reply-To: <11604422062-BeMail@cr593174-a>
Alexander G. M. Smith wrote:
>Hans Reiser wrote on Thu, 22 May 2003 19:30:16 +0400:
>
>
>>Forgive me for asking some bonehead questions.....
>>
>>Are skip lists height balanced? (All paths to the leaves are equal?)
>>
>>
>
>Only on the average, at least in the original skip list algorithm. The
>height is determined randomly when the node is created; there is no
>rebalancing. The random distribution is defined as you would expect,
>50% of the nodes have 1 level, 25% have 2 levels, ... 0.5**n of the
>nodes have n levels. Surprisingly, this works fairly well.
>
>- Alex
>
>
>
>
To have a level means to be on that level or lower?
--
Hans
next prev parent reply other threads:[~2003-05-22 17:16 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-05-08 4:22 Split Trees (my design, similar to binary treaps) Kevin Bealer
2003-05-22 15:30 ` Hans Reiser
2003-05-22 16:09 ` Alexander G. M. Smith
2003-05-22 17:16 ` Hans Reiser [this message]
2003-05-22 20:21 ` Alexander G. M. Smith
2003-05-22 22:48 ` Hans Reiser
2003-05-22 23:27 ` Alexander G. M. Smith
2003-05-23 18:56 ` Kevin Bealer
2003-06-02 17:33 ` Hans Reiser
2003-06-04 4:54 ` Kevin Bealer
2003-05-23 19:24 ` Kevin Bealer
2003-06-03 17:49 ` Hans Reiser
2003-06-04 5:17 ` Enrique Perez-Terron
2003-06-04 9:40 ` Hans Reiser
2003-06-05 22:34 ` Enrique Perez-Terron
2003-06-08 5:26 ` Kevin Bealer
2003-06-09 15:33 ` Enrique Perez-Terron
2003-06-08 5:20 ` Kevin Bealer
2003-06-04 5:22 ` Kevin Bealer
2003-06-04 9:44 ` Hans Reiser
2003-06-08 5:17 ` Kevin Bealer
2003-05-27 1:38 ` Enrique Perez-Terron
2003-05-27 20:47 ` Hans Reiser
2003-05-28 16:44 ` Kevin Bealer
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=3ECD05DF.8090107@namesys.com \
--to=reiser@namesys.com \
--cc=agmsmith@rogers.com \
--cc=reiserfs-list@namesys.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.