Binary search tree node class：
public class MemberBSTNode{
private MemberBSTNode leftNode;
private MemberBSTNode rightNode;
private Member member;
public MemberBSTNode() {
}
public MemberBSTNode(Member member) {
this.member = member;
}
public MemberBSTNode getLeftNode() {
return leftNode;
}
public void setLeftNode(MemberBSTNode leftNode) {
this.leftNode = leftNode;
}
public MemberBSTNode getRightNode() {
return rightNode;
}
public void setRightNode(MemberBSTNode rightNode) {
this.rightNode = rightNode;
}
public Member getMember() {
return member;
}
public void setMember(Member member) {
this.member = member;
}
@Override
public String toString() {
return "MemberBSTNode{" +
"leftNode=" + leftNode +
", rightNode=" + rightNode +
'}';
}
}
Binary search tree class
public class MemberBST implements IMemberDB {
private MemberBSTNode root;
private int treeSize;
public MemberBST() {
System.out.println("Binary Search Tree");
}
@Override
public void clearDB() {
root = null;
}
@Override
public boolean containsName(String name) {
assert name != null;
MemberBSTNode node = this.root;
while (node != null){
if (node.getMember().getName().compareTo(name) == 0){
return true; // Found the member with the specified name
} else if (node.getMember().getName().compareTo(name) < 0) {
node = node.getRightNode(); // Go right
} else {
node = node.getLeftNode(); // Go left
}
}
// Not found
return false;
}
@Override
public Member get(String name) {
System.out.println("get a member");
assert name != null;
// Start searching from the root node
MemberBSTNode node = this.root;
while (node != null){
System.out.println(node);
if (node.getMember().getName().compareTo(name) == 0){
System.out.println("Found the member with the specified name: " + name);
return node.getMember(); // Found the member with the specified name
} else if (node.getMember().getName().compareTo(name) < 0) {
node = node.getRightNode(); // Go right for larger values
} else {
node = node.getLeftNode(); // Go left for smaller values
}
}
return null; // Member not found
}
@Override
public int size() {
return this.treeSize;
}
@Override
public boolean isEmpty() {
return root == null;
}
@Override
public Member put(Member member) {
System.out.println("put a memeber");
assert member != null;
// If the tree is empty, create a new root node with the member
this.treeSize++;
if (root == null){
this.root = new MemberBSTNode(member);
return member;
}
MemberBSTNode node = this.root;
while (node != null){
System.out.println(node);
if (node.getMember().getName().compareTo(member.getName()) < 0){
// Go right if the name is greater than the current node's name
if (node.getRightNode() == null){
node.setRightNode(new MemberBSTNode(member));
return member; // Inserted successfully
} else {
node = node.getRightNode();
}
} else if (node.getMember().getName().compareTo(member.getName()) > 0){
// Go left if the name is less than the current node's name
if (node.getLeftNode() == null){
node.setLeftNode(new MemberBSTNode(member));
System.out.println("Inserted successfully");
System.out.println(member);
return member; // Inserted successfully
} else {
node = node.getLeftNode();
}
} else {
return member; // Member with the same name already exists
}
}
return member;
}
@Override
public Member remove(String name) {
System.out.println("remove a member");
assert name != null;
// Call the delete method to remove the member node
MemberBSTNode memberBSTNode = delete(this.root, name);
System.out.println("Removed member: " + name);
return memberBSTNode.getMember();
}
private MemberBSTNode delete(MemberBSTNode root, String name){
if (root == null){
return null; // Empty tree or member not found
}
System.out.println(root);
if (root.getMember().getName().compareTo(name) > 0){
root.setLeftNode(delete(root.getLeftNode(), name)); // Go left
} else if (root.getMember().getName().compareTo(name) < 0){
root.setRightNode(delete(root.getRightNode(), name)); // Go right
} else {
if (root.getLeftNode() == null){
return root.getRightNode(); // No left child
} else if (root.getRightNode() == null) {
return root.getLeftNode(); // No right child
}
// Node has both left and right children
MemberBSTNode successor = findSuccessor(root.getRightNode());
root.setMember(successor.getMember());
root.setRightNode(delete(root.getRightNode(),
successor.getMember().getName()));
}
return root; // Return the updated subtree root
}
private MemberBSTNode findSuccessor(MemberBSTNode node){
while (node.getLeftNode() != null){
node = node.getLeftNode(); // Go left until reaching the smallest node
}
return node;
}
@Override
public void displayDB() {
inOrder(this.root);
}
private void inOrder(MemberBSTNode root){
if (root == null){
return;
}
// Traverse left subtree
inOrder(root.getLeftNode());
// Print the member value at the current node
System.out.println(root.getMember());
// Traverse right subtree
inOrder(root.getRightNode());
}
public MemberBSTNode getRoot() {
return root;
}
public void setRoot(MemberBSTNode root) {
this.root = root;
}
