Hi All, Good discussion. Let me explain my idea. First of all B-Tree, or version of the B-Tree, is the data structure that suites your requirement. As you mentioned in the case 2, you want to maintain the Fill Factor as ( 70%) should have minimum 5 leaf nodes.
For implementation, Linked list way implementation is the best way, i guess. 1. First create tree 2. Balance the tree 3. To maintain the fill factor now call the redistribution algorithm Define a structure for a node. Please refere to any good data structures book and Data base management systems book. Fundamentals of Data Structures: Ellis Horowitz, Sartaj Sahani Data base management systems by Raghu Rama Krishna. * * On Mon, Jun 30, 2008 at 9:12 PM, Vandana <[EMAIL PROTECTED]> wrote: > > Ok thanks, employee hierarchy was just an example. I forgot that b- > trees dint need a id. > > Thanks a lot. > > > On Jun 30, 11:20 am, "Nat Padmanabhan" <[EMAIL PROTECTED]> wrote: > > B-trees don't need any special node identifiers, as long as there is some > > ordering in the data you should be fine. For employees, names are not a > bad > > idea - you are going to have dupes but that can be handled. > > > > On Mon, Jun 30, 2008 at 11:14 AM, Vandana <[EMAIL PROTECTED]> wrote: > > > > > Hi, > > > > > I have used arrays and I have implemented 'Case 1' that I have > > > explained in my example. > > > Now I want to optimize it. To optimize the code I was thinking of B- > > > trees. > > > But the nodes dont have any unique identifier. It can be thought of > > > as an employee hierarchy tree > > > where only the affliation to the parent node is important and needs to > > > be kept track of. > > > > > Would b-trees be the best way to implement this? > > > > > No this is not part of my homework. :) > > > > > Thanks > > > > > On Jun 30, 11:07 am, "Venkatraman S" <[EMAIL PROTECTED]> wrote: > > > > what did you try before you ask it in the forum? Is this part of your > > > > homework? > > > > > > Venkat > > > > > > On Mon, Jun 30, 2008 at 8:35 PM, Vandana <[EMAIL PROTECTED]> wrote: > > > > > > > Hello All, > > > > > > > I would like to implement a tree with the following properties. > > > > > > > 1. The tree is balanced. > > > > > 2. Each node has a max of 7 sub nodes and min of ceil(7/2) sub > nodes. > > > > > 3. Number of nodes known from the beginning. > > > > > > > How would I implement this? Is there a data structure that I can > use? > > > > > > > Consider the following scenario: I have 16 nodes and I want to > create > > > > > a balanced tree such that each sub_node has a max of 7 nodes. > > > > > (example) I can create the tree in the following 2 ways: > > > > > > > Case 1: Make a root node, with 3 sub_nodes, 2 sub_nodes have 7 leaf > > > > > nodes and the third sub_node of the root node has 2 leaf nodes. > > > > > > > Case 2: Make a root node, with 3 sub_nodes, distribute the leaf > nodes > > > > > such that all 3 sub_nodes have 5 leaf nodes and 1 of them has an > > > > > extra. > > > > > > > I am interested in case 2. > > > > > > > I must first construct this and then > > > > > be able to move around the leaf nodes and ensure that this > 'balance' > > > > > is not lost. > > > > > > > I know I have to use AVL principles of rotation, but since text > books > > > > > explain only for binary trees, i need some help on it. > > > > > Any ideas will be most helpful. > > > > > > > Thanks, > > > > > Vandana. > > > -- Regards PRADEEP MACHARLA --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
