Help with Java Code With following Binary Node and Binary Tree class need help making an AVL Tree with the Insert and Remove Functions that deals with the rotations. Use inheritance from Binary Tree to create AVL Tree. Modifications to the Binary Node or Binary Tree are fine. Trees should be specific for strings Binary Node Class: public class BinNode { private String data; private BinNode left; private BinNode right; public BinNode(){ data = ""; left = null; right = null; } public BinNode(String d){ data = d; left = null; right = null; } public void setData(String d){ this.data = d; } public String getData(){ return this.data; } public void setLeft(BinNode l){ this.left = l; } public BinNode getLeft(){ return this.left; } public void setRight(BinNode r){ this.right = r; } public BinNode getRight(){ return this.right; } } Binary Tree Code: public class BinaryTree { private BinNode root; private BinNode curr; /* Function to traverse right */ public void goRight() { this.curr = this.curr.getRight(); } public BinaryTree() { root = new BinNode(); curr = new BinNode(); } public BinNode getRoot(){ return this.root; } /* Function to check if tree is empty */ public boolean isEmpty() { return this.root == null; } /* Functions to insert data */ public void insert(String data) { this.root = insert(this.root, data); } //done /* Function to insert data recursively */ private BinNode insert(BinNode node, String data) { if (node == null) node = new BinNode(data); else { int i = node.getData().compareTo(data); if (i < 0) { // Go right node.setRight(insert(node.getRight(), data)); } else if (i >= 0) { // Go left node.setLeft(insert(node.getLeft(), data)); } // write this! } return node; } /* Function to count number of nodes */ public int countNodes() { return countNodes(this.root); } /* Function to count number of nodes recursively */ private int countNodes(BinNode r) { if (r == null) { return 0; // If the current node is null, there are no nodes to count. } int leftCount = countNodes(r.getLeft()); // Count nodes in the left subtree int rightCount = countNodes(r.getRight()); // Count nodes in the right subtree // Add 1 to count the current node itself return 1 + leftCount + rightCount; } /* Function to search for an element */ public BinNode search(String val) { return search(this.root, val); } /* Function to search for an element recursively */ private BinNode search(BinNode r, String val) { // Base case: If the current node is null, the value is not found. if (r == null) { return null; } int comparison = val.compareTo(r.getData()); if (comparison < 0) { // Value is smaller, so search in the left subtree. return search(r.getLeft(), val); } else if (comparison > 0) { // Value is larger, so search in the right subtree. return search(r.getRight(), val); } else { // Value is equal to the current node's data, so it's found. //this.curr = r; return r; } } /* Function for inorder traversal */ public void inorder() { inorder(this.root); } private void inorder(BinNode r) { if (r != null) { inorder(r.getLeft()); System.out.print(r.getData() +" "); inorder(r.getRight()); } } /* Function for preorder traversal */ public void preorder() { preorder(root); } private void preorder(BinNode r) { if (r != null) { System.out.print(r.getData() +" "); preorder(r.getLeft()); preorder(r.getRight()); } } /* Function for postorder traversal */ public void postorder() { postorder(root); } private void postorder(BinNode r) { if (r != null) { postorder(r.getLeft()); postorder(r.getRight()); System.out.print(r.getData() +" "); } } // find the in-order successor of a given node public BinNode findInorderSuccessor(BinNode node) { BinNode current = node.getRight(); while (current.getLeft() != null) { current = current.getLeft(); } return current; } //Remove function public void remove(String key) { // Find the node to be removed and its parent BinNode parent = null; BinNode n = this.root; while (n != null && !n.getData().equals(key)) { parent = n; if (key.compareTo(n.getData()) < 0) { n = n.getLeft(); } else { n = n.getRight(); } } if (n == null) { // Key not found, nothing to remove return; } // Case 1: Node with no children if (n.getLeft() == null && n.getRight() == null) { if (parent == null) { // Removing the root node this.root = null; } else if (parent.getLeft() == n) { parent.setLeft(null); } else { parent.setRight(null); } } // Case 2: Node with one child else if (n.getLeft() == null || n.getRight() == null) { BinNode child = (n.getLeft() != null) ? n.getLeft() : n.getRight(); if (n == this.root) { this.root = child; } else if (parent.getLeft() == n) { parent.setLeft(child); } else { parent.setRight(child); } } // Case 3: Node with two children else { BinNode successor = findInorderSuccessor(n); n.setData(successor.getData()); remove(successor.getData()); // Recursively remove the successor } } }

Help with Java Code With following Binary Node and Binary Tree class need help making an AVL Tree with the Insert and Remove Functions that deals with the rotations. Use inheritance from Binary Tree to create AVL Tree. Modifications to the Binary Node or Binary Tree are fine. Trees should be specific for strings Binary Node Class: public class BinNode { private String data; private BinNode left; private BinNode right; public BinNode(){ data = ""; left = null; right = null; } public BinNode(String d){ data = d; left = null; right = null; } public void setData(String d){ this.data = d; } public String getData(){ return this.data; } public void setLeft(BinNode l){ this.left = l; } public BinNode getLeft(){ return this.left; } public void setRight(BinNode r){ this.right = r; } public BinNode getRight(){ return this.right; } } Binary Tree Code: public class BinaryTree { private BinNode root; private BinNode curr; /* Function to traverse right / public void goRight() { this.curr = this.curr.getRight(); } public BinaryTree() { root = new BinNode(); curr = new BinNode(); } public BinNode getRoot(){ return this.root; } / Function to check if tree is empty / public boolean isEmpty() { return this.root == null; } / Functions to insert data / public void insert(String data) { this.root = insert(this.root, data); } //done / Function to insert data recursively / private BinNode insert(BinNode node, String data) { if (node == null) node = new BinNode(data); else { int i = node.getData().compareTo(data); if (i < 0) { // Go right node.setRight(insert(node.getRight(), data)); } else if (i >= 0) { // Go left node.setLeft(insert(node.getLeft(), data)); } // write this! } return node; } / Function to count number of nodes / public int countNodes() { return countNodes(this.root); } / Function to count number of nodes recursively / private int countNodes(BinNode r) { if (r == null) { return 0; // If the current node is null, there are no nodes to count. } int leftCount = countNodes(r.getLeft()); // Count nodes in the left subtree int rightCount = countNodes(r.getRight()); // Count nodes in the right subtree // Add 1 to count the current node itself return 1 + leftCount + rightCount; } / Function to search for an element / public BinNode search(String val) { return search(this.root, val); } / Function to search for an element recursively / private BinNode search(BinNode r, String val) { // Base case: If the current node is null, the value is not found. if (r == null) { return null; } int comparison = val.compareTo(r.getData()); if (comparison < 0) { // Value is smaller, so search in the left subtree. return search(r.getLeft(), val); } else if (comparison > 0) { // Value is larger, so search in the right subtree. return search(r.getRight(), val); } else { // Value is equal to the current node's data, so it's found. //this.curr = r; return r; } } / Function for inorder traversal / public void inorder() { inorder(this.root); } private void inorder(BinNode r) { if (r != null) { inorder(r.getLeft()); System.out.print(r.getData() +" "); inorder(r.getRight()); } } / Function for preorder traversal / public void preorder() { preorder(root); } private void preorder(BinNode r) { if (r != null) { System.out.print(r.getData() +" "); preorder(r.getLeft()); preorder(r.getRight()); } } / Function for postorder traversal */ public void postorder() { postorder(root); } private void postorder(BinNode r) { if (r != null) { postorder(r.getLeft()); postorder(r.getRight()); System.out.print(r.getData() +" "); } } // find the in-order successor of a given node public BinNode findInorderSuccessor(BinNode node) { BinNode current = node.getRight(); while (current.getLeft() != null) { current = current.getLeft(); } return current; } //Remove function public void remove(String key) { // Find the node to be removed and its parent BinNode parent = null; BinNode n = this.root; while (n != null && !n.getData().equals(key)) { parent = n; if (key.compareTo(n.getData()) < 0) { n = n.getLeft(); } else { n = n.getRight(); } } if (n == null) { // Key not found, nothing to remove return; } // Case 1: Node with no children if (n.getLeft() == null && n.getRight() == null) { if (parent == null) { // Removing the root node this.root = null; } else if (parent.getLeft() == n) { parent.setLeft(null); } else { parent.setRight(null); } } // Case 2: Node with one child else if (n.getLeft() == null || n.getRight() == null) { BinNode child = (n.getLeft() != null) ? n.getLeft() : n.getRight(); if (n == this.root) { this.root = child; } else if (parent.getLeft() == n) { parent.setLeft(child); } else { parent.setRight(child); } } // Case 3: Node with two children else { BinNode successor = findInorderSuccessor(n); n.setData(successor.getData()); remove(successor.getData()); // Recursively remove the successor } } }

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

Help with Java Code

With following Binary Node and Binary Tree class need help making an AVL Tree with the Insert and Remove Functions that deals with the rotations. Use inheritance from Binary Tree to create AVL Tree. Modifications to the Binary Node or Binary Tree are fine.

Trees should be specific for strings

Binary Node Class:

public class BinNode
{
private String data;
private BinNode left;
private BinNode right;

public BinNode(){
data = "";
left = null;
right = null;
}

public BinNode(String d){
data = d;
left = null;
right = null;
}

public void setData(String d){
this.data = d;
}
public String getData(){
return this.data;
}
public void setLeft(BinNode l){
this.left = l;
}
public BinNode getLeft(){
return this.left;
}
public void setRight(BinNode r){
this.right = r;
}
public BinNode getRight(){
return this.right;
}
}

Binary Tree Code:

public class BinaryTree
{
private BinNode root;
private BinNode curr;

/* Function to traverse right */
public void goRight() {
this.curr = this.curr.getRight();
}

public BinaryTree()
{
root = new BinNode();
curr = new BinNode();
}

public BinNode getRoot(){
return this.root;
}

/* Function to check if tree is empty */
public boolean isEmpty()
{
return this.root == null;
}
/* Functions to insert data */
public void insert(String data)
{
this.root = insert(this.root, data);
} //done
/* Function to insert data recursively */
private BinNode insert(BinNode node, String data)
{
if (node == null)
node = new BinNode(data);
else
{
int i = node.getData().compareTo(data);
if (i < 0) {
// Go right
node.setRight(insert(node.getRight(), data));
} else if (i >= 0) {
// Go left
node.setLeft(insert(node.getLeft(), data));
}
// write this!
}
return node;
}
/* Function to count number of nodes */
public int countNodes()
{
return countNodes(this.root);
}
/* Function to count number of nodes recursively */
private int countNodes(BinNode r)
{
if (r == null) {
return 0; // If the current node is null, there are no nodes to count.
}

int leftCount = countNodes(r.getLeft()); // Count nodes in the left subtree
int rightCount = countNodes(r.getRight()); // Count nodes in the right subtree

// Add 1 to count the current node itself
return 1 + leftCount + rightCount;
}
/* Function to search for an element */
public BinNode search(String val)
{
return search(this.root, val);
}
/* Function to search for an element recursively */
private BinNode search(BinNode r, String val)
{
// Base case: If the current node is null, the value is not found.
if (r == null) {
return null;
}

int comparison = val.compareTo(r.getData());

if (comparison < 0) {
// Value is smaller, so search in the left subtree.
return search(r.getLeft(), val);
} else if (comparison > 0) {
// Value is larger, so search in the right subtree.
return search(r.getRight(), val);
} else {
// Value is equal to the current node's data, so it's found.
//this.curr = r;
return r;
}
}
/* Function for inorder traversal */
public void inorder()
{
inorder(this.root);
}
private void inorder(BinNode r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() +" ");
inorder(r.getRight());
}
}
/* Function for preorder traversal */
public void preorder()
{
preorder(root);
}
private void preorder(BinNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
/* Function for postorder traversal */
public void postorder()
{
postorder(root);
}
private void postorder(BinNode r)
{
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() +" ");
}
}

// find the in-order successor of a given node
public BinNode findInorderSuccessor(BinNode node) {
BinNode current = node.getRight();

while (current.getLeft() != null) {
current = current.getLeft();
}

return current;
}

//Remove function
public void remove(String key) {
// Find the node to be removed and its parent
BinNode parent = null;
BinNode n = this.root;
while (n != null && !n.getData().equals(key)) {
parent = n;
if (key.compareTo(n.getData()) < 0) {
n = n.getLeft();
} else {
n = n.getRight();
}
}

if (n == null) {
// Key not found, nothing to remove
return;
}

// Case 1: Node with no children
if (n.getLeft() == null && n.getRight() == null) {
if (parent == null) {
// Removing the root node
this.root = null;
} else if (parent.getLeft() == n) {
parent.setLeft(null);
} else {
parent.setRight(null);
}
}
// Case 2: Node with one child
else if (n.getLeft() == null || n.getRight() == null) {
BinNode child = (n.getLeft() != null) ? n.getLeft() : n.getRight();
if (n == this.root) {
this.root = child;
} else if (parent.getLeft() == n) {
parent.setLeft(child);
} else {
parent.setRight(child);
}
}
// Case 3: Node with two children
else {
BinNode successor = findInorderSuccessor(n);
n.setData(successor.getData());
remove(successor.getData()); // Recursively remove the successor
}
}

}

Expert Solution

Step 1: To create an AVL Tree from the provided BinaryTree class :

you can extend the BinaryTree class to create an AVLTree class, and then modify the insert method to ensure the AVL property is maintained by performing rotations as necessary. Here's a step-by-step guide:

Create an AVLTree class that extends BinaryTree:

Modify the insert method in the AVLTree class to ensure AVL balance after insertion. To do this, you'll need to perform appropriate rotations (left or right rotations) when the AVL property is violated. You can do this by tracking the height of the nodes and checking the balance factor.

Step by step

Solved in 3 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.