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:27:26 2015
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id 1F0951612E1; Wed, 6 May 2015 02:27:26 -0400 (EDT)
Delivered-To: learn-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id 0F6B01612ED; Wed, 6 May 2015 02:27:26 -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 4A7991612E1
for ; Wed, 6 May 2015 02:26:59 -0400 (EDT)
Received: from [10.0.0.19] (www.mrbrklyn.com [96.57.23.82])
by mailbackend.panix.com (Postfix) with ESMTPSA id 4E67213D72;
Wed, 6 May 2015 02:26:59 -0400 (EDT)
Message-ID: <5549B432.8020406-at-panix.com>
Date: Wed, 06 May 2015 02:26: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>
In-Reply-To: <55498C6D.4070404-at-my.liu.edu>
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
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
still 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
|
|
