Tree structure, Data Structure & Algorithms

Assignment Help:

We would like to implement a 2-4Tree containing distinct integer keys. This 2-4Tree is defined by the ArrayList Nodes of all the 2-4Nodes in the tree and the special 2-4Node Root which is the root of the tree. Each 2-4Node is defined by 2 ArrayLists Keys and Refs. Keys is an ArrayList of Integer objects representing the ordered integer keys stored in the node;

Refs is an ArrayList containing the references to the node's parent (NULL if the node is the root) and children (NULL if they are leaves). All these ArrayLists are implemented in java.util.ArrayList. Implement the following methods of the two classes 2-4Node and 2-4Tree using the methods of java.util.ArrayList as well as any other method you find necessary:

 2-4Node:

{ public int Type(): Returns the type of the node (2Node or 3Node etc.). { public void InsertinNode(int i): Inserts the integer i in the node at the right position. We consider that the children of the node are leaves. The Keys and Refs lists should be appended properly. Thus, you have to take into account the special case where the node contains no keys. No duplicate keys are allowed in the node so this method returns an error if you try to insert an existing key.

On the other hand an overow is not treated in this method.

2-4Tree:

{ public 2-4Node[] Search(int i,2-4Node N): This method searches recursively for the key i in the 2-4subtree of root N. It returns a reference to the node M containing i (NULL if i is not in the subtree) and another reference to the parent of this node M (if M is NULL its parent is the last searched 2-4node). Returns an error if N is NULL.

{ public void Insert(int i): Inserts the key i in the 2-4Tree at the right 2- 4Node and position. You have to take into account the special case where i is the first key to be inserted in the 2-4Tree. Returns an error if i is already in the 2-4Tree. In the case of an overow this overow should be treated!

{ public void split(2-4Node N): Splits the overowing 2-4Node N into two separate nodes and sends the 3rd key in N to its parent M. The lists Keys and Refs of M should be modified properly. The split is applied to the parent M if overowing etc. Pay attention to the special case where N is the root of the 2-4Tree.

Test :

Test your classes and methods by inserting the following sequence of integers (in the same order) into an initially empty 2-4Tree:f8,12,1,15,2,14,3,10,5,6,4,9,16,21,7,17g. Printout the keys in the 2-4 Node M containing 6, the keys in its parent and in the 2nd child of M.


Related Discussions:- Tree structure

Algorithm that inputs the codes for all items in stock, A shop sells books,...

A shop sells books, magazines and maps. Every item is identified by a unique 4 - digit code. All books have a code which starts with 1, all maps have a code starting with 2 and all

Merging, Merging two sequence using CREW merge

Merging two sequence using CREW merge

Basic organization of computer system, what happen''s in my computer when ...

what happen''s in my computer when i input any passage

Estimate the probability that the noncritical path , An advertising project...

An advertising project manager developed the network diagram shown below for a new advertising campagign.  In addition, the manager gathered the time information for each activity,

Applications of shortest path algorithms, The minimum cost spanning tree ha...

The minimum cost spanning tree has broad applications in distinct fields. It represents several complicated real world problems such as: 1. Minimum distance for travelling all o

Draw trace table and determine output of number, Draw trace table and deter...

Draw trace table and determine output from the following flowchart using following data: Number = 45, -2, 20.5

Stack, implement multiple stacks ina single dimensional array. write algori...

implement multiple stacks ina single dimensional array. write algorithams for various stack operation for them.

State the symbols of abstract data type operation, Symbols of ADT oepration...

Symbols of ADT oeprations All Symbol ADT operations are implemented in Symbol class, except toSymbol(), which is implemented in classes (like String) which can generate a Symb

Explain multiplication method, Multiplication Method: The multiplication m...

Multiplication Method: The multiplication method operates in 2 steps. In the 1ststep the key value K is multiplied by a constant A in the range O

Define queue, A queue is a, FIFO (First In First Out) list.

A queue is a, FIFO (First In First Out) list.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd