MESSAGE
| DATE | 2015-05-06 |
| FROM | Ruben Safir
|
| SUBJECT | Re: [LIU Comp Sci] Fibonacci trees
|
From owner-learn-outgoing-at-mrbrklyn.com Wed May 6 03:08:36 2015
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id 0B6CC1612E1; Wed, 6 May 2015 03:08:36 -0400 (EDT)
Delivered-To: learn-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id F2C591612ED; Wed, 6 May 2015 03:08:35 -0400 (EDT)
Delivered-To: learn-at-mrbrklyn.com
Received: from mailbackend.panix.com (mailbackend.panix.com [166.84.1.89])
by mrbrklyn.com (Postfix) with ESMTP id 603901612E1
for ; Wed, 6 May 2015 03:08:11 -0400 (EDT)
Received: from [10.0.0.19] (www.mrbrklyn.com [96.57.23.82])
by mailbackend.panix.com (Postfix) with ESMTPSA id 07F5112EF2;
Wed, 6 May 2015 03:08:10 -0400 (EDT)
Message-ID: <5549BDDA.9050106-at-panix.com>
Date: Wed, 06 May 2015 03:08:10 -0400
From: Ruben Safir
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
MIME-Version: 1.0
To: "Jose A. Rodriguez"
Subject: Re: [LIU Comp Sci] Fibonacci trees
References: <55498808.7030608-at-panix.com> <55498C6D.4070404-at-my.liu.edu> <5549B432.8020406-at-panix.com> <5549BB3A.7050804-at-panix.com>
In-Reply-To: <5549BB3A.7050804-at-panix.com>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Sender: owner-learn-at-mrbrklyn.com
Precedence: bulk
Reply-To: learn-at-mrbrklyn.com
The catch seems to be that it says in the notes, When m is EVEN for the
top down insertion etc etc.
I don't see a method for when m is odd.
thinking about it, if I was going to design this, I would say when the m
is odd, I would use a medium that is the side of the current track of
the new key. If the key, for example is going left, then the medium
should be m%2 but if the new key is going to the right of the medium,
then I would promote m%2 + 1. This would guarantee the necessary
rotation of the root.
Ruben
On 05/06/2015 02:56 AM, Ruben Safir wrote:
> Look at it this way for an example
>
> Add 10 14 16 1 102 92 35 7 58 22 61 4 72 into a 3m btree
> You end up with leafs on different levels
>
> 10 14
> ~~~~~~~
> 10
> 1 14 |16
> ~~~~~~~~~~ adding 102
> 10, 14
> 1 16, 102
> ~~~~~~~~~~~adding 92
>
> 10 <=== where do I put 1? under 14? that would be the wrong
> side
> 1 14|16
> 92 |102 Now all my leaves are NOT on the same level.
>
>
> O n 05/06/2015 02:26 AM, Ruben Safir wrote:
>> Good Morning
>>
>> I'm looking at the definition for B-trees and looking at it now, it has
>> confused me.
>> In this context, for one thing, I'm not sure what a leaf is. A leaf has
>> to have NO children, correct?
>>
>> So the rest of this definition leaves me scratching my head because as
>> you add your first, second, third, etc, node to the B-Tree, it is not
>> possible to satisfy the requirements.
>>
>> 1- The root is either a leaf, or non-leaf and has anywhere between 2 and
>> M children.
>>
>> so, you make it simple, lets say M = 5
>>
>> And we are adding, regardless of the method,
>>
>> 2 63 15 81 22 10
>>
>> So we add the first entry
>>
>> 2
>> if is a leaf - NO CHILDERN
>> 2 63
>>
>> still a leaf - NO CHILDREN
>> 2|15|63
>>
>> s till a leaf - No Children
>> 2|15|63|81
>>
>> adding 22, from the Top Down, just pick a method
>> spilt the root
>>
>> 15
>> 2 16 |63|81
>>
>> then find the key location
>>
>> Not the root is non-leaf and has 2 children. so it is FINALLY in
>> complience/
>>
>> But then there is the problem with definition 3:
>>
>> All the leaves appear in the same level and also contain at least [m/2]
>> -1 keys, with the exception of the root, which if it is a leaf it can
>> contain anywhere between 1 and m - 1 keys. with m=5 it is hard to
>> demonstration but eventually, if a Leaf fills up, it will be split
>>
>>
>
|
|
