?
Solved

need HELP on 2-3 TREE. i have declaration, but don't know how to make the code.

Posted on 2003-02-19
8
Medium Priority
?
251 Views
Last Modified: 2010-04-15
i have come with with two possible declarations for a 2-3 tree (is it correct?), but don't know how to do the code for INSERT and DELETE; too confusing (given the algorithms out there)... will someone please help me?

/********** DECALARATION 1 **********/

struct inode_leaf {
     enum kind { inode, leaf } knd; /* notes which kind of node the self is */
     union {
          struct inode { /* interior node */
               element_type key1, key2;
               struct inode_leaf *l_child, *m_child, *r_child; /* pointers to left, middle, and right child */
          } in;
          struct leaf {
               element_type info;
               /* other info */
          } lf;
     } un;
} two_three_tree;

/********** DECLARATION 2 **********/

struct leaf {
     element_type info;
     /* other info */
};

struct inode { /*interior node */
     enum { inode, leaf } kind_n; /* notes which kind of node the pointers point to */
     element_type key1, key2;
     union pointer {
          struct leaf *ptr_lf;
          struct inode *ptr_nd;
     } children[3];
};

struct head {
     enum kind { inode, leaf }  kind_h; /* notes which kind of node the pointers point to */
     union pointer {
          struct leaf *ptr_lf;
          struct inode *ptr_nd;
     } ptr;
} two_three_tree;


NOTE: please note w/c declaration you are using. i think i'm more preferable to the 2nd declaration. it saves a lot of storage space since its union consists only of pointers.

0
Comment
Question by:geff_chang
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
8 Comments
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 7983831
Howdy....

Using your first definition may be wasteful of memory, but unless you're going to be building a very large tree, "so what?".

I certainly prefer that to continually recasting pointers.

Besides the Insert() and Delete() functions that you've mentioned, you're also going to need a general routine to traverse the tree.  I suggest that you build Insert(), Traverse(), and Delete(), in that order so you can test the tree you've built before you try and deleting anything.

Insert() is dependent upon the definition of each child node.  In a binary tree, the left node IS the left node because it's smaller, because the node's contained item was on the left, because it came first, or some other definitive reason.  The Insert() into your tree will need to know how and why to add a child in each of the positions.  (You didn't indicate this in your question.)

Actually performing the insert is easy.  Ignoring any casting requirements, the code will resemble:

InsertLeftChild (TNode *Root, TNode *NewChild, int Where)
{
  switch (Where)
  {
  case  LEFT:
    NewChild->LeftChild = Root->LeftChild;
    break;

  case  MIDDLE:
    NewChild->LeftChild = Root->LeftChild;
    break;

  case  RIGHT:
    NewChild->LeftChild = Root->LeftChild;
  }
  Root->LeftChild = NewChild;
}

This function will insert the NewChild node as the left child of the root node, and the root's original left node becomes the left, middle, or right node of the new node.  In this case "root" isn't necessarily the tree's root node, it's a location in the tree that is current.  (Much like changing your working directory.  You haven't changed the root directory, just what you're looking at.)

You'll need similar functions to add to the middle and right.

This will help you build the initial tree.  Keep in mind that this makes no attempt to normalize (balance) the tree.  That's an entirely different level of complication.  First build the tree, then when the process of building the tree is clear tackle balancing the tree.

HTH,
Kdo
0
 
LVL 1

Author Comment

by:geff_chang
ID: 7993610
Kdo,

thanks for the few tips, but i still don't get it. would you please go to the link (my site) h77p://members.fortunecity.com/changerds/ttt001.html to check out the notes i scanned from our IT class. i hope you can help me out on this. i don't even know where to start. and source codes on 2-3 trees are hardly even available on the NET. ;c

the only thing i know is, though... this functions really have to recursive. ;b
0
 
LVL 1

Author Comment

by:geff_chang
ID: 7993616
Kdo,

thanks for the few tips, but i still don't get it. would you please go to the link (my site) http://members.fortunecity.com/changerds/ttt001.html to check out the notes i scanned from our IT class. i hope you can help me out on this. i don't even know where to start. and source codes on 2-3 trees are hardly even available on the NET. ;c

the only thing i know is, though... this functions really have to recursive. ;b

NOTE: sorry for the repost. the link in the previous MSG was not highlighted.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 46

Expert Comment

by:Kent Olsen
ID: 7995717

Hey Geff,

There's a pretty strict policy about homework questions being asked of the group.  Your original question was structured in a way that it suggested a "general knowledge" inquiry.  I've given you a pretty good primer on 2-3 trees and laid out 1/3 of the add sequence.

But now you tell us that it's a homework assignment and that there's a web site with 5 pages describing the assignment, characteristics of the tree, and general coding requirements.

You need to converse with someone in your class.  Perhaps even your professor.  If 5+ pages, with pics, don't make this reasonably clear then no amount of text typed through this board will either.


Good Luck.
0
 
LVL 22

Expert Comment

by:Dreamboat
ID: 7997780
0
 
LVL 1

Author Comment

by:geff_chang
ID: 8006574
I respect and understand (and have done so beforehand) that it is the policy of this board not to code assignments and anything similar. but unfortunately, i had to resort to this option after having given up with the codes for INSERT and DELETE. I have already made the funtion MEMBER using the second declaration, to which I am not even sure is correct and efficient.

I do not ask you to the code the code for me, if you think it is not appropriate. I would, however, apppreciate all efforts to do so. The codes for INSERT and DELETE are rather complicated, after having seen a code implemented in Java using a declaration almost as similar as the first declaration I came up (but hardly close). In fact, even the best in our class (I can attest to that; he codes the shortest and most efficient of all programs. Though I, too, also rank among the best, I tend to code longer but safer in my own point of view) cannot come up with a recursive using the second declaration.

Of course, it is again your prerogative whether ir not you would like to present the code for INSERT and DELETE using the second declaration. I am, in no way, obligating you to do so, but would again, appreciate would it, considering the complexity of the operations performed. It would also, if you consider it to be, a challenge on your part if you can code the funtions.

I only hope you have not misunderstood me. I do thank you, by the way, for reminding me once again for the policy. And, thanks, too, for all the tips. Wish you happy coding!


#define MTY -1
#define STL 69

struct leaf {
     element_type E;
     /* other information */
}

struct node {
     int NK;
     element_type K1, K2;
     union {
          struct leaf *NL;
          struct node *NN;
     } C[3];
};

struct head {
     int HK;
     union {
          struct leaf *HL;
          struct node *HN;
     } PTR;
} TTT;

TTT A;


/* value = MEMBER(A, X); */
int MEMBER(TTT B, element_type X) {
     int condition = 0;

     if(B.HK != MTY) {
          if((B.HK == 0)&&(B.PTR.HL->E == X))
               ++condition;
          else if(B.HK) {
               while(B.PTR.HN->NK) {
                    if((B.PTR.HN->K2 != STL)&&(X >= B.PTR.HN->K2))
                         B.PTR.HN = B.PTR.HN->C[2].NN;
                    else if(X >= B.PTR.HN->K1)
                         B.PTR.HN = B.PTR.HN->C[1].NN;
                    else
                         B.PTR.HN = B.PTR.HN->C[0].NN;
               } /* END. while(B.PTR.HN->NK) */

               if((B.PTR.HN->K2 != STL)&&(X >= B.PTR.HN->K2))
                    B.PTR.HL = B.PTR.HN->C[2].HL;
               else if(X >= B.PTR.HN->K1)
                    B.PTR.HL = B.PTR.HN->C[1].HL;
               else
                    B.PTR.HL = B.PTR.HN->C[0].HL;

               if(B.PTR.HL->E ==X)
                    ++condtion;
          } /* END. else if(B.HK) */
     } /* END. if(B.HK != MTY) */
     return condition;
}
0
 
LVL 46

Accepted Solution

by:
Kent Olsen earned 100 total points
ID: 8008316

Ok Geff.  I'm sold that you really do need some help.  :)

It appears that you don't really understand recursion and how the program stack works.  It's a bit hard to tell from your code, but it appears that your MEMBER function is supposed to determine whether a specific element is in the tree, OR where the element should be added into the tree.

The 'while' loop is the only means that this function can use to traverse the tree.  While scanning the tree, it modifies the child pointers in the passed structure (B).  This is a bit unorthodox for a recursive language.  Most recursive languages (stack languages like C, PASCAL, etc) will use the program stack to manage traversing a tree.

A simple traversal of a linked list (a unary tree) looks something like this:

MyStruct * PrintTree (MyStruct *Current, char *Key)
{
  fprintf (stdout, "At Node: %d", Current->Something);
  if (Current->Link)
    PrintTree (Link);
}

A simple traversal of a binary tree looks like this:

MyStruct * PrintTree (MyStrunct *Current)
{
  if (Current->LeftChild)
    PrintTree (Current->LeftChild);
  fprintf (stdout, "At Node: %d", Current->Something);
  if (Current->RightChild)
    PrintTree (Current->RightChild);
}

You'll need to do something similar for your 2-3 tree.

Note that you can use this quick traversal method to easily find the desired element or location.  Even thought the two functions above don't actually return anything, they imply a return pointer (poor coding practice on my part, but part of the demo).

Note that the first function will print the elements of the list in the order of their links.  Simply move the 'fprintf' statement below the 'if' statement and the elements will be printed in reverse order.  (If the list is really large, the stack could overflow, but that's a separate issue.)  To use the function to search for an element just return a pointer or call the function to check the next element.

MyStruct * ScanTreeForKey (MyStruct *Current, char *Key)
{
  if (Current->Item == Key)
    return (Current)
  else
    if (Current->Link)
      return (ScanTreeForKey (Current->Link, Key));
  return (NULL);
}


The coding for a binary tree is very similar.  If the element is the desired element return the pointer, else traverse the tree left, the traverse the tree to the right.  I'll leave it up to you to do the coding.  (It will be a good warmup for your 2-3 tree search.)

Traversing your 2-3 tree is almost identical.  Certainly the logic hasn't changed.  You know which of the three branches will (or does) contain the item that you seek.  If the current element is not the target element, recursively call the search function on the correct element.  

The entire search function should be no more than about 10 lines of code.


Good Luck!
Kdo
0
 
LVL 1

Author Comment

by:geff_chang
ID: 8013368
Kdo,

i'm sorry to have missed out on a very important point, but the function MEMBER i have coded earlier is not meant to be recursive in nature (though the INSERT and DELETE should be), since the 2-3 tree will not change in any way and is therefore efficient using any loop method.

though it may be too much to ask, i do hope that you will look into it and see if it is correct. only then can I work to improve on the code.

many thanks, once again.

happy coding,
geff_chang
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
Suggested Courses

752 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question