Computer Science Tree Question

Question

Hello,

I am currently attempting to complete a project for my computer science class and we have to implement a ternary tree as a sort of database of different cat objects. I know that my method to add cats to the tree is correct but I can't figure out how to do the delete method.

This is a clearer description of the project from the directions:

The database of all cats is represented by a ternary tree CatTree. This tree has a single field root which contains a reference to the root node. The nodes are defined by a private nested class CatNode. Each CatNode is associated with data stored in a CatInfo object (code provided). This CatInfo class stores data into the following fields:

• String name: the name of the cat.

• int monthHired: the time at which the cat was hired.

• int furThickness: the average thickness of the cat’s fur in millimeters

• int nextGroomingAppointment: the month in which we expect the next grooming appointment

The CatTree class contains a CatNode inner class, and a field root, which contains the root node of the tree. It also implements Iterable and includes a CatTreeIterator inner class.

The CatNode inner class contains the information about the tree structure:

• CatInfo data: the CatInfo object with the data for this cat.

• CatNode senior: this cat and all the children of its node have more seniority than the current node’s cat.

• CatNode junior: this cat and all the children of its node have less seniority than the current node’s cat.

• CatNode same: this cat and all the children of its node have exactly the same seniority than the current node’s cat. In addition, in the structure of the tree, CatNodes with equal seniority should be sorted in decreasing order of fur thickness.

Below is my code for adding:

public CatNode addCat(CatNode c) {

CatNode currentNode = this;

CatNode newNode = new CatNode(c.data);

if(currentNode != null) {

if(newNode.data.monthHired < currentNode.data.monthHired) {

if(currentNode.senior == null) {currentNode.senior=newNode;}

else {currentNode.senior=currentNode.senior.addCat(newNode);}

}

else if(newNode.data.monthHired > currentNode.data.monthHired) {

if(currentNode.junior == null) {currentNode.junior = newNode;}

else {currentNode.junior=currentNode.junior.addCat(newNode);}

}

else if(newNode.data.monthHired == currentNode.data.monthHired) {

if(newNode.data.furThickness < currentNode.data.furThickness) {

if(currentNode.same == null) {currentNode.same=newNode;}

else {currentNode.same = currentNode.same.addCat(newNode);}

}

else if(newNode.data.furThickness > currentNode.data.furThickness) {

if(currentNode.same == null) {

currentNode.same = new CatNode(currentNode.data);

currentNode.data = newNode.data;

}

else {

CatNode temp;

temp = new CatNode(currentNode.data);

currentNode.data = newNode.data;

currentNode.same = currentNode.same.addCat(temp);

}

}

}

}

return this;

}

And my attempt at deletion:

if(nodeToRemove.same != null) {

nodeToRemove.same = nodeToRemove;

root = nodeToRemove.same;

nodeToRemove = null;

}

else if(nodeToRemove.same == null && nodeToRemove.senior != null) {

nodeToRemove.senior = nodeToRemove;

root = nodeToRemove.senior;

nodeToRemove = null;

}

else {

nodeToRemove.junior = nodeToRemove;

root = nodeToRemove.junior;

nodeToRemove = null;

}

I know this is a very big question but if you can't assist with it could you at least provide some insight into ternary search trees that contain objects like this because I can not find ANYTHING online about them.

Thank you so much!

Answer 1

Lets see how we can write delete node in a better format keeping the above concepts in mind:

I have added comments as well for better understanding.

public CatNode removeCat(CatInfo c) {

//cat to remove is SENIOR to this.

if(this.data.monthHired > c.monthHired) {

if(this.senior != null)

this.senior = this.senior.removeCat(c);

else

return this;

}

//cat to remove is JUNIOR to this.

else if(this.data.monthHired < c.monthHired ) {

if(this.junior !=null)

this.junior = this.junior.removeCat(c);

else

return this;

}

//cat to remove is SAME to this(have same monthHired), compare furThickness.

else {

//if c`s Fur is SMALLER than THIS, removeCAt(c) on the SAME node;

if(c.furThickness < this.data.furThickness) {

if(this.same != null)

this.same = this.same.removeCat(c);

else

return this;

}

//both c and THIS have the same furThickness and monthHired

else if(c.furThickness == this.data.furThickness) {

//We`ve found Cat to remove as the root.

if(c.equals(this.data)) {

//case 1: cat has a SAME: set the parent link to be the root and set reference to this and return same

if(this.same != null) {

this.data = this.same.data;

this.same = this.same.same;

return this;

}

//case 2: cat has NO SAME but has SENIOR, set the parent link to this SENIOR

else if(this.senior != null) {

//if this senior has a JUNIOR, place it in the SENIOR`s subtree.

if(this.junior != null) {

this.senior.addCat(this.junior);

}

return this.senior;

}

//case 3: cat has no SAME, no SENIOR but has JUNIOR. set parent link to this`s JUNIOR

else if(this.junior != null) {

return this.junior;

}

//cat has no SAME, no JUNIOR, no SENIOR, set parent link to null

else {

return null;

}

}

}

}

return this;

}

Hope this helps. :)

Happy coding !