Implementation of the AVL Tree in Java

In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child sub-trees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.

The following is my implementation of an AVL tree Java library, which supports methods for insertion, deletion, and look-up. The data structure is simple. AVLNode has the following fields:

protected AVLNode left, right, parent;
protected Integer value, height;
private Object object; //An additional field for data to be stored in an AVLNode

And an AVLTree object represents an AVL tree composed of AVLNode objects.

You can download the Java library from http://sites.google.com/site/moderntone/AVLTree.zip




AVLTree.java

package com.avltree;

public class AVLTree {

 private AVLNode root;

 public AVLTree(int... values) {
  for (int value : values)
   insert(value);
 }

 public AVLNode getRoot() {
  return root;
 }

 public void insert(AVLNode node){
  if (root == null)
   root = node;
  else {
   root.insertToLeaf(node);
   AVLNode keyNode = updateHeightsAndDetectKeyNode(node);
   if (keyNode != null) // rotate to adjust the tree
    adjustTreeByRotation(keyNode);
  }
 }
 
 private void insert(int value){
  if (root == null)
   root = new AVLNode(value);
  else {
   AVLNode newNode = new AVLNode(value);
   root.insertToLeaf(newNode);
   AVLNode keyNode = updateHeightsAndDetectKeyNode(newNode);
   if (keyNode != null) // rotate to adjust the tree
    adjustTreeByRotation(keyNode);
  }
 }

 public void delete(AVLNode node){
  int value = node.value;
  delete(value);
 }
 
 public void delete(int value) {
  AVLNode parentOfDeletedLeaf = deleteBeforeAdjustment(value);
  if (parentOfDeletedLeaf != null) {
   AVLNode keyNode = detectKeyNode(parentOfDeletedLeaf);
   if (keyNode != null){
    AVLNode newkeyNode = adjustTreeByRotation(keyNode);
    updateHeights(newkeyNode.parent);
   }
  } else {
   System.out.println("The AVLTree doesn't contain " + value);
  }
 }

 private AVLNode detectKeyNode(AVLNode parentOfDeletedLeaf){
  AVLNode currentNode = parentOfDeletedLeaf;
  while (currentNode != null) {
   int bf = currentNode.getBalanceFactor();
   if (bf == 2 || bf == -2)
    return currentNode;
   else 
    currentNode = currentNode.parent;
  }
  return null;
 }
 
 private AVLNode deleteBeforeAdjustment(int value) {
  AVLNode currentNode = root;
  while (currentNode != null) {
   if (currentNode.value == value)
    break;
   else
    currentNode = value < currentNode.value ? 
     currentNode.left : currentNode.right;
  }

  if (currentNode != null) {
   while (!currentNode.isLeaf()) {
    AVLNode replacement = currentNode.getBalanceFactor() < 0 ? 
     currentNode.right.getLeftmost() : currentNode.left.getRightmost();
    currentNode.value = replacement.value;
    currentNode = replacement;
   }

   AVLNode parent = currentNode.getParent();
   if (parent == null) root = null;
   else if (currentNode == parent.left) 
    parent.setLeft(null);
   else 
    parent.setRight(null);
   updateHeights(parent);
   return parent;
  }
  return null;
 }

 private void updateHeights(AVLNode fromParentOfDeletedLeaf){
  AVLNode currentNode = fromParentOfDeletedLeaf;
  currentNode.adjustHeight();
  while (currentNode != null){
   currentNode.adjustHeight();
   currentNode = currentNode.parent;
  }
 }
 
 /**
  * called by insert(int) keyNode: the node closest to the newly inserted
  * node where |BF|>1
  * @param newNode : newly added leaf AVLNode
  * @return keyNode
  */
 private AVLNode updateHeightsAndDetectKeyNode(AVLNode newNode) {
  AVLNode keyNode = null;
  while (newNode.parent != null) {
   if (newNode.getParent().height - newNode.height != 1) {
    if (keyNode == null) {
     int bf_parent = newNode.getParent().getBalanceFactor();
     if (bf_parent > 1 || bf_parent < -1) {
      keyNode = newNode.getParent();
      break;
     }
    }
    newNode.getParent().height++;
    newNode = newNode.getParent();
   } else
    break;
  }
  return keyNode;
 }

 public AVLNode lookup(int value) {
  AVLNode currentNode = root;
  while (currentNode != null) {
   if (currentNode.value == value)
    return currentNode;
   else
    currentNode = value < currentNode.value ? 
     currentNode.left : currentNode.right;
  }
  System.out.println("The AVLTree doesn't contain " + value);
  return null;
 }

 /**
  * LL or LR type if balance factor == 2; rotateRight for keyNode if bf of
  * keyNode.left == -1, it's LR type; rotateLeft for keyNode.left first RR or
  * RL type if balance factor == -2; rotateLeft for keyNode if bf of
  * keyNode.right == 1, it's RL type; rotateRight for keyNode.right first
  * 
  * @param keyNode
  */
 private AVLNode adjustTreeByRotation(AVLNode keyNode) {
  AVLNode newKeyNode = null;
  int bf_keyNode = keyNode.getBalanceFactor();
  if (bf_keyNode == 2) {
   if (keyNode.left.getBalanceFactor() == -1) // LR
    keyNode.setLeft(keyNode.left.rotateLeft());
   newKeyNode = keyNode.rotateRight();
  } else if (bf_keyNode == -2) {
   if (keyNode.right.getBalanceFactor() == 1) // RL
    keyNode.setRight(keyNode.right.rotateRight());
   newKeyNode = keyNode.rotateLeft();
  } else {
   new Exception("There are some bugs").printStackTrace();
  }

  if (keyNode.parent == null) {
   root = newKeyNode;
   root.parent = null;
  }
  else {
   if (keyNode == keyNode.parent.left)
    keyNode.parent.setLeft(newKeyNode);
   else
    keyNode.parent.setRight(newKeyNode);
   newKeyNode.parent.adjustHeight();
  }
  return newKeyNode;
 }

 public void print(Order order) {
  switch (order) {
  case PREORDER:
   root.print_preorder();
   break;
  case INORDER:
   root.print_inorder();
   break;
  case POSTORDER:
   root.print_postorder();
   break;
  }
 }
}

AVLNode.java

package com.avltree;

public class AVLNode {

 protected AVLNode left, right, parent;
 protected Integer value, height;
 private Object object; //enable the AVLTree to store additional info
 
 public AVLNode(int value){
  this.value = value;
  this.height = 0;
 }
 
 public AVLNode(int value, Object object){
  this.value = value;
  this.height = 0;
  this.object = object;
 }
 
 public AVLNode(AVLNode node){
  this.value = node.value;
  this.height = node.height;
  this.left = node.left;
  this.right = node.right;
 }
 
 public Object getObject() {
  return object;
 }

 public void setObject(Object object) {
  this.object = object;
 }
 
 public int getValue(){
  return value;
 }
 
 public AVLNode getParent() {
  return parent;
 }
 
 public AVLNode getLeft() {
  return left;
 }
 
 protected void setLeft(AVLNode left){
  this.left = left;
  if (left != null)
   left.parent = this;
 }
 
 public AVLNode getRight() {
  return right;
 }
 
 protected void setRight(AVLNode right){
  this.right = right;
  if (right != null)
   right.parent = this;
 }
 
 public int getHeight() {
  return height;
 }
 
 public int getLevel(){
  int level = 0;
  AVLNode currentNode = this;
  while ((currentNode = currentNode.parent) != null)
   level++;
  return level;
 }
 
 protected int getBalanceFactor(){
  int leftHeight = getLeftHeight();
  int rightHeight = getRightHeight();
  return leftHeight - rightHeight;
 }
 
 protected void insertToLeaf(AVLNode node){
  if (node.value == value){
   System.out.println("Duplicate node " + value);
   return;
  }
  else {
   if (node.value < value){
    if (left == null)   setLeft(node);
    else left.insertToLeaf(node);
   }
   else {
    if (right == null) setRight(node);
    else right.insertToLeaf(node);
   }
  }
 }
 
 
 /**rotate right
  * change of height should be added;
  * applies to the LL type situation 
  */
 protected AVLNode rotateRight(){
  AVLNode newRight = new AVLNode(this);
  newRight.height = getRightHeight() + 1;
  newRight.setLeft(left.right);
  left.setRight(newRight);
  left.adjustHeight();
  return left;
 }

 /**
  * rotate left
  * change of height should be added;
  * applies to the LL type situation 
  */
 protected AVLNode rotateLeft(){
  AVLNode newLeft = new AVLNode(this);
  newLeft.height = getLeftHeight() + 1;
  newLeft.setRight(right.left);
  right.setLeft(newLeft);
  right.adjustHeight();
  return right;
 }
 
 protected void adjustHeight(){
  int leftHeight = getLeftHeight();
  int rightHeight = getRightHeight();
  height = (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
 } 
 
 protected int getLeftHeight(){
  return left == null ? -1 : left.height; 
 }
 
 protected int getRightHeight(){
  return right == null ? -1 : right.height;
 }
 
 protected boolean isLeaf(){
  return left == null && right == null;
 }
 
 protected AVLNode getLeftmost(){
  AVLNode leftmost = this;
  while (leftmost.left != null)
   leftmost = leftmost.left;
  return leftmost;
 }
 
 protected AVLNode getRightmost(){
  AVLNode rightmost = this;
  while (rightmost.right != null)
   rightmost = rightmost.right;
  return rightmost;
 }
 
 
 //////////
 protected void print_preorder(){
  System.out.print(value + " ");
  if (left != null) left.print_preorder();
  if (right != null) right.print_preorder();
 }

 protected void print_inorder(){
  if (left != null) left.print_inorder();
  System.out.print(value + " ");
  if (right != null) right.print_inorder();
 }
 
 protected void print_postorder(){
  if (left != null) left.print_postorder();
  if (right != null) right.print_postorder();
  System.out.print(value + " ");
 }
}

Order.java

package com.avltree;

public enum Order{
 PREORDER, INORDER, POSTORDER
}

Test.java

package com.test;

import com.avltree.*;

public class Test {

 public static void main(String[] args) {

//  int[] values = new int[] {23, 18, 12, 8, 14, 20, 44, 52 };
  
  AVLTree tree = new AVLTree(23,18,44,12,20,52,4,14,16); //LR
//  AVLTree tree = new AVLTree(18,12,44,23,52,20,20); //RL 
//  AVLTree tree = new AVLTree(18,20,12,14,8,4); //LL
//  AVLTree tree = new AVLTree(14,12,20,18,23,44); //RR
//  AVLTree tree = new AVLTree(23,18,12);   //simple LL
  
//  AVLTree tree = new AVLTree(50, 20, 80, 10, 30, 60, 90, 70); //test delete
  
  AVLNode root = tree.getRoot();
  System.out.println(root.getValue() + ", with height " + root.getHeight());
  System.out.println(root.getLeft().getValue() + ", with height " + root.getLeft().getHeight());
  System.out.println(root.getRight().getValue() + ", with height " + root.getRight().getHeight());

  System.out.println(root.getLeft().getLeft().getValue() + ", with height " + root.getLeft().getLeft().getHeight());
  System.out.println(root.getRight().getRight().getValue() + ", with height " + root.getRight().getRight().getHeight());

  int toBeDeleted = 90;
  System.out.println("After deleting " + toBeDeleted);
  tree.delete(toBeDeleted);
  System.out.println(root.getValue() + ", with height " + root.getHeight());
  System.out.println(root.getRight().getValue() + ", with height " + root.getRight().getHeight());
//  System.out.println(root.getRight().getRight().getValue() + ", with height " + root.getRight().getRight().getHeight());
//  System.out.println(root.getRight().getLeft().getValue() + ", with height " + root.getRight().getLeft().getHeight());
//  System.out.println(root.getLeft().getRight() == null);
  
  tree.print(Order.PREORDER);

 }
}

An Implementation of the Tic-Tac-Toe Artificial Intelligence in Java

This is my Java implementation of the Tic-Tac-Toe artificial intelligence. The first player, O, is the user, and the second player, X, is the computer.

The algorithm is simple and effective but may not be entirely perfect. The heuristic rules are simply grounded on those basic strategies I put together for playing Tic-Tac-Toe games and presented in the private int computeHeuristicScoreAt(int position) method in ArtificialIntelligence.java below.

You can download the Java source codes in http://sites.google.com/site/moderntone/TicTacToe.zip and the executable jar file along with the two images in http://sites.google.com/site/moderntone/TicTacToeExecutableJar.zip









ArtificialIntelligence.java

package com.tictactoe;

import java.awt.Image;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.util.*;

import javax.swing.*;
import javax.swing.table.DefaultTableModel;

public class ArtificialIntelligence extends MouseAdapter{
 
 /** Indexes of the nine positions:
  * 0 1 2
  * 3 4 5
  * 6 7 8 
  */
 private int[] situation; // length = 9; 0: empty; 1: O; 2: X private JTable table;
 private Integer[] heuristicScoresAndPositions;
 
 public ArtificialIntelligence(JTable table){
  this.table = table;
  situation = new int[9];
  
 }
 
 private static final HashMap<Integer, List<Integer>> linesMap;
 
 static {
  linesMap = new HashMap<Integer, List<Integer>>();
  
  List<Integer> lines = new ArrayList<Integer>();
  lines.add((1 << 4) + 2); lines.add((3 << 4) + 6);
  lines.add((4 << 4) + 8); 
linesMap.put(0, lines);
  
  lines = new ArrayList<Integer>();
  lines.add((0 << 4) + 2); lines.add((4 << 4) + 7);
  linesMap.put(1, lines);
  
  lines = new ArrayList<Integer>();
  lines.add((0 << 4) + 1); lines.add((4 << 4) + 6);
  lines.add((5 << 4) + 8);
  linesMap.put(2, lines);
  
  lines = new ArrayList<Integer>();
  lines.add((0 << 4) + 6); lines.add((4 << 4) + 5);
  linesMap.put(3, lines);
  
  lines = new ArrayList<Integer>();
  lines.add((0 << 4) + 8); lines.add((2 << 4) + 6);
  lines.add((1 << 4) + 7); lines.add((3 << 4) + 5);
  linesMap.put(4, lines);
  
  lines = new ArrayList<Integer>();
  lines.add((2 << 4) + 8); lines.add((3 << 4) + 4);
  linesMap.put(5, lines);
  
  lines = new ArrayList<Integer>();
  lines.add((0 << 4) + 3); lines.add((2 << 4) + 4);
  lines.add((7 << 4) + 8);
  linesMap.put(6, lines);
  
  lines = new ArrayList<Integer>();
  lines.add((1 << 4) + 4); lines.add((6 << 4) + 8);
  linesMap.put(7, lines);
  
  lines = new ArrayList<Integer>();
  lines.add((0 << 4) + 4); lines.add((2 << 4) + 5);
  lines.add((6 << 4) + 7);
  linesMap.put(8, lines);
 }
 
 private boolean checkWhetherTheCurrentPlayerWins(int position, boolean byUser){
  List<Integer> possibleLines = linesMap.get(position);
  for (Integer anotherTwoPositions : possibleLines){
   int p1 = anotherTwoPositions >> 4, p2 = anotherTwoPositions & 0xf;
   if (byUser){
    if (situation[p1] * situation[p2] == 1) 
     return true;
   }
   else 
    if (situation[p1] + situation[p2] == 4) 
    return true;
  }
  return false;
 }
 
 @Override
 public void mousePressed(MouseEvent e) {
  boolean notEnded = playByUser(e);
  try {
   Thread.sleep(100);
  } catch (InterruptedException e1) {
   e1.printStackTrace();
  }
  if (notEnded)
   playByComputer();
 }

 private void computeHeuristicScores(){
  heuristicScoresAndPositions = new Integer[9]; //score << 8 + row << 4 + column 
  for (int i = 0 ; i < 9 ; i++){
   heuristicScoresAndPositions[i] = (situation[i] > 0) ? 
     i : computeHeuristicScoreAt(i) + i; 
  }
 }
 
 private int computeHeuristicScoreAt(int position){
  List<Integer> possibleLines = linesMap.get(position);
  
  int h = 0;
  for (Integer line : possibleLines){
   int p1 = line >> 4, p2 = line & 0xf;
   int zeroCount = 0, oneCount = 0, twoCount = 0;
   
   switch (situation[p1]) {
   case 0:  zeroCount++; break;
   case 1:  oneCount++; break;
   default: twoCount++; break;
   }
   switch (situation[p2]) {
   case 0:  zeroCount++; break;
   case 1:  oneCount++; break;
   default: twoCount++; break;
   }
   
   if (twoCount == 2)
    return 1 << 20;
   else if (oneCount == 2)
    h += 1 << 16;
   else {
    if (zeroCount == 1 && twoCount == 1)
     h += 1 << 12;
    else if ( zeroCount * oneCount == 1)
     h += 1 << 10;
    else if (zeroCount == 2)
     h += 1 << 9;
    else {
     h += 1 << 6;
    }
   }
  }
  return h;
 }
 
 private void playByComputer(){
  computeHeuristicScores();
  Arrays.sort(heuristicScoresAndPositions);
  int thePosition = heuristicScoresAndPositions[8] & 0xf;
  if (situation[thePosition] > 0){
   JOptionPane.showMessageDialog(null, "This game is ended in a draw.");
   restart();
   return;
  }
  situation[thePosition] = 2;
  ImageIcon OorXIcon = new ImageIcon("images/x.png");
  Image img = OorXIcon.getImage();
  Image newImg = img.getScaledInstance(90, 90,
    java.awt.Image.SCALE_SMOOTH);
  DefaultTableModel tableModel = (DefaultTableModel) table.getModel();
  tableModel.setValueAt(new ImageIcon(newImg), thePosition / 3, thePosition % 3);
  if (checkWhetherTheCurrentPlayerWins(thePosition, false)){
   JOptionPane.showMessageDialog(null, "Congratuations! Player X Wins.");
   restart();
   return;
  }
 }
 
 private boolean playByUser(MouseEvent e){
  int column = table.columnAtPoint(e.getPoint());
  int row = table.rowAtPoint(e.getPoint());
  if (table.getValueAt(row, column) != null)
   return false;
  int position = row * 3 + column;
  situation[position] = 1;
  ImageIcon OorXIcon = new ImageIcon("images/o.png");
  Image img = OorXIcon.getImage();
  Image newImg = img.getScaledInstance(90, 90,
    java.awt.Image.SCALE_SMOOTH);
  DefaultTableModel tableModel = (DefaultTableModel) table.getModel();
  tableModel.setValueAt(new ImageIcon(newImg), row, column);
  if (checkWhetherTheCurrentPlayerWins(position, true)){
   JOptionPane.showMessageDialog(null, "Congratuations! Player O Wins.");
   restart();
   return false;
  }
  return true;
 }
 
 public void restart(){
  for (int i = 0; i < 3; i++) {
   for (int j = 0; j < 3; j++)
    table.setValueAt(null, i, j);
  }
  situation = new int[9];
 }
}

ImageRenderer.java

package com.tictactoe;

import java.awt.Component;

import javax.swing.ImageIcon;
import javax.swing.JLabel;
import javax.swing.JTable;
import javax.swing.table.DefaultTableCellRenderer;

public class ImageRenderer extends DefaultTableCellRenderer {
 
 private static final long serialVersionUID = 1L;
 JLabel lbl = new JLabel();
 public Component getTableCellRendererComponent(JTable table,
   Object value, boolean isSelected, boolean hasFocus, int row,
   int column) {
  lbl.setIcon((ImageIcon) value);
  return lbl;
 }
}

TictacToe.java

package com.tictactoe;

import javax.swing.*;
import java.awt.*;
import javax.swing.border.EmptyBorder;
import javax.swing.border.EtchedBorder;
import javax.swing.table.DefaultTableModel;
import java.awt.event.ActionListener;
import java.awt.event.ActionEvent;

public class TicTacToe extends JFrame {

 private static final long serialVersionUID = 1L;
 private JPanel contentPane;
 private static JTable table;
 private ArtificialIntelligence ai;
 
 public static void main(String[] args) {
  EventQueue.invokeLater(new Runnable() {
   public void run() {
    try {
     TicTacToe frame = new TicTacToe();
     frame.setVisible(true);
    } catch (Exception e) {
     e.printStackTrace();
    }
   }
  });
 }

 private void setTable() {
  final Object[][] tableItems = new Object[][] { { null, null, null },
    { null, null, null }, { null, null, null }, };
  table = new JTable();
  table.setGridColor(new Color(255, 0, 0));

  ai = new ArtificialIntelligence(table);
  table.addMouseListener(ai);
  table.setModel(new DefaultTableModel(tableItems, new String[] { "0",
    "1", "2" }) {
   private static final long serialVersionUID = 1L;
   @Override
   public boolean isCellEditable(int row, int column) {
    return false;
   }
  });

  table.setBackground(new Color(153, 255, 255));
  table.setBorder(new EtchedBorder(EtchedBorder.RAISED, new Color(107,
    142, 35), null));
  table.setBounds(89, 70, 270, 270);
  for (int i = 0; i < 3; i++) {
   table.setRowHeight(i, 90);
   table.getColumnModel().getColumn(i)
     .setCellRenderer(new ImageRenderer());
  }
 }

 public TicTacToe() {
  setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  setBounds(100, 100, 450, 470);
  setTitle("Tic-Tac-Toe");
  setResizable(false);
  contentPane = new JPanel();
  contentPane.setBorder(new EmptyBorder(5, 5, 5, 5));
  contentPane.setLayout(null);
  setContentPane(contentPane);

  setTable();
  contentPane.add(table);

  JButton btnNewButton = new JButton("Restart");
  btnNewButton.addActionListener(new ActionListener() {
   public void actionPerformed(ActionEvent arg0) {
    ai.restart();
   }
  });
  btnNewButton.setFont(new Font("SansSerif", Font.BOLD, 16));
  btnNewButton.setBounds(180, 380, 90, 25);
  contentPane.add(btnNewButton);
 }
}