Are AVL trees equal? - revision 3

Question

The original question

Given two binary trees, return true if they are structurally identical, and false otherwise.

Are AVL trees equal?

Are AVL trees equal? - revision 2

This revision on GitHub

In this revision:

• equals() is documented. Two trees are equal if they are structurally identical.
• AvlTree has a type parameter T extends Comparable<T>.
• Sizes of compared trees are used as a quick rejection. But I tested insertion of 10M items to two trees. There is no performance benefit in using size. The result is shown below.

AvlTree.

package com.bst;
import java.util.LinkedList;
import java.util.Queue;
public class AvlTree<T extends Comparable<T>> {
 Node<T> root;
 private int size;
 public AvlTree() {
 }
 public AvlTree(T... keys) {
 insert(keys);
 }
 private Node<T> insert(Node<T> parent, T key) {
 if (parent == null) {
 size++;
 return new Node<T>(key);
 }
 if (key.compareTo(parent.key) < 0) {
 parent.left = insert(parent.left, key);
 } else if (key.compareTo(parent.key) > 0) {
 parent.right = insert(parent.right, key);
 }
 return balance(parent);
 }
 public int getSize() {
 return size;
 }
 private Node<T> balance(Node<T> p) {
 fixHeight(p);
 if (bfactor(p) == 2) {
 if (bfactor(p.right) < 0) {
 p.right = rotateRight(p.right);
 }
 return rotateLeft(p);
 }
 if (bfactor(p) == -2) {
 if (bfactor(p.left) > 0) {
 p.left = rotateLeft(p.left);
 }
 return rotateRight(p);
 }
 return p;
 }
 private Node<T> rotateRight(Node<T> p) {
 Node<T> q = p.left;
 p.left = q.right;
 q.right = p;
 fixHeight(p);
 fixHeight(q);
 return q;
 }
 private Node<T> rotateLeft(Node<T> q) {
 Node<T> p = q.right;
 q.right = p.left;
 p.left = q;
 fixHeight(q);
 fixHeight(p);
 return p;
 }
 private int height(Node<T> p) {
 return p == null ? 0 : p.height;
 }
 private int bfactor(Node<T> p) {
 return height(p.right) - height(p.left);
 }
 private void fixHeight(Node<T> p) {
 int hl = height(p.left);
 int hr = height(p.right);
 p.height = (hl > hr ? hl : hr) + 1;
 }
 public void insert(T... keys) {
 if (keys == null) {
 return;
 }
 for (T key : keys) {
 if (key == null) {
 throw new NullPointerException("Can't insert null");
 }
 root = insert(root, key);
 }
 }
 @Override
 public boolean equals(Object arg0) {
 if (this == arg0) {
 return true;
 }
 if (!(arg0 instanceof AvlTree)) {
 return false;
 }
 AvlTree other = (AvlTree) arg0; 
 // size == other.size && 
 return areTreesEqual(this.root, other.root);
 }
 /**
 * 
 * @param root1 the root of the first tree
 * @param root2 the root of the second tree
 * @return true if the trees with the given roots are structurally identical, 
 * false otherwise
 */
 private boolean areTreesEqual(Node<T> root1, Node<T> root2) {
 if (root1 == root2) {
 return true;
 }
 if (root1 == null || root2 == null) {
 return false;
 }
 return root1.equals(root2) && areTreesEqual(root1.left, root2.left) && areTreesEqual(root1.right, root2.right);
 }
 @Override
 public int hashCode() {
 if (root == null) {
 return 0;
 }
 Queue<Node<T>> nodes = new LinkedList<Node<T>>();
 nodes.add(root);
 int res = 17;
 while (!nodes.isEmpty()) {
 Node<T> head = nodes.remove();
 res = 31 * res + head.hashCode();
 if (head.left != null) {
 nodes.add(head.left);
 }
 if (head.right != null) {
 nodes.add(head.right);
 }
 }
 return res;
 }
 @Override
 public String toString() {
 if (root == null) {
 return "[]";
 }
 StringBuilder builder = new StringBuilder("[");
 inOrderPrint(root, builder);
 builder.setLength(builder.length() - 2);
 builder.append("]");
 return builder.toString();
 }
 private void inOrderPrint(Node<T> root, StringBuilder builder) {
 if (root != null) {
 inOrderPrint(root.left, builder);
 builder.append(root + ", ");
 inOrderPrint(root.right, builder);
 }
 }
 static final class Node<T> {
 Node<T> left;
 Node<T> right;
 final T key;
 private int height;
 Node(T key) {
 this.key = key;
 this.height = 1;
 }
 @Override
 public int hashCode() {
 return key.hashCode();
 }
 @Override
 public boolean equals(Object obj) {
 if (obj == this) {
 return true;
 }
 if (!(obj instanceof Node)) {
 return false;
 }
 Node other = (Node) obj;
 return key.equals(other.key); 
 }
 @Override
 public String toString() {
 return key.toString();
 }
 }
}

AvlTreeTest (Unit tests)

package com.bst;
import org.junit.Assert;
import org.junit.Test;
import com.bst.AvlTree.Node;
public class AvlTreeTest {
 @Test
 public void testTwoEmptyTrees() {
 AvlTree<Integer> t1 = new AvlTree<Integer>();
 AvlTree<Integer> t2 = new AvlTree<Integer>();
 Assert.assertEquals(t1, t2);
 }
 @Test
 public void testLeftEmptyTree() {
 AvlTree<Integer> t1 = new AvlTree<Integer>();
 AvlTree<Integer> t2 = new AvlTree<Integer>(12);
 Assert.assertNotEquals(t1, t2);
 }
 @Test
 public void testRightEmptyTree() {
 AvlTree<Integer> t1 = new AvlTree<Integer>(12);
 AvlTree<Integer> t2 = new AvlTree<Integer>();
 Assert.assertNotEquals(t1, t2);
 }
 @Test
 public void testEqualsItself() {
 AvlTree<Integer> t1 = new AvlTree<Integer>();
 Assert.assertEquals(t1, t1);
 }
 @Test
 public void testNotEqualNotAvlInstance() {
 AvlTree<Integer> t1 = new AvlTree<Integer>();
 Object object = new Object();
 Assert.assertNotEquals(t1, object);
 }
 @Test
 public void testNotequalSizes() {
 final int min = 0;
 final int max = 100000;
 AvlTree<Integer> t1 = new AvlTree<Integer>();
 insertRange(t1, min, max);
 AvlTree<Integer> t2 = new AvlTree<Integer>();
 insertRange(t2, min, max + 1);
 Assert.assertNotEquals(t1, t2);
 }
 @Test
 public void testStructurallyNotIdentical() {
 final int min = 0;
 final int max = 100000;
 AvlTree<Integer> t1 = new AvlTree<Integer>();
 insertRange(t1, min, max);
 AvlTree<Integer> t2 = new AvlTree<Integer>();
 insertRange(t2, min + 1, max + 1);
 Assert.assertNotEquals(t1, t2);
 }
 @Test
 public void testStructurallIdentical() {
 final int min = 0;
 final int max = 100000;
 AvlTree<Integer> t1 = new AvlTree<Integer>();
 insertRange(t1, min, max);
 AvlTree<Integer> t2 = new AvlTree<Integer>();
 insertRange(t2, min, max);
 Assert.assertEquals(t1, t2);
 }
 @Test
 public void testLeftNodeMissing() {
 AvlTree<Integer> t1 = new AvlTree<Integer>(10, 4, 18, 2, 20);
 AvlTree<Integer> t2 = new AvlTree<Integer>(10, 4, 18, 6, 20);
 Assert.assertNotEquals(t1, t2);
 }
 @Test
 public void testRightNodeMissing() {
 AvlTree<Integer> t1 = new AvlTree<Integer>(10, 4);
 AvlTree<Integer> t2 = new AvlTree<Integer>(10, 4, 18);
 Assert.assertNotEquals(t1, t2);
 }
 @Test
 public void testLeftNodesNotEqual() {
 AvlTree<Integer> t1 = new AvlTree<Integer>(10, 3, 18);
 AvlTree<Integer> t2 = new AvlTree<Integer>(10, 4, 18);
 Assert.assertNotEquals(t1, t2);
 }
 @Test
 public void testRightNodesNotEqual() {
 AvlTree<Integer> t1 = new AvlTree<Integer>(10, 4, 16);
 AvlTree<Integer> t2 = new AvlTree<Integer>(10, 4, 18);
 Assert.assertNotEquals(t1, t2);
 }
 @Test
 public void testRootNodesNotEqual() {
 AvlTree<Integer> t1 = new AvlTree<Integer>(12, 3, 45);
 AvlTree<Integer> t2 = new AvlTree<Integer>(13, 3, 45);
 Assert.assertNotEquals(t1, t2);
 }
 @Test
 public void testEmptyTreeHashCode() {
 AvlTree<Integer> avlTree = new AvlTree<Integer>();
 Assert.assertEquals(0, avlTree.hashCode());
 }
 @Test
 public void testSingleZeroNodeTreeHashCode() {
 AvlTree<Integer> avlTree = new AvlTree<Integer>(0);
 Assert.assertNotEquals(0, avlTree.hashCode());
 }
 @Test
 public void testRootAndLeftNodesTreeHashCode() {
 Integer[] nodes = new Integer[] {12, 3};
 AvlTree<Integer> avlTree = new AvlTree<Integer>(nodes);
 int res = 17;
 res = 31 * res + nodes[0].hashCode();
 res = 31 * res + nodes[1].hashCode();
 Assert.assertEquals(res, avlTree.hashCode());
 }
 @Test
 public void testRootAndRightNodesTreeHashCode() {
 Integer[] nodes = new Integer[] {12, 30};
 AvlTree<Integer> avlTree = new AvlTree<Integer>(nodes);
 int res = 17;
 res = 31 * res + nodes[0].hashCode();
 res = 31 * res + nodes[1].hashCode();
 Assert.assertEquals(res, avlTree.hashCode());
 }
 private void insertRange(AvlTree<Integer> tree, int min, int max) {
 for (int i = min; i < max; i++) {
 tree.insert(i);
 }
 }
 @Test
 public void testEqualTreesEqualHashCodes() {
 AvlTree<Integer> avlTree1 = new AvlTree<Integer>(1, 2, 3);
 AvlTree<Integer> avlTree2 = new AvlTree<Integer>(1, 2, 3);
 Assert.assertEquals(avlTree1.hashCode(), avlTree2.hashCode());
 }
 @Test
 public void testSingleRotateLeft() {
 AvlTree<Integer> t1 = new AvlTree<Integer>(10);
 t1.insert(14, 56);
 Assert.assertEquals(t1.root.key, Integer.valueOf(14));
 Assert.assertEquals(t1.root.left.key, Integer.valueOf(10));
 Assert.assertEquals(t1.root.right.key, Integer.valueOf(56));
 }
 @Test
 public void testSingleRotateRight() {
 AvlTree<Integer> t1 = new AvlTree<Integer>(10);
 t1.insert(2, 1);
 Assert.assertEquals(t1.root.key, Integer.valueOf(2));
 Assert.assertEquals(t1.root.left.key, Integer.valueOf(1));
 Assert.assertEquals(t1.root.right.key, Integer.valueOf(10));
 }
 @Test
 public void testDoubleRotateLeftRight() {
 AvlTree<Integer> t1 = new AvlTree<Integer>(10);
 t1.insert(4, 9);
 Assert.assertEquals(t1.root.key, Integer.valueOf(9));
 Assert.assertEquals(t1.root.left.key, Integer.valueOf(4));
 Assert.assertEquals(t1.root.right.key, Integer.valueOf(10));
 }
 @Test
 public void testDoubleRotateRightLeft() {
 AvlTree<Integer> t1 = new AvlTree<Integer>(10);
 t1.insert(14, 12);
 Assert.assertEquals(t1.root.key, Integer.valueOf(12));
 Assert.assertEquals(t1.root.left.key, Integer.valueOf(10));
 Assert.assertEquals(t1.root.right.key, Integer.valueOf(14));
 }
 @Test
 public void testInsertDuplicate() {
 AvlTree<Integer> avlTree = new AvlTree<Integer>(12, 12);
 Assert.assertEquals(1, avlTree.getSize());
 }
 @Test
 public void testInitWithNull() {
 AvlTree<Integer> avlTree = new AvlTree<Integer>(null);
 Assert.assertNull(null, avlTree.root);
 }
 @Test(expected = NullPointerException.class)
 public void testInsertNull() {
 Integer[] nodes = {
 12, null
 };
 AvlTree<Integer> avlTree = new AvlTree<Integer>(nodes);
 }
 @Test
 public void testNodeEqual() {
 Node<Integer> node = new Node<Integer>(1);
 Node<Integer> node2 = node;
 Assert.assertEquals(node, node2);
 }
}

I insert items from 0 (inclusive) to 10,000,0000 (exclusive) to the two trees. And the execution time of the first fillTree() is four times as long as the execution time of the second fillTree(). I think the JVM just reuses some/all nodes I previously used. And equal() works very fast (0.221 sec.). For example, fillTree(start, count); and fillTree(start, count);

package com.client;
import com.bst.AvlTree;
public class Main {
 public static void main(String[] args) {
 // Client code goes here
 final int start = 0;
 final int count = 10000000; 
 AvlTree<Integer> avlTree1 = fillTree(start, count);
 AvlTree<Integer> avlTree2 = fillTree(count, 2 * count);
 long startTimeStamp = System.currentTimeMillis();
 System.out.println(avlTree1.equals(avlTree2));
 printDuration("equals: ", startTimeStamp, System.currentTimeMillis());
 }
 private static AvlTree<Integer> fillTree(int start, int count) {
 AvlTree<Integer> avlTree = new AvlTree<Integer>();
 long startTimeStamp = System.currentTimeMillis();
 for (int i = start; i < start + count; i++) {
 avlTree.insert(i);
 }
 printDuration("Insertion: ", startTimeStamp, System.currentTimeMillis());
 return avlTree;
 }
 private static void printDuration(String operation, long start, long end) {
 System.out.println(operation + (end - start) / 1000.0);
 }
}

Insertion: 11.758

10000000

Insertion: 3.802

equals: 0.221

If the second tree contains values that are not presented in the first tree, the second call of fillTree() will take twice as long as the first one. Maybe because heap is already filled with 10M items. For example, fillTree(start, count); and fillTree(count, 2 * count);

Insertion: 12.196

Insertion: 24.109

false

equals: 0.0

• greybeard: With AvlTree.insert() (implicitly) using 0 == T.compareTo(), wouldn't it be wiser to either use that in areTreesEqual(), or document that T.compareTo() shall be consistent with T.equals()?

Answer 1

 p.height = (hl > hr ? hl : hr) + 1;

For this sort of stuff you should use Math.max. It reads better. The JVM will handle inlining if it is needed.

I can't really find any other in-code improvements.