ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
Notices
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
Suggestion:
1. Try to get as far as you can with the problem.
2. Post some code (or even pseudo code) to let us know you made some minimal effort
3. Ask a specific question about exactly where you're "stuck".
create(node I,item)
{
if(I!=0)
{
a[I]=item
optiony/n) node I has left subtree
if(option=y)
create(2*I,nextitem)
else
create(0,NULL)
optiony/n) node I has right subtree
if(option=y)
create(2*I+1,nextitem)
else
create(0,NULL)
}
}
OK, here's a copy of my homework assignment on what I suspect is a similar (the same?) topic from a couple of years ago:
Quote:
Binary searching B-tree blocks for keys is an important for DBMS systems.
The keys are arrays, and are contiguous in the B-tree block.
Lower performance systems, e.g., Oracle, store the keys as arrays of bytes.
Higher performance DBMS systems, e.g. MKF, store the keys as arrays of
longwords: When comparing the target key against a key in the B-tree block,
you must do 4 times as many compares when the keys are arrays of bytes
compared to the case when the keys are arrays of longwords. Therefore, in
this exercise the keys are arrays of longwords. (The most significant
longword is first.)
In a B-tree block, a key is the value of the key column(s) followed by an
address pointer. The address pointer points to a lower level B-tree block,
or to a row in a data block. In this exercise as in MKF, the key arrays are
fixed length.
When you search for a target key, you may or may not find it. If you find
it, you need to find the first duplicate, if there are duplicates.
If you don't find it, you need the index of the point at which you should
insert the target key (after first shifting all the keys from that point
onward up by one key position).
Write a binary search routine to search a B-tree block for a target key that
satisfies the following signature:
The array a[] holds the keys. key[i] starts at a[i * key_lw]. The index
of the first key is 0 (and it starts at a[0]), and the index of the last key
is n - 1 (and it starts at a[(n-1) * key_lw]).
n >= 0.
The key_lw parameter is the number of longwords in a key. 1 <= key_lw <= 4.
The target_p parameter points to the first longword of the target key.
If the key is found, 1 is returned, else 0.
If the key is found, *index_p is set to the index of the first key
in the array that has a value identical to the target key (i.e., duplicate
keys are allowed in the array).
If the key is not found, *index_p is set to the insertion point (i.e.,
the index of the key minimally greater than the target key), or, if the target
key is greater than all the keys in the array a[], *index_p is set to 'n'.
Your goal is to write a the fastest B-tree key search routine in the world.
That is, no one can write a faster routine.
The key_lw parameter is the number of longwords (unsigned 32 bit integers)
per key. This value can range from one to four. Your routine should work
for any n >= 0.
Put the binary_search routine in the attached file called "binsearch.c".
Do not create your own file. Edit the attached file.
I suppose I could post my solution, verbatim.
But instead, let me ask these questions:
1. What exactly does your "create()" function do?
2. Where exactly does the "option" parameter come from?
... and ...
3. "a[]" is an array of exactly what?
(or, to put it differently: "what exacty is the definition of 'item'?"
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.