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 02:57:23 2015
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id 07B8C1612E1; Wed, 6 May 2015 02:57:23 -0400 (EDT)
Delivered-To: learn-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id E9B301612ED; Wed, 6 May 2015 02:57:22 -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 3B7B91612E1
for ; Wed, 6 May 2015 02:56:58 -0400 (EDT)
Received: from [10.0.0.19] (www.mrbrklyn.com [96.57.23.82])
by mailbackend.panix.com (Postfix) with ESMTPSA id A8FF6129B9;
Wed, 6 May 2015 02:56:58 -0400 (EDT)
Message-ID: <5549BB3A.7050804-at-panix.com>
Date: Wed, 06 May 2015 02:56:58 -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: learn-at-mrbrklyn.com, "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>
In-Reply-To: <5549B432.8020406-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
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
>
>
|
|
