need help with finishing my remove method for my binary search tree i need help where it says implement the rest of the remove as well as the public remove method i also need to create a driver to test this this is a recursive
i need help with finishing my remove method for my binary search tree
i need help where it says implement the rest of the remove as well as the public remove method
i also need to create a driver to test this
this is a recursive binary search tree with integers being stored in parallel arrays
there is also an index involved
import java.util.*;
import java.io.*;
public class BoundedBST {
private int root;
private int free;
private int left[];
private int data[];
private int right[];
private int currentSize;
public BoundedBST(int size) {
root = -1;
free = -1;
left = new int[size];
data = new int[size];
right = new int[size];
currentSize = 0;
}
public boolean full() {
return free == -1 && currentSize == data.length;
}
private int createNode(int value){
data[currentSize]=value;
left[currentSize]=-1;
right[currentSize]=-1;
return currentSize++;
}
// insert method to insert the new Date
public void insert(int d) {
if(root==-1){
root=createNode(d);
}
else{
insert(d, 0);
}
}
private void insert( int d, int index) {
if (data[index] == d) {
return;
}
if (data[index] > d) {
if (left[index] == -1) {
left[index] = createNode(d);
} else {
insert(d, left[index]);
}
} else {
if (right[index] == -1) {
right[index] = createNode(d);
} else {
insert(d, right[index]);
}
}
return;
}
public void print(){
print(root);
System.out.println();
}
private void print(int index){
if(index!=-1){
print(left[index]);
System.out.print(data[index] + " ");
print(right[index]);
}
//find largest node in left subtree and return its index
private int findGreatest(int index) {
int r = right[index];
if(r != -1) {
return findGreatest(r);
}
return index;
}
public void remove(int d) {
//if d is in the tree remove d otherwise the tree does not change
}
private void remove(int d, int index) {
//we found the data to remove
if(data[index] == d) {
//removes
//if the node is a leaf
if (left[index] == -1 && right[index] == -1) {
data[index] = -1;
if (free == -1) {
free = index;
} else {
freeUpdate(index);
}
currentSize--;
}
//the node has a left child
else if (left[index] != -1 && right[index] == -1) {
int l = left[index];
data[index] = data[l];
left[index] = left[l];
right[index] = right[l];
if (free == -1) {
free = l;
} else {
freeUpdate(l);
}
//delete stuff in node that moved
data[l] = -1;
right[l] = -1;
currentSize--;
}
//the node has a right child
else if (left[index] == -1 && right[index] != -1) {
int r = right[index];
data[index] = data[r];
left[index] = left[r];
right[index] = right[r];
if (free == -1) {
free = r;
} else {
freeUpdate(r);
}
//delete stuff in node that moved
data[r] = -1;
right[r] = -1;
currentSize--;
}
//the node has two children
else {
int l = left[index];
int r = right[index];
int newParent = findNew(l);
//implement the rest of the remove here
currentSize--;
}
} else {
//if we have searched the entire tree
if(index == data.length) {
return;
} else {
//keep searching for d
remove(d, index + 1);
}
}
}
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 3 images
