Given two binary trees, return true if they are structurally identical, and false otherwise.
Are AVL trees equal? - revision 2
In this revision:
equals()is documented. Two trees are equal if they are structurally identical.AvlTreehas a type parameterT 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
AvlTree.insert()(implicitly) using0 == T.compareTo(), wouldn't it be wiser to either use that inareTreesEqual(), or document thatT.compareTo()shall be consistent withT.equals()? \$\endgroup\$