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);
 }
}

A Java Implementation of the K-means Clustering Algorithm for 3D points

In data mining, k-means clustering is a method of cluster analysis that aims to partition n points into k clusters where each point belongs to the cluster with the nearest mean. This results in a partitioning of the data space into Voronoi cells.

The following codes are my implementation of the K-means algorithm for 3D points. The Java project can be downloaded from https://sites.google.com/site/moderntone/K-Means.zip




Cluster.java

package kmeans;
import java.util.*;

public class Cluster {

 private final List<point> points;
 private Point centroid;
 
 public Cluster(Point firstPoint) {
  points = new ArrayList<point>();
  centroid = firstPoint;
 }
 
 public Point getCentroid(){
  return centroid;
 }
 
 public void updateCentroid(){
  double newx = 0d, newy = 0d, newz = 0d;
  for (Point point : points){
   newx += point.x; newy += point.y; newz += point.z;
  }
  centroid = new Point(newx / points.size(), newy / points.size(), newz / points.size());
 }
 
 public List<point> getPoints() {
  return points;
 }
 
 public String toString(){
  StringBuilder builder = new StringBuilder("This cluster contains the following points:\n");
  for (Point point : points)
   builder.append(point.toString() + ",\n");
  return builder.deleteCharAt(builder.length() - 2).toString(); 
 }
}

Clusters.java

package kmeans;

import java.util.*;

public class Clusters extends ArrayList<cluster> {

 private static final long serialVersionUID = 1L;
 private final List<point> allPoints;
 private boolean isChanged;
 
 public Clusters(List<point> allPoints){
  this.allPoints = allPoints;
 }
 
 /**@param point
  * @return the index of the Cluster nearest to the point
  */
 public Integer getNearestCluster(Point point){
  double minSquareOfDistance = Double.MAX_VALUE;
  int itsIndex = -1;
  for (int i = 0 ; i < size(); i++){
   double squareOfDistance = point.getSquareOfDistance(get(i).getCentroid());
   if (squareOfDistance < minSquareOfDistance){
    minSquareOfDistance = squareOfDistance;
    itsIndex = i;
   }
  }
  return itsIndex;
 }

 public boolean updateClusters(){
  for (Cluster cluster : this){
   cluster.updateCentroid();
   cluster.getPoints().clear();
  }
  isChanged = false;
  assignPointsToClusters();
  return isChanged;
 }
 
 public void assignPointsToClusters(){
  for (Point point : allPoints){
   int previousIndex = point.getIndex();
   int newIndex = getNearestCluster(point);
   if (previousIndex != newIndex)
    isChanged = true;
   Cluster target = get(newIndex);
   point.setIndex(newIndex);
   target.getPoints().add(point);
  }
 }
}

Point.java

package kmeans;

public class Point {
 
 private int index = -1; //denotes which Cluster it belongs to
 public double x, y, z;
 
 public Point(double x, double y, double z) {
  this.x = x;
  this.y = y;
  this.z = z;
 }
 
 public Double getSquareOfDistance(Point anotherPoint){
  return  (x - anotherPoint.x) * (x - anotherPoint.x)
    + (y - anotherPoint.y) *  (y - anotherPoint.y) 
    + (z - anotherPoint.z) *  (z - anotherPoint.z);
 }

 public int getIndex() {
  return index;
 }

 public void setIndex(int index) {
  this.index = index;
 }
 
 public String toString(){
  return "(" + x + "," + y + "," + z + ")";
 } 
}

KMeans.java

package kmeans;

import java.io.*;
import java.util.*;

public class KMeans {

 private static final Random random = new Random();
 public final List<point> allPoints;
 public final int k;
 private Clusters pointClusters; //the k Clusters

 /**@param pointsFile : the csv file for input points
  * @param k : number of clusters
  */
 public KMeans(String pointsFile, int k) {
  if (k < 2)
   new Exception("The value of k should be 2 or more.").printStackTrace();
  this.k = k;
  List<point> points = new ArrayList<point>();
  try {
   InputStreamReader read = new InputStreamReader(
     new FileInputStream(pointsFile), "UTF-8");
   BufferedReader reader = new BufferedReader(read);
   String line;
   while ((line = reader.readLine()) != null) 
    points.add(getPointByLine(line));
   reader.close();
   
  } catch (IOException e) {
   e.printStackTrace();
  }
  this.allPoints = Collections.unmodifiableList(points);
 }

 private Point getPointByLine(String line) {
  String[] xyz = line.split(",");
  return new Point(Double.parseDouble(xyz[0]),
    Double.parseDouble(xyz[1]), Double.parseDouble(xyz[2]));
 }

 /**step 1: get random seeds as initial centroids of the k clusters
  */
 private void getInitialKRandomSeeds(){
  pointClusters = new Clusters(allPoints);
  List<point> kRandomPoints = getKRandomPoints();
  for (int i = 0; i < k; i++){
   kRandomPoints.get(i).setIndex(i);
   pointClusters.add(new Cluster(kRandomPoints.get(i)));
  } 
 }
 
 private List<point> getKRandomPoints() {
  List<point> kRandomPoints = new ArrayList<point>();
  boolean[] alreadyChosen = new boolean[allPoints.size()];
  int size = allPoints.size();
  for (int i = 0; i < k; i++) {
   int index = -1, r = random.nextInt(size--) + 1;
   for (int j = 0; j < r; j++) {
    index++;
    while (alreadyChosen[index])
     index++;
   }
   kRandomPoints.add(allPoints.get(index));
   alreadyChosen[index] = true;
  }
  return kRandomPoints;
 }
 
 /**step 2: assign points to initial Clusters
  */
 private void getInitialClusters(){
  pointClusters.assignPointsToClusters();
 }
 
 /** step 3: update the k Clusters until no changes in their members occur
  */
 private void updateClustersUntilNoChange(){
  boolean isChanged = pointClusters.updateClusters();
  while (isChanged)
   isChanged = pointClusters.updateClusters();
 }
 
 /**do K-means clustering with this method
  */
 public List<cluster> getPointsClusters() {
  if (pointClusters == null) {
   getInitialKRandomSeeds();
   getInitialClusters();
   updateClustersUntilNoChange();
  }
  return pointClusters;
 }
 
 public static void main(String[] args) {
  String pointsFilePath = "files/randomPoints.csv";
  KMeans kMeans = new KMeans(pointsFilePath, 6);
  List<cluster> pointsClusters = kMeans.getPointsClusters();
  for (int i = 0 ; i < kMeans.k; i++)
   System.out.println("Cluster " + i + ": " + pointsClusters.get(i));
 }
}

An implementation of the R-Tree algorithm in Java

The following classes are my implementation of R-Tree, which can be used to construct an R-Tree for a list of points in a plane. The package along with a csv file storing points to be inserted can be downloaded from https://sites.google.com/site/moderntone/RTree.zip. The method to split an overflowing node is the Quadratic method by Antonin Guttman.

I have done a little testing but am still not very sure that the source codes below are entirely free of bugs. Any reader who finds bugs is welcomed to report them in comments below. And if I find some bugs afterwards, I will also modify this post.




MBR.java

package RTree;

import java.util.ArrayList;
import java.util.Collections;

public class MBR {
 
 protected double left, right, top, bottom;
 private Double area;
 
 private ArrayList children;  //an array of children MBRs
 
 //an array of leaf entries; only leaf MBRs have entries with nonzero size
 private ArrayList entries;
 
 private MBR parent;  //All leaf entries and node entries except the root have a parent MBR
 
 
 
 private static int idTrace = 0;
 private Integer id;
 
 private static final QuadraticComparator qc = new QuadraticComparator();
 
 private static Integer m, M;
 public static void initialize(int m, int M){
  if (M < 2 || m > M / 2)
   new Exception("Improper m and M values").printStackTrace();
  MBR.m = m; MBR.M = M;
 }
 
 public MBR(double left, double right, double top, double bottom) {
  this.left = left; this.right = right;
  this.top = top;  this.bottom = bottom;
  if (left > right || bottom > top)
   new Exception("Left shouldn't be larger than right, " +
     "and bottom shouldn't be larger than top").printStackTrace();
  children = new ArrayList(); entries = new ArrayList();
  setId();
 }
 
 
 /**
  * search the leaf MBR the leafEntry inserts to;
  * @param leafEntry
  */
 public MBRPair search(MBR leafEntry) {
  MBRPair targetMbrPair = null;
  if (children.size() == 0) //has no children but may have leaf entries
   targetMbrPair = new MBRPair(this, leafEntry);
  else {
   ArrayList mbrPairs = new ArrayList();
   for (MBR child : children)
    mbrPairs.add(new MBRPair(child, leafEntry));
   targetMbrPair = Collections.min(mbrPairs).getTarget().search(leafEntry);
  }
  return targetMbrPair;
 }
 
 /**
  * If the leaf node is not full, an entry is inserted. Else
 –Split the leaf node
 –Update the directory rectangles of the ancestor nodes if necessary
 * return null if no split occurs, or root MBR if it does
  */
 public MBR splitWhenFull(){
  
  MBR parentMbr = null;
  
  if (getLeafEntries().size() == M + 1){
   parentMbr = split_quardratic_forLeafEntries();
//   System.out.println("MBR 72");
//   parentMbr.printDetails();
  }
  else 
   return null;
  while (parentMbr.getChildren().size() == M + 1) {
   parentMbr = parentMbr.split_quardratic_forNoneLeafEntries();
  }
  
  return parentMbr.getRoot();
  
 }
 
 
 private void updateNodes(MBR newChild){
  MBRPair temp = new MBRPair(this, newChild);
  if (temp.getEnlargement() == 0) return;
  adjustRegion(temp.getMergedMBR());
 }
 
 /**
  * save calculation time a bit
  * @param newChild
  * @param pair
  */
 private void updateNodes(MBR newChild, MBRPair pair){
  MBRPair temp;
  if (pair.getEnlargement() == 0) return;
  adjustRegion(pair.getMergedMBR());
  
  MBR ancestor = parent;
  while (ancestor != null){
   temp = new MBRPair(ancestor, newChild);
   if (temp.getEnlargement() == 0) return;
   ancestor.adjustRegion(temp.getMergedMBR());
   ancestor = ancestor.getParent();
  }
 }
 
 
 
 
 public void addNonLeafChild(MBR nonLeafChild){
  nonLeafChild.setParent(this);
  children.add(nonLeafChild);
  updateNodes(nonLeafChild);
 }
 
 /**
  * reduce calculation time a bit compared to addNonLeafChild(MBR nonLeafChild)
  */
 public void addNonLeafChild(MBR nonLeafChild, MBRPair pair){
  nonLeafChild.setParent(this);
  children.add(nonLeafChild);
  updateNodes(nonLeafChild, pair);
 }
 
 public void addLeafChild(MBR leafChild){
  leafChild.setParent(this);
  entries.add(leafChild);
  updateNodes(leafChild);
 }
 
 /**
  * reduce calculation time a bit compared to addLeafChild(MBR leafChild)
  */
 public void addLeafChild(MBR leafChild, MBRPair pair){
  leafChild.setParent(this);
  entries.add(leafChild);
  updateNodes(leafChild, pair);
 }
 
 
 public MBR split_quardratic_forLeafEntries(){
  MBR group1 = this;
  ArrayList group1sLeafEntries = group1.getLeafEntries();
  ArrayList allPairs = new ArrayList();
  for (int j = 1; j < group1sLeafEntries.size(); j ++){
   for (int i = 0 ; i < j; i++)
    allPairs.add(new MBRPair(group1sLeafEntries.get(i), group1sLeafEntries.get(j)));
  }
  
  MBRPair theBestPair = Collections.max(allPairs, qc);
  MBR group1_firstLeafEntry = theBestPair.getTarget();
  MBR group2_firstLeafEntry = theBestPair.getToBeInserted();
  
  ArrayList leafEntries_bak = new ArrayList();
  leafEntries_bak.addAll(group1sLeafEntries);
  leafEntries_bak.remove(group1_firstLeafEntry);
  leafEntries_bak.remove(group2_firstLeafEntry);


  group1sLeafEntries.clear();
  group1.adjustRegion(group1_firstLeafEntry);
  group1.addLeafChild(group1_firstLeafEntry);
  
  
  if (parent == null){ //happens when splitting the root; the parent becomes the new root
   parent = new MBR(left, right, top, bottom);
   parent.addNonLeafChild(group1);
   
  }
  
  MBR group2 = new MBR(group2_firstLeafEntry.left, group2_firstLeafEntry.right, group2_firstLeafEntry.top, group2_firstLeafEntry.bottom);
  parent.addNonLeafChild(group2);
  group2.addLeafChild(group2_firstLeafEntry);
  
  for (MBR child : leafEntries_bak){
   MBRPair pair1 = new MBRPair(group1, child);
   MBRPair pair2 = new MBRPair(group2, child);
   
   if (group1.getLeafEntries().size() == M - m + 1){
    group2.addLeafChild(child, pair2);
    continue;
   }else if (group2.getLeafEntries().size() == M - m + 1){
    group1.addLeafChild(child, pair1);
    continue;
   }
   
   if (pair1.getEnlargement() < pair2.getEnlargement()){
    group1.addLeafChild(child, pair1);
   }else if (pair2.getEnlargement() < pair1.getEnlargement() ){
    group2.addLeafChild(child, pair2);
   }else {
    if (group1.getArea() < group2.getArea()){
     group1.addLeafChild(child, pair1);
    }else if (group2.getArea() < group1.getArea()){
     group2.addLeafChild(child, pair2);
    }
    else {
     if (group1.getChildren().size() <= group2.getChildren().size())
      group1.addLeafChild(child, pair1);
     else
      group2.addLeafChild(child, pair2);
    }
   }
   
  }
  
//  System.out.println("MBR 216 : two groups " + group1.getLeafEntries().size() + ", " + group2.getLeafEntries().size());
//  System.out.println("MBR 217 " + group1.left + ", " + group1.right + ", " + group1.top + ", " + group1.bottom);
//  System.out.println("MBR 218 " + group2.left + ", " + group2.right + ", " + group2.top + ", " + group2.bottom);
  return parent;
  
 }
 
 public MBR split_quardratic_forNoneLeafEntries(){
  //this: group1; this.getChildren(): group1sChildren
  MBR group1 = this;
  ArrayList group1sChildren = group1.getChildren();
  ArrayList allPairs = new ArrayList();
  for (int j = 1; j < group1sChildren.size(); j ++){
   for (int i = 0 ; i < j; i++)
    allPairs.add(new MBRPair(group1sChildren.get(i), group1sChildren.get(j)));
  }
  
  MBRPair theBestPair = Collections.max(allPairs, qc);
  MBR group1_firstMBR = theBestPair.getTarget();
  MBR group2_firstMBR = theBestPair.getToBeInserted();
  
  ArrayList children_bak = new ArrayList();
  children_bak.addAll(group1sChildren);
  children_bak.remove(group1_firstMBR); 
  children_bak.remove(group2_firstMBR);
  group1sChildren.clear();
  group1.adjustRegion(group1_firstMBR);
  group1.addNonLeafChild(group1_firstMBR);
  
  if (parent == null){ //parent becomes new root
   parent = new MBR(left, right, top, bottom);
   parent.addNonLeafChild(group1);
  }
  
  MBR group2 = new MBR(group2_firstMBR.left, group2_firstMBR.right, group2_firstMBR.top, group2_firstMBR.bottom);
  parent.addNonLeafChild(group2);
  group2.addNonLeafChild(group2_firstMBR);
  
  for (MBR child : children_bak){
   MBRPair pair1 = new MBRPair(group1, child);
   MBRPair pair2 = new MBRPair(group2, child);
   
   if (group1.getChildren().size() == M - m + 1){
    group2.addNonLeafChild(child, pair2);
    continue;
   }else if (group2.getChildren().size() == M - m + 1){
    group1.addNonLeafChild(child, pair1);
    continue;
   }
   
   if (pair1.getEnlargement() < pair2.getEnlargement()){
    group1.addNonLeafChild(child, pair1);
   }else if (pair2.getEnlargement() < pair1.getEnlargement() ){
    group2.addNonLeafChild(child, pair2);
   }else {
    if (group1.getArea() < group2.getArea()){
     group1.addNonLeafChild(child, pair1);
    }else if (group2.getArea() < group1.getArea()){
     group2.addNonLeafChild(child, pair2);
    }
    else {
     if (group1.getChildren().size() <= group2.getChildren().size())
      group1.addNonLeafChild(child, pair1);
     else
      group2.addNonLeafChild(child, pair2);
    }
   }
   
  }
  
  return parent;
 }
 
 
 

 /**
  * adjust regon and leave other info unchanged
  * @param newRegionMBR
  */
 private void adjustRegion(MBR newRegionMBR){
  this.left = newRegionMBR.left; this.right = newRegionMBR.right;
  this.top = newRegionMBR.top; this.bottom = newRegionMBR.bottom;
 }
 
 public Double getArea(){
  if (area == null)
   area = (right - left) * (top - bottom);
  return area;
 }
 

 public MBR getParent() {
  return parent;
 }

 public void setParent(MBR parent) {
  this.parent = parent;
 }

 public ArrayList getChildren() {
  return children;
 }
 


 public Integer getId() {
  return id;
 }
 public void setId() {
  if (id == null)
   id = ++idTrace; 
 }

 public ArrayList getLeafEntries() {
  return entries;
 }
 
 public MBR getRoot(){
  if (parent == null)
   return this;
  MBR root = parent;
  while (root.getParent() != null)
   root = root.getParent();
  return root;
 }

 public void printDetails(){
  System.out.println("MBR.printDetails(): for MBR with id = " + id);
  System.out.println("left = " + left + ", right = " + right 
    + ", top = " + top + ", bottom = " + bottom);
  System.out.println("children.size() = " + children.size() + ", leafEntries.size() = " + entries.size());
  for (int i = 0; i < children.size(); i++){
   System.out.println("child " + i + "left = " + children.get(i).left + ", right = " + children.get(i).right 
     + ", top = " + children.get(i).top + ", bottom = " + children.get(i).bottom);
  }
  if (parent != null){
   System.out.println("parent.left = " + parent.left + ", parent.right = " + parent.right 
     + ", parent.top = " + parent.top + ", parent.bottom = " + parent.bottom);
  }
 } 
}

MBRPair.java

package RTree;

public class MBRPair implements Comparable{

 /**
  * An MBRPair represent a pair of MBR;
  * Used to facilitate the determination of the most proper leaf MBR an entry should be inserted to
  * or the most proper non-leaf MBR an MBR should be inserted to 
  */
 private Double enlargement;
 private final MBR target, toBeInserted;
 private MBR mergedMBR; //merge target and toBeInserted into one by adjusting left, right, top, bottom
 
 public MBRPair(MBR target, MBR toBeInserted){
  this.target = target; 
  this.toBeInserted = toBeInserted;
 }
 
 /**
  * �VIf there is a node whose directory rectangle contains the mbbto be inserted, then search the subtree
�VElse choose a node such that the enlargement of its directory rectangle is minimal, then search the subtree
�VIf more than one node satisfy this, choose the one with smallest area
  */
 @Override
 public int compareTo(MBRPair anotherPair) {
  int firstComparison = getEnlargement().compareTo(anotherPair.getEnlargement());
  if (firstComparison != 0)
   return firstComparison;
  return target.getArea().compareTo(anotherPair.getTarget().getArea());
 }
 
 public Double getEnlargement() {
  if (enlargement == null){
   double leftMost, rightMost, topMost, bottomMost;
   leftMost = min(target.left, toBeInserted.left);
   rightMost = max(target.right, toBeInserted.right);
   topMost = max(target.top, toBeInserted.top);
   bottomMost = min(target.bottom, toBeInserted.bottom);
   mergedMBR = new MBR(leftMost, rightMost, topMost, bottomMost);
   enlargement = mergedMBR.getArea() - target.getArea();
  }
  return enlargement;
 }
 
 
 private double max(double a, double b){
  return a > b ? a : b;
 }
 private double min(double a, double b){
  return a < b ? a : b;
 }
 
 public MBR getTarget() {
  return target;
 }
 
 public MBR getToBeInserted() {
  return toBeInserted;
 }

 public MBR getMergedMBR() {
  if (mergedMBR == null)
   getEnlargement();
  return mergedMBR;
 }
}

QuadraticComparator.java

package RTree;

import java.util.Comparator;

public class QuadraticComparator implements Comparator{
 
 @Override
 public int compare(MBRPair pair1, MBRPair pair2) {
  Double additionalArea1 = computeAdditionalArea(pair1);
  Double additionalArea2 = computeAdditionalArea(pair2);
  return additionalArea1.compareTo(additionalArea2);
 }
 
 private double computeAdditionalArea(MBRPair pair){
  return pair.getMergedMBR().getArea() - pair.getTarget().getArea() - pair.getToBeInserted().getArea();
 }
}

RTree.java

package RTree;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;


public class RTree {

 public RTree() {
  
 }
 MBR root = null;
 
 public static void main(String[] args) {
  MBR.initialize(3, 7);
  RTree rTree = new RTree();
  String pointsFilePath = "files/randomPoints.csv";
  MBR root = rTree.constructRTree(pointsFilePath);
  root.printDetails();
 }
 
 
 public MBR constructRTree(String pointsFilePath){
  
  ArrayList leafMBRsToBeInserted = readLeafMBRs(pointsFilePath);
  if (leafMBRsToBeInserted.size() == 0)
   return root = null;
  else{
   MBR firstLeafMBR = leafMBRsToBeInserted.get(0);
   root = new MBR(firstLeafMBR.left, firstLeafMBR.right, firstLeafMBR.top, firstLeafMBR.bottom);
   root.addLeafChild(firstLeafMBR);
  }
  for (int i = 1 ; i < leafMBRsToBeInserted.size(); i++){
   MBRPair pair = root.search(leafMBRsToBeInserted.get(i));
   MBR targetMbr = pair.getTarget();
   targetMbr.addLeafChild(leafMBRsToBeInserted.get(i), pair);
   
   MBR newRoot = targetMbr.splitWhenFull();
   if (newRoot != null)
    root = newRoot;
   
  }
  
  return root;
 }
 
 
 
 /**
  * Read leaf MBRs to be inserted to the RTree from file.
  * The leaf MBrs of the RTree are zero-area points. 
  */
 private ArrayList readLeafMBRs(String pointsFilePath){
  ArrayList points = new ArrayList();
  try {
   InputStreamReader read = new InputStreamReader(new FileInputStream(pointsFilePath), "utf-8");
   BufferedReader reader = new BufferedReader(read);
   String line;
   while ((line = reader.readLine()) != null) {
    
    int comma = line.indexOf(",");
    double x = Double.parseDouble(line.substring(0, comma));
    double y = Double.parseDouble(line.substring(comma + 1));
    points.add(new MBR(x, x, y, y));
   } reader.close();
  } catch (Exception e) {
   e.printStackTrace();
  }
  return points;
 }

}