Data Structures II jusing java Question: Balanced Trees, A Comparison between 2-

Question

Data Structures II jusing java

Question: Balanced Trees, A Comparison between 2-3 Trees and AVL

Trees For this assignment, you are to create a 2-3 Tree class and an AVL Tree class. For each, the following interface must be used:

public interface BalancedTree {

boolean isEmpty();

void insert(T val);

void delete(T val);

boolean contains(T val);

boolean isFullTree();

boolean isBalancedTree();

int nodeCount(); int treeHeight();

}

The data must be objects – and the implementations must be generic.I suggest building it to work with Integer objects and then convert it to be generic.

For the 2-3 tree, a height data member cannot be part of the node, but a link to the parent can be. For the AVL tree, a link to the parent will not be allowed, but a height data member is expected. Also, when implementing nodeCount(), you must not use a global size variable in either implementations.

A test file has been provided. Each line starts with one of three letters: ‘I’ for insert, ‘D’ for delete, and ‘R’ for report. Both the insert and delete lines will also include an integer value to be used with the operation. I recommend you look in the file.

Create a test program that will:

a) Ask the user which balanced tree structure to use

b) Read the test file and perform the operations as specified. When the ‘R’ for reporting is encountered, report the following details:

Test with: (1) 23Tree or (2) AVL? 1

Added: 999; Delete: 999

Total Nodes: 999; Height: 99

Is Balanced? Yes/No; Is Full? Yes/No

c) Leave a blank line between each reporting

Explanation / Answer

class twoThreeTree { public: twoThreeTree(void); // Constructor ~twoThreeTree(void); // Destructor void add(int item); // Adds an item void search(int item); // Searches for an item private: twoThreeNode *root; // Pointer to root node // Private helper functions go here }; class twoThreeNode { public: int firstData, secondData; // Two data fields // The three child nodes twoThreeNode *first, *second, *third; // This next one is quite useful. It aids // moving around the tree. It is a pointer // to the parent of the current node. twoThreeNode *parent; };

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.