Stack Implementation in Java

Stack is a LIFO (Last In First Out) data structure and supports various operations as specified by the interface below:

public interface IStack<T> {
    public boolean push(T value);
    public T pop();
    public void clear();
    public boolean contains(T value);
    public int size();
}

The Stack can be implemented using an Array or a LinkedList. The Array implementation will be having an underlying array which will be re-sized accordingly. The source code is pretty straight forward and does not need much explanation.

public class ArrayStack<T> implements IStack<T> {
 private static final int MINIMUM_SIZE = 10;
 private T[] array = (T[]) new Object[MINIMUM_SIZE];
 private int size = 0;

 @Override
 public boolean push(T value) {
  int stackSize = this.size;
  if (stackSize >= array.length) {
   array = Arrays.copyOf(array, (stackSize + (stackSize>>1)));
  }
  array[size++] = value;
  return true;
 }

 @Override
 public T pop() {
  if (size <= 0) return null;
  T t = array[--size];
  array[size] = null;
  int stackShrinkSIze = size;
  if (size >= MINIMUM_SIZE && size < (stackShrinkSIze + (stackShrinkSIze<<1))) {
   System.arraycopy(array, 0, array, 0, size);
  }
  return t;
 }
 @Override
 public void clear() {
  size = 0;
 }
 
 @Override
 public boolean contains(T value) {
  for (int i = 0; i < size; i++) {
     T item = array[i];
     if (item.equals(value))
    return true;
  }
  return false;
 }
 @Override
 public int size() {
  return size;
 }
}

Similarly we can make use of LinkedList to implement Stack in Java.

public class LinkedStack<T> implements IStack<T> {
 private Node<T> top = null;
 private int size = 0;

 public LinkedStack() {
  top = null;
  size = 0;
 }
 @Override
 public boolean push(T value) {
  return push(new Node<T>(value));
 }
 private boolean push(Node<T> node) {
  if (top == null) { 
   top = node;
  } else {
   Node<T> oldTop = top;
   top = node;
   top.below = oldTop;
   oldTop.above = top;
  }
  size++;
  return true;
 }
 @Override
 public T pop() {
  if (top==null) return null;

  Node<T> nodeToRemove = top;
  top = nodeToRemove.below;
  if (top != null) top.above = null;

  T value = nodeToRemove.value;
  size--;
  return value;
 }
 @Override
 public void clear() {
  top = null;
  size = 0;
 }
 @Override
 public boolean contains(T value) {
  if (top == null) return false;
  Node<T> node = top;
  while (node != null) {
   if (node.value.equals(value)) return true;
   node = node.below;
  }
  return false;
 }

 @Override
 public int size() {
  return size;
 }
}

On a side note we have a class named Stack in Java as well but it usage is deprecated. That's all. I hope you liked the post!

AVL Binary Search Tree Implementation in Java

AVL (Adelson-Velsky and Landis) is an example of self-balanced Binary Search Tree. It has the same basic operations as that of a regular BST but modifications are followed by zero or more tree rotation operations. Every node also stores balance factor which is corrected after insertion or deletion. If the recomputed balance factor remains in the range from -1 to +1 then only corrections of the balance factor is required and no rotations are necessary. But if the recomputed balance factor becomes less than -1 or greater than +1 the subtree rooted at this node is unbalanced, and a rotation is needed. The AVLNode class (extends Node from BinarySearchTree class) can be declared like:

public static class AVLNode<T extends Comparable<T>> extends Node<T> {
    protected int height = 1;
    protected AVLNode(Node<T> parent, T value) {
        super(parent, value);
    }

    protected boolean isLeaf() {
        return ((getLeft() == null) && (getRight() == null));
    }

    protected void updateHeight() {
        int lesserHeight = 0;
        int greaterHeight = 0;
        if (getLeft() != null) {
            AVLNode<T> lesserAVLNode = (AVLNode<T>) getLeft();
            lesserHeight = lesserAVLNode.height;
        }
        if (getRight() != null) {
            AVLNode<T> greaterAVLNode = (AVLNode<T>) getRight();
            greaterHeight = greaterAVLNode.height;
        }
        if (lesserHeight > greaterHeight) {
            height = lesserHeight + 1;
        } else {
            height = greaterHeight + 1;
        }
    }

    protected int getBalanceFactor() {
        int lesserHeight = 0;
        int greaterHeight = 0;
        if (getLeft() != null) {
            AVLNode<T> lesserAVLNode = (AVLNode<T>) getLeft();
            lesserHeight = lesserAVLNode.height;
        }
        if (getRight() != null) {
            AVLNode<T> greaterAVLNode = (AVLNode<T>) getRight();
            greaterHeight = greaterAVLNode.height;
        }
        return greaterHeight - lesserHeight;
    }

    @Override
    public String toString() {
        return "value=" + getData() + " height=" + height + " parent=" + ((getParent() != null) ? getParent().getData() : "NULL")
                    + " left=" + ((getLeft() != null) ? getLeft().getData() : "NULL") + " right="
                    + ((getRight() != null) ? getRight().getData() : "NULL");
    }
}

The AVLTree class can be declared like:

public class AVLTree<T extends Comparable<T>> extends RotatableBinarySearchTree<T> {
   public AVLTree() { }
}

We need to re-balance after insertion and deletion. Consider the insertion method first

@Override
protected Node<T> insertValue(T id) {
        Node<T> returnedNode = super.insertValue(id);
 AVLNode<T> insertedNode = (AVLNode<T>) returnedNode;
 while (insertedNode != null) {
  insertedNode.updateHeight();
  balanceAfterInsert(insertedNode);
  insertedNode = (AVLNode<T>) insertedNode.getParent();
 }
 return returnedNode;
}

private enum RotationSequence {
        LEFT_LEFT, LEFT_RIGHT, RIGHT_LEFT, RIGHT_RIGHT
};

private void balanceAfterInsert(AVLNode<T> node) {
 int balanceFactor = node.getBalanceFactor();
 
 if (balanceFactor > 1 || balanceFactor < -1) {
  AVLNode<T> parent = null;
  AVLNode<T> child = null;
  RotationSequence rotation = null;
  
  if (balanceFactor < 0) {
   parent = (AVLNode<T>) node.getLeft();
   balanceFactor = parent.getBalanceFactor();
   if (balanceFactor < 0) {
    child = (AVLNode<T>) parent.getLeft();
    rotation = RotationSequence.LEFT_LEFT;
   } else {
    child = (AVLNode<T>) parent.getRight();
    rotation = RotationSequence.LEFT_RIGHT;
   }
  } else {
   parent = (AVLNode<T>) node.getRight();
   balanceFactor = parent.getBalanceFactor();
   if (balanceFactor < 0) {
    child = (AVLNode<T>) parent.getLeft();
    rotation = RotationSequence.RIGHT_LEFT;
   } else {
    child = (AVLNode<T>) parent.getRight();
    rotation = RotationSequence.RIGHT_RIGHT;
   }
  }

  if (rotation == RotationSequence.LEFT_RIGHT) {
   // Left-Right (Left rotation, right rotation)
   rotateLeft(parent);
   rotateRight(node);
  } else if (rotation == RotationSequence.RIGHT_LEFT) {
   // Right-Left (Right rotation, left rotation)
   rotateRight(parent);
   rotateLeft(node);
  } else if (rotation == RotationSequence.LEFT_LEFT) {
   // Left-Left (Right rotation)
   rotateRight(node);
  } else {
   // Right-Right (Left rotation)
   rotateLeft(node);
  }

  node.updateHeight(); // New child node
  child.updateHeight(); // New child node
  parent.updateHeight(); // New Parent node
 }
}

The deletion will be similar and the process is: find the node in tree, find its replacement and replace the node and balance it accordingly.

@Override
protected Node<T> deleteValue(T value) {
 // Find node to remove
 Node<T> nodeToRemoved = this.searchAndGetNode(value);
 if (nodeToRemoved != null) {
  // Find the replacement node
  Node<T> replacementNode = this.getReplacementNode(nodeToRemoved);

  // Find the parent of the replacement node to re-factor the
  // height/balance of the tree
  AVLNode<T> nodeToRefactor = null;
  if (replacementNode != null)
   nodeToRefactor = (AVLNode<T>) replacementNode.getParent();
  if (nodeToRefactor == null)
   nodeToRefactor = (AVLNode<T>) nodeToRemoved.getParent();
  if (nodeToRefactor != null && nodeToRefactor.equals(nodeToRemoved))
   nodeToRefactor = (AVLNode<T>) replacementNode;

  // Replace the node
  deleteAndReplaceNode(nodeToRemoved, replacementNode);

  // Re-balance the tree all the way up the tree
  if (nodeToRefactor != null) {
   while (nodeToRefactor != null) {
    nodeToRefactor.updateHeight();
    balanceAfterDelete(nodeToRefactor);
    nodeToRefactor = (AVLNode<T>) nodeToRefactor.getParent();
   }
  }
 }
 return nodeToRemoved;
}

private void balanceAfterDelete(AVLNode<T> node) {
 int balanceFactor = node.getBalanceFactor();
 if (balanceFactor == -2 || balanceFactor == 2) {
  if (balanceFactor == -2) {
   AVLNode<T> ll = (AVLNode<T>) node.getLeft().getLeft();
   int lesser = (ll != null) ? ll.height : 0;
   AVLNode<T> lr = (AVLNode<T>) node.getLeft().getRight();
   int greater = (lr != null) ? lr.height : 0;
   if (lesser >= greater) {
    rotateRight(node);
    node.updateHeight();
    if (node.getParent() != null)
     ((AVLNode<T>) node.getParent()).updateHeight();
   } else {
    rotateLeft(node.getLeft());
    rotateRight(node);

    AVLNode<T> p = (AVLNode<T>) node.getParent();
    if (p.getLeft() != null)
     ((AVLNode<T>) p.getLeft()).updateHeight();
    if (p.getRight() != null)
     ((AVLNode<T>) p.getRight()).updateHeight();
    p.updateHeight();
   }
  } else if (balanceFactor == 2) {
   AVLNode<T> rr = (AVLNode<T>) node.getRight().getRight();
   int greater = (rr != null) ? rr.height : 0;
   AVLNode<T> rl = (AVLNode<T>) node.getRight().getLeft();
   int lesser = (rl != null) ? rl.height : 0;
   if (greater >= lesser) {
    rotateLeft(node);
    node.updateHeight();
    if (node.getParent() != null)
     ((AVLNode<T>) node.getParent()).updateHeight();
   } else {
    rotateRight(node.getRight());
    rotateLeft(node);

    AVLNode<T> p = (AVLNode<T>) node.getParent();
    if (p.getLeft() != null)
     ((AVLNode<T>) p.getLeft()).updateHeight();
    if (p.getRight() != null)
     ((AVLNode<T>) p.getRight()).updateHeight();
    p.updateHeight();
   }
  }
 }
}

Remaining methods are inherited from BinarySearchTree class. So the major changes are in insertion/deletion along with re-balancing efforts. But considering the benefits it provide it is worth it.

Self-balancing Binary Search Tree

Before we go any further lets see what will happen  if we insert sorted numbers into a regular Binary Search Tree (BST). Suppose we enter 10,20,30,40 and 50 in the same order. Then what we will get is a highly unbalanced BST:

Actually it has become a linked list now. You can read more about skewed BSTs here. As it hurts the performance badly there is always a need for balance Binary Search Tree.

A self balanced binary search tree is the one that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. An example is AVL (Adelson-Velsky and Landis) Binary Search Tree which makes use of rotations to keep itself balanced.

As per wikipedia: "In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations."

The wi-ki page also demonstrates how rotation works:

AVL tree is generally compared with Red-Black tree as both have certain common properties and both support the concept of rotation. They also support same operations and take O(log n) time for basic operations (For purists they actually take O(lg n) time but base does not matter much in this case as they will show same pattern). For look up intensive applications AVL trees are supposed to be faster than Red-Black trees but both are height balanced.

We have already covered implementation of Binary Search Tree in previous article. Here I will create an abstract class that will have methods for rotation as well.

abstract public class RotatableBinarySearchTree<T extends Comparable<T>> extends BinarySearchTree<T> {
    protected enum Position {
       LEFT, RIGHT
    };
    public RotatableBinarySearchTree() { }
}

The methods that will perform rotation are: rotateLeft and rotateRight. These are shown below:

protected void rotateLeft(Node<T> node) {
 Position parentPosition = null;
 Node<T> parent = node.getParent();
 if (parent != null) {
  if (node.equals(parent.getLeft())) {
   // Lesser
   parentPosition = Position.LEFT;
  } else {
   // Greater
   parentPosition = Position.RIGHT;
  }
 }

 Node<T> greater = node.getRight();
 node.setRight(null);
 Node<T> lesser = greater.getLeft();

 greater.setLeft(node);
 node.setParent(greater);

 node.setRight(lesser);
 if (lesser != null)
  lesser.setParent(node);

 if (parentPosition != null) {
  if (parentPosition == Position.LEFT) {
   parent.setLeft(greater);
  } else {
   parent.setRight(greater);
  }
  greater.setParent(parent);
 } else {
  root = greater;
  greater.setParent(null);
 }
}

protected void rotateRight(Node<T> node) {
 Position parentPosition = null;
 Node<T> parent = node.getParent();
 if (parent != null) {
  if (node.equals(parent.getLeft())) {
   // Lesser
   parentPosition = Position.LEFT;
  } else {
   // Greater
   parentPosition = Position.RIGHT;
  }
 }

 Node<T> lesser = node.getLeft();
 node.setLeft(null);
 Node<T> greater = lesser.getRight();

 lesser.setRight(node);
 node.setParent(lesser);

 node.setLeft(greater);
 if (greater != null)
  greater.setParent(node);

 if (parentPosition != null) {
  if (parentPosition == Position.LEFT) {
   parent.setLeft(lesser);
  } else {
   parent.setRight(lesser);
  }
  lesser.setParent(parent);
 } else {
  root = lesser;
  lesser.setParent(null);
 }
}

This abstract class provides method for rotation and will be extended by the implementation of AVL and Red-Black Trees when we will discuss them.

Binary Search Tree implementation in Java

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:

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:

1. First locate the node that needs to be deleted.
2. 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.
3. Then we need to delete this node and replace it with its replacement found in step 2.

This is performed by the following code:

        @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.