Tree structure, Data Structure & Algorithms

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:


{ 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.


{ 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.

Posted Date: 2/22/2013 1:51:15 AM | Location : United States

Related Discussions:- Tree structure, Assignment Help, Ask Question on Tree structure, Get Answer, Expert's Help, Tree structure Discussions

Write discussion on Tree structure
Your posts are moderated
Related Questions
Define tractable and intractable problems Problems that can be solved in polynomial time are known as tractable problems, problems that cannot be solved in polynomial time are

Suppose we have a set of N agents and a set of N tasks.Each agent can only perform exactly one task and there is a cost associated with each assignment. We would like to find out a

Define the Carrier set of the Symbol ADT Carrier set of the Symbol ADT is the set of all finite sequences of characters over Unicode characters set (Unicode is a standard char

Write a function that performs the integer mod function. Given the previous functions you have implemented already, this one should be a piece of cake. This function will find the

The first assignment in this course required you to acquire data to enable you to implement the PHYSAT algorithm (Alvain et al. 2005, Alvain et al. 2008) in this second assignment

Taking a suitable example explains how a general tree can be shown as a Binary Tree. Conversion of general trees to binary trees: A general tree can be changed into an equiv

explain implementation of circular queue insert,delete operations

This unit discussed about data structure called Arrays. The easiest form of array is a one-dimensional array which may be described as a finite ordered set of homogeneous elements

The controversy of RISC versus CISC never ends. Suppose that you represent an advocate for the RISC approach; write at least a one-page critic of the CISC approach showing its disa

1. Use the Weierstrass condition, find the (Strongly) minimizing curve and the value of J min for the cases where x(1) = 0, x(2) = 3. 2. The system = x 1 + 2u; where