Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. This post is not about the basics of BST, in case you are interested please check this pdf.

I will first declare an interface ITree which we assume all our tree implementations to implement:

I will first declare an interface ITree which we assume all our tree implementations to implement:

public interface Tree<T> { public boolean insert(T value); public T delete(T value); public void clear(); public boolean contains(T value); public int size(); }

This interface can be implemented by the class as follows:

public class BinarySearchTree<T extends Comparable<T>> implements Tree<T> { protected Node<T> root = null; protected int size = 0; public BinarySearchTree() { } }

We have used generics and we also want elements to be mutually comparable. We will first provide implementation of insert method as:

@Override public boolean insert(T value) { Node<T> nodeAdded = this.insertValue(value); return (nodeAdded != null); } protected Node<T> insertValue(T value) { Node<T> newNode = getNewNode(value); // If root is null, assign if (root == null) { root = newNode; size++; return newNode; } Node<T> currentNode = root; while (currentNode != null) { if (newNode.getData().compareTo(currentNode.getData()) <= 0) { // Less than or equal to goes left if(currentNode.getLeft() == null) { insertNodeToLeft(currentNode, newNode); break; } currentNode = currentNode.getLeft(); } else { // Greater than goes right if (currentNode.getRight() == null) { insertNodeToRight(currentNode, newNode); break; } currentNode = currentNode.getRight(); } } return newNode; }

The insert method will insert the node in left or right branch based on its value. The deletion part is slightly tricky. The process of deletion is as follows:

- First locate the node that needs to be deleted.
- Then find the replacement node for this node. We can select from left or right subtree and we do not want to select from one subtree all the time as it can lead to skewed tree.
- Then we need to delete this node and replace it with its replacement found in step 2.

@Override public T delete(T value) { Node<T> nodeToRemove = this.deleteValue(value); return ((nodeToRemove!=null)?nodeToRemove.getData():null); } protected Node<T> deleteValue(T value) { Node<T> nodeToRemoved = this.searchAndGetNode(value); if (nodeToRemoved != null) nodeToRemoved = deleteNode(nodeToRemoved); return nodeToRemoved; } protected Node<T> searchAndGetNode(T value) { Node<T> currentNode = root; while (currentNode != null && currentNode.getData() != null) { int valueComparison = value.compareTo(currentNode.getData()); if (valueComparison == 0) { return currentNode; } else if (valueComparison < 0) { currentNode = currentNode.getLeft(); } else { currentNode = currentNode.getRight(); } } return null; } protected Node<T> deleteNode(Node<T> nodeToRemoved) { if (nodeToRemoved != null) { Node<T> replacementNode = this.getReplacementNode(nodeToRemoved); deleteAndReplaceNode(nodeToRemoved, replacementNode); } return nodeToRemoved; } protected Node<T> getReplacementNode(Node<T> nodeToRemoved) { Node<T> replacement = null; if (nodeToRemoved.getLeft() != null && nodeToRemoved.getRight() == null) { // Using the less subtree replacement = nodeToRemoved.getLeft(); } else if (nodeToRemoved.getRight() != null && nodeToRemoved.getLeft() == null) { // Using the greater subtree (there is no lesser subtree) replacement = nodeToRemoved.getRight(); } else if (nodeToRemoved.getRight() != null && nodeToRemoved.getLeft() != null) { // Two children add some randomness to deletions, so we don't always use the greatest/least on deletion if (toggleReplacementNodeSelection) { replacement = this.getLargestNodeInSubTree(nodeToRemoved.getLeft()); if (replacement == null) replacement = nodeToRemoved.getLeft(); } else { replacement = this.getSmallestNodeInSubTree(nodeToRemoved.getRight()); if (replacement == null) replacement = nodeToRemoved.getRight(); } toggleReplacementNodeSelection = !toggleReplacementNodeSelection; } return replacement; } protected void deleteAndReplaceNode(Node<T> nodeToDelete, Node<T> replacementNode) { if (replacementNode != null) { // Record left and right child of replacementNode for later use Node<T> leftChildOfReplacementNode = replacementNode.getLeft(); Node<T> rightChildOfReplacementNode = replacementNode.getRight(); // For left and right children of nodeToDelete, new parent is replacementNode Node<T> leftChildOfNodeToDelete = nodeToDelete.getLeft(); if (leftChildOfNodeToDelete != null && !leftChildOfNodeToDelete.equals(replacementNode)) { replacementNode.setLeft(leftChildOfNodeToDelete); leftChildOfNodeToDelete.setParent(replacementNode); } Node<T> rightChildOfNodeToDelete = nodeToDelete.getRight(); if (rightChildOfNodeToDelete != null && !rightChildOfNodeToDelete.equals(replacementNode)) { replacementNode.setRight(rightChildOfNodeToDelete); rightChildOfNodeToDelete.setParent(replacementNode); } // Update the link of parent of replacementNode as well. For the parent of replacementNode kids of replacementNode are its new kids. In short grand-kids are kids now. Node<T> parentOfReplacementNode = replacementNode.parent; if (parentOfReplacementNode != null && !parentOfReplacementNode.equals(nodeToDelete)) { Node<T> leftChildOfParentOfReplacementNode = parentOfReplacementNode.getLeft(); Node<T> rightChildOfParentOfReplacementNode = parentOfReplacementNode.getRight(); // Check whether the replacementNode is left or right child of its parent. if (leftChildOfParentOfReplacementNode != null && leftChildOfParentOfReplacementNode.equals(replacementNode)) { parentOfReplacementNode.setLeft(rightChildOfReplacementNode); if (rightChildOfReplacementNode != null) rightChildOfReplacementNode.setParent(parentOfReplacementNode); } else if (rightChildOfParentOfReplacementNode != null && rightChildOfParentOfReplacementNode.equals(replacementNode)) { parentOfReplacementNode.setRight(leftChildOfReplacementNode); if (leftChildOfReplacementNode != null) leftChildOfReplacementNode.setParent(parentOfReplacementNode); } } } // Update the link in the tree from the nodeToRemoved to the replacementNode Node<T> parentOfNodeToDelete = nodeToDelete.getParent(); if (parentOfNodeToDelete == null) { // We are deleting root node. So replacing the root node. root = replacementNode; if (root != null) root.parent = null; } else if (parentOfNodeToDelete.getLeft() != null && (parentOfNodeToDelete.getLeft().getData().compareTo(nodeToDelete.getData()) == 0)) { parentOfNodeToDelete.setLeft(replacementNode); if (replacementNode != null) replacementNode.parent = parentOfNodeToDelete; } else if (parentOfNodeToDelete.getRight() != null && (parentOfNodeToDelete.getRight().getData().compareTo(nodeToDelete.getData()) == 0)) { parentOfNodeToDelete.setRight(replacementNode); if (replacementNode != null) replacementNode.parent = parentOfNodeToDelete; } size--; }

Now the remaining methods are relatively easy ones.

@Override public void clear() { root = null; size = 0; } @Override public boolean contains(T value) { Node<T> node = searchAndGetNode(value); return (node != null); } @Override public int size() { return size; }

This completes the implementation of BST in Java.

## No comments:

Post a Comment