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

Program to implment an avl& 2-3 tree:-See the logic and implement it. /* * Java Program to Implement AVL Tree */ import java.util.Scanner; /* Class AVLNode */ class AVLNode { AVLNode left, right; int data; int height; /* Constructor */ public AVLNode() { left = null; right = null; data = 0; height = 0; } /* Constructor */ public AVLNode(int n) { left = null; right = null; data = n; height = 0; } } /* Class AVLTree */ class AVLTree { private AVLNode root; /* Constructor */ public AVLTree() { root = null; } /* Function to check if tree is empty */ public boolean isEmpty() { return root == null; } /* Make the tree logically empty */ public void makeEmpty() { root = null; } /* Function to insert data */ public void insert(int data) { root = insert(data, root); } /* Function to get height of node */ private int height(AVLNode t ) { return t == null ? -1 : t.height; } /* Function to max of left/right node */ private int max(int lhs, int rhs) { return lhs > rhs ? lhs : rhs; } /* Function to insert data recursively */ private AVLNode insert(int x, AVLNode t) { if (t == null) t = new AVLNode(x); else if (x t.right.data) t = rotateWithRightChild( t ); else t = doubleWithRightChild( t ); } else ; // Duplicate; do nothing t.height = max( height( t.left ), height( t.right ) ) + 1; return t; } /* Rotate binary tree node with left child */ private AVLNode rotateWithLeftChild(AVLNode k2) { AVLNode k1 = k2.left; k2.left = k1.right; k1.right = k2; k2.height = max( height( k2.left ), height( k2.right ) ) + 1; k1.height = max( height( k1.left ), k2.height ) + 1; return k1; } /* Rotate binary tree node with right child */ private AVLNode rotateWithRightChild(AVLNode k1) { AVLNode k2 = k1.right; k1.right = k2.left; k2.left = k1; k1.height = max( height( k1.left ), height( k1.right ) ) + 1; k2.height = max( height( k2.right ), k1.height ) + 1; return k2; } /** * Double rotate binary tree node: first left child * with its right child; then node k3 with new left child */ private AVLNode doubleWithLeftChild(AVLNode k3) { k3.left = rotateWithRightChild( k3.left ); return rotateWithLeftChild( k3 ); } /** * Double rotate binary tree node: first right child * with its left child; then node k1 with new right child */ private AVLNode doubleWithRightChild(AVLNode k1) { k1.right = rotateWithLeftChild( k1.right ); return rotateWithRightChild( k1 ); } /* Functions to count number of nodes */ public int countNodes() { return countNodes(root); } private int countNodes(AVLNode r) { if (r == null) return 0; else { int l = 1; l += countNodes(r.left); l += countNodes(r.right); return l; } } /* Functions to search for an element */ public boolean search(int val) { return search(root, val); } private boolean search(AVLNode r, int val) { boolean found = false; while ((r != null) && !found) { int rval = r.data; if (val rval) r = r.right; else { found = true; break; } found = search(r, val); } return found; } public class AVLTreeTest { public static void main(String[] args) { Scanner scan = new Scanner(System.in); /* Creating object of AVLTree */ AVLTree avlt = new AVLTree(); System.out.println("AVLTree Tree Test "); char ch; /* Perform tree operations */ do { System.out.println(" AVLTree Operations "); System.out.println("1. insert "); System.out.println("2. search"); System.out.println("3. count nodes"); System.out.println("4. check empty"); System.out.println("5. clear tree"); int choice = scan.nextInt(); switch (choice) { case 1 : System.out.println("Enter integer element to insert"); avlt.insert( scan.nextInt() ); break; case 2 : System.out.println("Enter integer element to search"); System.out.println("Search result : "+ avlt.search( scan.nextInt() )); break; case 3 : System.out.println("Nodes = "+ avlt.countNodes()); break; case 4 : System.out.println("Empty status = "+ avlt.isEmpty()); break; case 5 : System.out.println(" Tree Cleared"); avlt.makeEmpty(); break; default : System.out.println("Wrong Entry "); break; } System.out.println(" Do you want to continue (Type y or n) "); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } } public class Node { boolean isLeaf = false; int numberOfKeys; String[] keys = new String[2]; //each node can contain up to 2 keys int[] values = new int[2]; //every key contains 2 values Node[] subtrees = new Node[3]; //every node can contain pointers to 3 different nodes Node(Node n) { n.numberOfKeys = 0; n.isLeaf = true; } } package kth.id2010.lab.lab04; public class Tree { Node root; // root node of the tree int n; // number of elements in the tree private Tree(){ root = new Node(root); n = 0; } //Return the values of the key if we find it public int[] get(String key){ //if the root has no subtrees check if it contain the right key if(this.root.subtrees.length == 0){ if(this.root.keys[0] == key){ return(this.root.keys[0].values); } else if(this.root.keys[1] == key){ return(this.root.keys[1].values); } } //if noot in root, check its subtree nodes //and here I can't get my head around how to traverse down the tree else{ for(int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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