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
, andkey
in the Eclipse debugger instead ofmLeft
,mRight
, andmKey
. - The node names
p
andq
are left, and I explained why. - The node name is
parent
rather thanroot
in the methodinsert(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);
}
}