Are AVL trees equal? - revision 2

Question

Revision 1.

This revision on GitHub

In addition to the solution itself, I wrote tests for all the possible cases.

It seems you have verified all execution paths are covered.

You are right. I only covered all execution paths in the class AvlTree

In this revision:

• No Android code style. In fact, it's much easier to deal with left, right, and key in the Eclipse debugger instead of mLeft, mRight, and mKey.
• The node names p and q are left, and I explained why.
• The node name is parent rather than root in the method insert(Node parent, int key).
• Duplicates are not allowed. I'd handle duplicates this way if I needed to. Let me insert the quote I mean:

An option to avoid this issue is to not represent duplicates structurally (as separate nodes) but instead use a counter that counts the number of occurrences of the key. The previous example would then have a tree like:

      3(1)
    /     \
  2(1)     4(1)

• An iterative version of insert is added. I expected the iterative approach would perform much faster than the recursive one. But when I inserted 50M nodes and then tried inserting a duplicate key 100,000 times, the execution times of the recursive and iterative methods were almost the same. time = 37.703. timeIter = 33.909
• Since I didn't find a tool for Eclipse which would build a DUG graph, I didn't do data flow testing.

Here I'd like you to take a look at balance(Node inserted, Deque<Node> stack). It doesn't look perfect, but I struggled with it enough. Now I'd like to post this far-from-perfect version and receive your feedback.

AvlTree

package com.bst;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class AvlTree {

    Node root;

    public AvlTree() {

    }

    public AvlTree(int... keys) {
        if (keys != null) {
            insert(keys);
        }
    }

    public void insertIteratively(int... keys) {
        if (keys != null) {
            for (int key : keys) {
                insertIteratively(root, key);
            }
        }
    }

    private Node insert(Node parent, int key) {
        if (parent == null) {
            return new Node(key);
        }
        if (key < parent.key) {
            parent.left = insert(parent.left, key);
        } else if (key > parent.key) {
            parent.right = insert(parent.right, key);
        }
        return balance(parent);
    }

    private void insertIteratively(Node parent, int key) {      
        if (parent == null) {
            root = new Node(key);
            return;
        }
        Deque<Node> stack = new ArrayDeque<Node>();
        Node current = parent;
        while (current != null) {
            parent = current;
            stack.push(current);
            if (key == current.key) {
                return;
            }
            current = key < current.key ? current.left : current.right;
        }
        Node inserted = new Node(key);
        if (key < parent.key) {
            parent.left = inserted;
        } else {
            parent.right = inserted;
        }
        balance(inserted, stack);
    }

    private void balance(Node inserted, Deque<Node> stack) {
        Node newLocalRoot = inserted;
        while (!stack.isEmpty()) {
            Node current = stack.pop();
            if (newLocalRoot.key < current.key) {
                current.left = newLocalRoot;
            } else {
                current.right = newLocalRoot;
            }
            newLocalRoot = balance(current); 
        }
        root = newLocalRoot;
    }

    private Node balance(Node 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 rotateRight(Node p) {
        Node q = p.left;
        p.left = q.right;
        q.right = p;
        fixHeight(p);
        fixHeight(q);
        return q;
    }

    private Node rotateLeft(Node q) {
        Node p = q.right;
        q.right = p.left;
        p.left = q;
        fixHeight(q);
        fixHeight(p);
        return p;
    }

    private int height(Node p) {
        return p == null ? 0 : p.height;
    }

    private int bfactor(Node p) {
        return height(p.right) - height(p.left);
    }

    private void fixHeight(Node p) {
        int hl = height(p.left);
        int hr = height(p.right);
        p.height = (hl > hr ? hl : hr) + 1;
    }

    public void insert(int... keys) {
        for (int key : keys) {
            root = insert(root, key);
        }
    }

    public void insert(int key) {
        root = insert(root, key);
    }

    public void insertIteratively(int key) {
        insertIteratively(root, key);
    }

    @Override
    public boolean equals(Object arg0) {
        if (this == arg0) {
            return true;
        }
        if (!(arg0 instanceof AvlTree)) {
            return false;
        }
        AvlTree other = (AvlTree) arg0;
        return areTreesEqual(this.root, other.root);
    }

    private boolean areTreesEqual(Node root1, Node root2) {
        if (root1 == root2) {
            return true;
        }
        if (root1 == null || root2 == null) {
            return false;
        }
        return root1.key == root2.key && areTreesEqual(root1.left, root2.left) && areTreesEqual(root1.right, root2.right);
    }

    @Override
    public int hashCode() {
        if (root == null) {
            return 0;
        }
        Queue<Node> nodes = new LinkedList<AvlTree.Node>();
        nodes.add(root);
        int res = 17;
        while (!nodes.isEmpty()) {
            Node 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 root, StringBuilder builder) {
        if (root != null) {
            inOrderPrint(root.left, builder);
            builder.append(root + ", ");
            inOrderPrint(root.right, builder);
        }
    }

    static class Node {

        Node left;
        Node right;
        final int key;
        private int height;

        private Node(int key) {
            this.key = key;
            this.height = 1;
        }

        @Override
        public int hashCode() {
            int res = 17;
            res = 17 * res + key;
            return res;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == this) {
                return true;
            }
            if (!(obj instanceof Node)) {
                return false;
            }
            Node other = (Node) obj;
            return key == other.key;
        }

        @Override
        public String toString() {
            return Integer.toString(key);
        }
    }

}

AvlTreeTest

package com.bst;

import org.junit.Assert;
import org.junit.Test;

public class AvlTreeTest {

    @Test
    public void testDefaultConstructor() {
        AvlTree t1 = new AvlTree();
        Assert.assertNull(t1.root);
    }

    @Test
    public void testIntegerConstructor() {
        AvlTree t1 = new AvlTree(1);
        Assert.assertNotNull(t1.root);
    }

    @Test
    public void testInsertToEmptyTree() {
        AvlTree t1 = new AvlTree();
        t1.insert(1);
        Assert.assertEquals(1, t1.root.key);
    }

    @Test
    public void testEqualsItself() {
        AvlTree t1 = new AvlTree();
        Assert.assertEquals(t1, t1);
    }

    @Test
    public void testNotEqualNotAvlInstance() {
        AvlTree t1 = new AvlTree();
        Object object = new Object();
        Assert.assertNotEquals(t1, object);
    }

    @Test
    public void testEmptyEqual() {
        AvlTree t1 = new AvlTree();
        AvlTree t2 = new AvlTree();
        Assert.assertEquals(t1, t2);
    }

    @Test
    public void testFirstEmpty() {
        AvlTree t1 = new AvlTree();
        AvlTree t2 = new AvlTree(1);
        Assert.assertNotEquals(t1, t2);
    }

    @Test
    public void testSecondEmpty() {
        AvlTree t1 = new AvlTree(1);
        AvlTree t2 = new AvlTree();
        Assert.assertNotEquals(t1, t2);
    }

    @Test
    public void testRootsEqual() {
        AvlTree t1 = new AvlTree(1);
        AvlTree t2 = new AvlTree(1);
        Assert.assertEquals(t1, t2);
    }

    @Test
    public void testRootAndLeftEqual() {
        AvlTree t1 = new AvlTree(10);
        t1.insert(2);
        AvlTree t2 = new AvlTree(10);
        t2.insert(2);
        Assert.assertEquals(t1, t2);
    }

    @Test
    public void testRootAndRightEqual() {
        AvlTree t1 = new AvlTree(1);
        t1.insert(2);
        AvlTree t2 = new AvlTree(1);
        t2.insert(2);
        Assert.assertEquals(t1, t2);
    }

    @Test
    public void testRootsEqual_LeftsNotEqual() {
        AvlTree t1 = new AvlTree(10);
        t1.insert(2);
        AvlTree t2 = new AvlTree(10);
        t2.insert(1);
        Assert.assertNotEquals(t1, t2);
    }

    @Test
    public void testRootsEqual_RightsNotEqual() {
        AvlTree t1 = new AvlTree(1);
        t1.insert(2);
        AvlTree t2 = new AvlTree(1);
        t2.insert(4);
        Assert.assertNotEquals(t1, t2);
    }

    @Test
    public void testEmptyTreeHashCode() {
        AvlTree t1 = new AvlTree();
        Assert.assertEquals(0, t1.hashCode());
    }

    @Test
    public void testEqualTreesEqualHashCodes() {
        AvlTree t1 = new AvlTree(10);
        t1.insert(2, 12);
        AvlTree t2 = new AvlTree(10);
        t2.insert(2, 12);
        Assert.assertEquals(t1.hashCode(), t2.hashCode());
    }

    @Test
    public void testToStringEmpty() {
        AvlTree t1 = new AvlTree();
        Assert.assertEquals("[]", t1.toString());
    }

    @Test
    public void testToStringSingleNode() {
        AvlTree t1 = new AvlTree(1);
        Assert.assertEquals("[1]", t1.toString());
    }

    @Test
    public void testToStringManyNodes() {
        AvlTree t1 = new AvlTree(1);
        t1.insert(12, 56, 7, 2, 1);
        Assert.assertEquals("[1, 2, 7, 12, 56]", t1.toString());
    }

    @Test
    public void testSingleRotateLeft() {
        AvlTree t1 = new AvlTree(10);
        t1.insert(14, 56);
        Assert.assertEquals(t1.root.key, 14);
        Assert.assertEquals(t1.root.left.key, 10);
        Assert.assertEquals(t1.root.right.key, 56);
    }

    @Test
    public void testSingleRotateRight() {
        AvlTree t1 = new AvlTree(10);
        t1.insert(2, 1);
        Assert.assertEquals(t1.root.key, 2);
        Assert.assertEquals(t1.root.left.key, 1);
        Assert.assertEquals(t1.root.right.key, 10);
    }

    @Test
    public void testDoubleRotateLeftRight() {
        AvlTree t1 = new AvlTree(10);
        t1.insert(4, 9);
        Assert.assertEquals(t1.root.key, 9);
        Assert.assertEquals(t1.root.left.key, 4);
        Assert.assertEquals(t1.root.right.key, 10);
    }

    @Test
    public void testDoubleRotateRightLeft() {
        AvlTree t1 = new AvlTree(10);
        t1.insert(14, 12);
        Assert.assertEquals(t1.root.key, 12);
        Assert.assertEquals(t1.root.left.key, 10);
        Assert.assertEquals(t1.root.right.key, 14);
    }
}

The client code with 50M inserted nodes and 100000 attempts to insert the duplicate.

Main

package com.client;

import com.bst.AvlTree;

public class Main {

    public static void main(String[] args) {
        // Here you can create an AVL tree. This is client code
        final int nodeCount = 50000000;
        final int duplicateKey = nodeCount - 1;

        startInsert(nodeCount, duplicateKey);
        startInsertIter(nodeCount, duplicateKey);
    }

    private static void startInsert(int nodeCount, int duplicateKey) {
        long start = System.currentTimeMillis();
        AvlTree avlTree = new AvlTree();

        for (int i = 0; i < nodeCount; i++) {
            avlTree.insert(i);
        }

        for (int i = 0; i < 100000; i++) {
            avlTree.insert(duplicateKey);
        }

        double time = (System.currentTimeMillis() - start) / 1000.0;
        System.out.println("time = " + time);
    }

    private static void startInsertIter(int nodeCount, int duplicateKey) {
        long startIter = System.currentTimeMillis();
        AvlTree avlTreeIter = new AvlTree();

        for (int i = 0; i < nodeCount; i++) {
            avlTreeIter.insertIteratively(i);
        }

        for (int i = 0; i < 100000; i++) {
            avlTreeIter.insertIteratively(duplicateKey);
        }

        double timeIter = (System.currentTimeMillis() - startIter) / 1000.0;
        System.out.println("timeIter = " + timeIter);
    }
}

Answer 1

1. Some of my comments from an answer to a previous question can be carried over directly.

2. I note that since that previous question you've removed childCount. That's a bit of a shame here, because "Is the size the same?" is a good quick-reject question for equality of collections.

3. I'm not actually sure whether the implementation of equals is correct or not, because you haven't documented what you consider equality to mean.

   If the intention is that two trees are equal only if they are structurally identical, then you should document that very clearly because it violates the general contract of collections (and although you're not implementing Collection<Integer>, as a user of your class I would assume that your intention was to provide a similar API).

   If your intention is that two trees are equal if they contain the same elements then I strongly suspect that the code is buggy. It seems quite implausible that every possible ordering of insertions would result in an identical structure.