"scorp *" <·········@hotmail.com> writes:
> bonjour, ;-)
>
> Thank you for your answer and your help.
>
> I have read conscientiously your explanation and I believe I have bad
> express my problem. According to the rumours of my friends, our
> teacher have give us a particular B-tree.
>
> I give you an exemple of it (the (x y z) represent a node (or a leaf))
>
> (13)
> (4 10) (30)
> (3) (6 7) (11 12) (15 20) (35 40)
>
> The nodes contain only integers.
In real applications, there's usually a bunch of data associated with
the nodes. A typical use of B-trees is in implementing database
tables, which will commonly have many fields, as with:
ID First name Surname Address Phone
====================================================
1 Chris Browne 123 1st St 555-1212
2 David Browne 456 3rd St 231-2134
And so forth.
Your tree seems to only be storing the keys, and not the other data.
Which isn't a big deal at all; you can always leave the "datum" blank.
Much more importantly, the example that you're providing does _not_
appear to be a B-tree; it appears instead to be a binary tree.
I'd expect a Btree for the above to look more like:
(7 12 20)
(3 4 6) (10 11) (20 40)
(13 15) (30 35)
> By reading your message, I don't understand one thing:
> Only the leaf contain informations? As a matter of fact, the
> structure "b-tree-node" have a slot chidren, a slot parent but not
> slot "datum"?
> May be I don't understand... certainly!
I think there's a bigger misunderstanding.
The data structures that have been outlined have been for B-trees,
where each "node" can potentially contain many elements.
It appears that you may actually be implementing a binary tree, where
each node has exactly _two_ elements.
There are a bunch of variations on B-trees (such B+-trees and
B*-trees) which vary in where the leaves are allowed to be and in the
way splitting policies work. If you're really trying to implement a
B-tree, then you certainly need to consult your instructor and/or text
to verify what policies you need to be using. The sample that you
show up above is _not_ terribly helpful, if the assignment is truly
about B-trees.
> If yes, can you give me, with your data structurs, the
> implementation of a simple tree, as the tree that I write above?
You need to take a step back, and determine if it's really a B-tree
that you need, or a binary tree. That is the _crucial_ question; it's
not worth any other discussion until that is determined.
And I'm going to redirect this back to comp.lang.lisp.
--
(concatenate 'string "cbbrowne" ·@ntlug.org")
http://www3.sympatico.ca/cbbrowne/internet.html
Rules of the Evil Overlord #227. "I will never bait a trap with
genuine bait." <http://www.eviloverlord.com/>
>> (13)
>> (4 10) (30)
>> (3) (6 7) (11 12) (15 20) (35 40)
> The data structures that have been outlined have been for B-trees,
> where each "node" can potentially contain many elements.
> It appears that you may actually be implementing a binary tree, where
> each node has exactly _two_ elements.
No no ! Each node can contain 1, 2 or 3 integers.
If the node contain 1 integer e, this node have two children : one will
contain the integers inferior to e, the other will contain the integers
superior to e.
If the node contain 2 integers e1 and e2, this node have three children :
one contain the integers < e1, the second the integers between e1 and e2,
and the last for the integers > e3.
If the node contain 3 integers, it's the same thing (with four children)
For example :
(10 13 30) ;;; a node with 3 integers so 4 children
(3 4 7) (12) (15 20) (35 40)
The title of the homework is : "administration of a B-tree of integers" (in
French, "gestion d'un B-arbre d'entiers")
So I think the teacher want an implementation of B-tree ;-)
Do your data structures is correct for this work?
If yes, can you implement, with this structures, the B-tree that I write
above?
Thank you for all,
Mathieu