4
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ 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()? \$\endgroup\$
    – greybeard
    Dec 29 '15 at 5:38
2
\$\begingroup\$
    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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.