For my Insert and Remove Method for a BInaryTree how can I replicate it for the AVL Insert and Remove I have below... I need to have the AVL Insert and Remove work for strings properly like it does for my Binary Tree... but when I use the Methods I believe I get an error pertaining to how BinNode and Strings work for it... public class BinNode { private String data; private BinNode left; private BinNode right; private int height; private boolean color; private BinNode parent; public BinNode(){ data = ""; left = null; right = null; parent = null; color = false; } public boolean getColor() { return color; } public void setColor(boolean color) { this.color = color; } public BinNode getParent() { return parent; } public void setParent(BinNode parent) { this.parent = parent; } public int getHeight() { return height; } public void setHeight(int height) { this.height = height; } 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; } } (My Binary Tree Insert Method) public void insert(String data) { this.root = insert(this.root, data); } /* 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) { node.setRight(insert(node.getRight(), data)); } else if (i >= 0) { node.setLeft(insert(node.getLeft(), data)); } } return node; } /* Function to count number of nodes */ public int countNodes() { return countNodes(this.root); } private int countNodes(BinNode r) { if (r == null) { return 0; } int leftCount = countNodes(r.getLeft()); int rightCount = countNodes(r.getRight()); return 1 + leftCount + rightCount; } public BinNode search(String val) { return search(this.root, val); } private BinNode search(BinNode r, String val) { if (r == null) { return null; } int comparison = val.compareTo(r.getData()); if (comparison < 0) { return search(r.getLeft(), val); } else if (comparison > 0) { return search(r.getRight(), val); } else { return r; } } public void remove(String key) { 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) { return; } if (n.getLeft() == null && n.getRight() == null) { if (parent == null) { this.root = null; } else if (parent.getLeft() == n) { parent.setLeft(null); } else { parent.setRight(null); } } 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 } (My AVL Tree methods) public void insert(String data) { root = insert(root, data); } private BinNode insert(BinNode node, String data) { if (node == null) { return new BinNode(data); } int cmp = data.compareTo(node.data); if (cmp < 0) { node.left = insert(node.left, data); } else if (cmp > 0) { node.right = insert(node.right, data); } else { return node; } node.height = 1 + Math.max(height(node.left), height(node.right)); int balance = getBalance(node); if (balance > 1) { if (data.compareTo(node.left.data) < 0) { return rightRotate(node); } else { node.left = leftRotate(node.left); return rightRotate(node); } } if (balance < -1) { if (data.compareTo(node.right.data) > 0) { return leftRotate(node); } else { node.right = rightRotate(node.right); return leftRotate(node); } } return node; } public void remove(String data) { root = remove(root, data); } private BinNode remove(BinNode node, String data) { if (node == null) { return node; } int cmp = data.compareTo(node.data); if (cmp < 0) { node.left = remove(node.left, data); } else if (cmp > 0) { node.right = remove(node.right, data); } else { // Node found, perform deletion if (node.left == null || node.right == null) { BinNode temp = (node.left != null) ? node.left : node.right; if (temp == null) { temp = node; node = null; } else { node = temp; } } else { BinNode temp = minValueNode(node.right); node.data = temp.data; node.right = remove(node.right, temp.data); } } if (node == null) { return node; } node.height = 1 + Math.max(height(node.left), height(node.right)); int balance = getBalance(node); if (balance > 1) { if (getBalance(node.left) >= 0) { return rightRotate(node); } else { node.left = leftRotate(node.left); return rightRotate(node); } } if (balance < -1) { if (getBalance(node.right) <= 0) { return leftRotate(node); } else { node.right = rightRotate(node.right); return leftRotate(node); } } return node; } private BinNode minValueNode(BinNode node) { BinNode current = node; while (current.left != null) { current = current.left; } return current; }
For my Insert and Remove Method for a BInaryTree how can I replicate it for the AVL Insert and Remove I have below... I need to have the AVL Insert and Remove work for strings properly like it does for my Binary Tree... but when I use the Methods I believe I get an error pertaining to how BinNode and Strings work for it...
public class BinNode
{
private String data;
private BinNode left;
private BinNode right;
private int height;
private boolean color;
private BinNode parent;
public BinNode(){
data = "";
left = null;
right = null;
parent = null;
color = false;
}
public boolean getColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
public BinNode getParent() {
return parent;
}
public void setParent(BinNode parent) {
this.parent = parent;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
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;
}
}
(My Binary Tree Insert Method)
public void insert(String data)
{
this.root = insert(this.root, data);
}
/* 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) {
node.setRight(insert(node.getRight(), data));
} else if (i >= 0) {
node.setLeft(insert(node.getLeft(), data));
}
}
return node;
}
/* Function to count number of nodes */
public int countNodes()
{
return countNodes(this.root);
}
private int countNodes(BinNode r)
{
if (r == null) {
return 0;
}
int leftCount = countNodes(r.getLeft());
int rightCount = countNodes(r.getRight());
return 1 + leftCount + rightCount;
}
public BinNode search(String val)
{
return search(this.root, val);
}
private BinNode search(BinNode r, String val)
{
if (r == null) {
return null;
}
int comparison = val.compareTo(r.getData());
if (comparison < 0) {
return search(r.getLeft(), val);
} else if (comparison > 0) {
return search(r.getRight(), val);
} else {
return r;
}
}
public void remove(String key) {
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) {
return;
}
if (n.getLeft() == null && n.getRight() == null) {
if (parent == null) {
this.root = null;
} else if (parent.getLeft() == n) {
parent.setLeft(null);
} else {
parent.setRight(null);
}
}
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
}
(My AVL Tree methods)
public void insert(String data) {
root = insert(root, data);
}
private BinNode insert(BinNode node, String data) {
if (node == null) {
return new BinNode(data);
}
int cmp = data.compareTo(node.data);
if (cmp < 0) {
node.left = insert(node.left, data);
} else if (cmp > 0) {
node.right = insert(node.right, data);
} else {
return node;
}
node.height = 1 + Math.max(height(node.left), height(node.right));
int balance = getBalance(node);
if (balance > 1) {
if (data.compareTo(node.left.data) < 0) {
return rightRotate(node);
} else {
node.left = leftRotate(node.left);
return rightRotate(node);
}
}
if (balance < -1) {
if (data.compareTo(node.right.data) > 0) {
return leftRotate(node);
} else {
node.right = rightRotate(node.right);
return leftRotate(node);
}
}
return node;
}
public void remove(String data) {
root = remove(root, data);
}
private BinNode remove(BinNode node, String data) {
if (node == null) {
return node;
}
int cmp = data.compareTo(node.data);
if (cmp < 0) {
node.left = remove(node.left, data);
} else if (cmp > 0) {
node.right = remove(node.right, data);
} else {
// Node found, perform deletion
if (node.left == null || node.right == null) {
BinNode temp = (node.left != null) ? node.left : node.right;
if (temp == null) {
temp = node;
node = null;
} else {
node = temp;
}
} else {
BinNode temp = minValueNode(node.right);
node.data = temp.data;
node.right = remove(node.right, temp.data);
}
}
if (node == null) {
return node;
}
node.height = 1 + Math.max(height(node.left), height(node.right));
int balance = getBalance(node);
if (balance > 1) {
if (getBalance(node.left) >= 0) {
return rightRotate(node);
} else {
node.left = leftRotate(node.left);
return rightRotate(node);
}
}
if (balance < -1) {
if (getBalance(node.right) <= 0) {
return leftRotate(node);
} else {
node.right = rightRotate(node.right);
return leftRotate(node);
}
}
return node;
}
private BinNode minValueNode(BinNode node) {
BinNode current = node;
while (current.left != null) {
current = current.left;
}
return current;
}
Step by step
Solved in 3 steps
