Skip to content

Instantly share code, notes, and snippets.

@manoelf

manoelf/AVLTeste1

Created September 10, 2016 15:48
Show Gist options
  • Save manoelf/3a1cf82ca09255fd0f67aa0b6a563f4f to your computer and use it in GitHub Desktop.
Save manoelf/3a1cf82ca09255fd0f67aa0b6a563f4f to your computer and use it in GitHub Desktop.
Download ZIP
Raw
AVLTeste1
package adt.avltree;
import static org.junit.Assert.*;
import java.util.Arrays;
import org.junit.Before;
import org.junit.Test;
import adt.bst.BSTNode;
public class AVLTeste1 {
AVLTreeImpl<Integer> myAVL;
@Before
public void initialize() {
myAVL = new AVLTreeImpl<Integer>();
}
@Test
public void testGetRoot0() {
assertNull(myAVL.getRoot().getData());
}
@Test
public void testGetRoot1() {
myAVL.insert(20);
assertEquals(new Integer(20), myAVL.getRoot().getData());
}
@Test
public void testIsEmpty0() {
assertTrue(myAVL.isEmpty());
}
@Test
public void testIsEmpty1() {
myAVL.insert(20);
assertFalse(myAVL.isEmpty());
}
@Test
public void testHeight0() {
assertEquals(-1, myAVL.height());
}
@Test
public void testHeight1() {
myAVL.insert(20);
assertEquals(0, myAVL.height());
}
@Test
public void testHeight2() {
myAVL.insert(15);
assertEquals(0, myAVL.height());
myAVL.insert(6);
assertEquals(1, myAVL.height());
myAVL.insert(3);
assertEquals(1, myAVL.height());
myAVL.insert(2);
assertEquals(2, myAVL.height());
myAVL.insert(4);
assertEquals(2, myAVL.height());
myAVL.insert(7);
assertEquals(2, myAVL.height());
myAVL.insert(13);
assertEquals(2, myAVL.height());
myAVL.insert(9);
assertEquals(3, myAVL.height());
myAVL.insert(18);
assertEquals(3, myAVL.height());
myAVL.insert(17);
assertEquals(3, myAVL.height());
myAVL.insert(20);
assertEquals(3, myAVL.height());
}
@Test
public void testSearch0() {
myAVL.insert(9);
assertEquals(new Integer(9), myAVL.search(9).getData());
}
@Test
public void testSearch1() {
myAVL.insert(9);
myAVL.insert(5);
myAVL.insert(10);
assertEquals(new Integer(5), myAVL.search(5).getData());
assertEquals(new Integer(10), myAVL.search(10).getData());
}
@Test
public void testSearch2() {
myAVL.insert(9);
myAVL.insert(5);
myAVL.insert(10);
myAVL.insert(2);
assertEquals(new Integer(2), myAVL.search(5).getLeft().getData());
assertEquals(new Integer(5), myAVL.search(2).getParent().getData());
assertEquals(new Integer(10), myAVL.search(9).getRight().getData());
}
@Test
public void testSearch3() {
myAVL.insert(9);
myAVL.insert(5);
myAVL.insert(10);
myAVL.insert(2);
assertEquals(new BSTNode<Integer>(), myAVL.search(1));
}
@Test
public void testInsert0() {
myAVL.insert(15);
assertEquals(0, myAVL.height());
assertEquals(new Integer(15), myAVL.getRoot().getData());
}
@Test
public void testInsert1() {
Integer[] preOrder = { 15, 6 };
Integer[] order = { 6, 15 };
Integer[] postOrder = { 6, 15 };
myAVL.insert(15);
myAVL.insert(6);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testInsert2() {
Integer[] preOrder = { 6, 3, 15 };
Integer[] order = { 3, 6, 15 };
Integer[] postOrder = { 3, 15, 6 };
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testInsert3() {
Integer[] preOrder = { 18, 15, 20 };
Integer[] order = { 15, 18, 20 };
Integer[] postOrder = { 15, 20, 18 };
myAVL.insert(15);
myAVL.insert(18);
myAVL.insert(20);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testInsert4() {
Integer[] preOrder = { 6, 3, 2, 4, 15 };
Integer[] order = { 2, 3, 4, 6, 15 };
Integer[] postOrder = { 2, 4, 3, 15, 6 };
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
myAVL.insert(2);
myAVL.insert(4);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testInsert5() {
Integer[] preOrder = { 6, 3, 2, 4, 15, 7 };
Integer[] order = { 2, 3, 4, 6, 7, 15 };
Integer[] postOrder = { 2, 4, 3, 7, 15, 6 };
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
myAVL.insert(2);
myAVL.insert(4);
myAVL.insert(7);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testInsert6() {
Integer[] preOrder = { 6, 3, 2, 4, 13, 7, 15 };
Integer[] order = { 2, 3, 4, 6, 7, 13, 15 };
Integer[] postOrder = { 2, 4, 3, 7, 15, 13, 6 };
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
myAVL.insert(2);
myAVL.insert(4);
myAVL.insert(7);
myAVL.insert(13);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testInsert7() {
Integer[] preOrder = { 6, 3, 2, 4, 13, 7, 9, 15, 18 };
Integer[] order = { 2, 3, 4, 6, 7, 9, 13, 15, 18 };
Integer[] postOrder = { 2, 4, 3, 9, 7, 18, 15, 13, 6 };
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
myAVL.insert(2);
myAVL.insert(4);
myAVL.insert(7);
myAVL.insert(13);
myAVL.insert(9);
myAVL.insert(18);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testInsert8() {
Integer[] preOrder = { 6, 3, 2, 4, 13, 7, 9, 17, 15, 18 };
Integer[] order = { 2, 3, 4, 6, 7, 9, 13, 15, 17, 18 };
Integer[] postOrder = { 2, 4, 3, 9, 7, 15, 18, 17, 13, 6 };
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
myAVL.insert(2);
myAVL.insert(4);
myAVL.insert(7);
myAVL.insert(13);
myAVL.insert(9);
myAVL.insert(18);
myAVL.insert(17);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testInsert9() {
Integer[] preOrder = { 13, 6, 3, 2, 4, 7, 9, 17, 15, 18, 20 };
Integer[] order = { 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 };
Integer[] postOrder = { 2, 4, 3, 9, 7, 6, 15, 20, 18, 17, 13 };
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
myAVL.insert(2);
myAVL.insert(4);
myAVL.insert(7);
myAVL.insert(13);
myAVL.insert(9);
myAVL.insert(18);
myAVL.insert(17);
myAVL.insert(20);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testRemove0() {
Integer[] array = {};
myAVL.remove(2);
assertArrayEquals(array, myAVL.order());
}
@Test
public void testRemove1() {
Integer[] preOrder = { 13, 6, 3, 2, 4, 7, 17, 15, 18, 20 };
Integer[] order = { 2, 3, 4, 6, 7, 13, 15, 17, 18, 20 };
Integer[] postOrder = { 2, 4, 3, 7, 6, 15, 20, 18, 17, 13 };
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
myAVL.insert(2);
myAVL.insert(4);
myAVL.insert(7);
myAVL.insert(13);
myAVL.insert(9);
myAVL.insert(18);
myAVL.insert(17);
myAVL.insert(20);
myAVL.remove(9);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testRemove2() {
Integer[] preOrder = { 13, 6, 3, 2, 4, 7, 9, 18, 17, 20 };
Integer[] order = { 2, 3, 4, 6, 7, 9, 13, 17, 18, 20 };
Integer[] postOrder = { 2, 4, 3, 9, 7, 6, 17, 20, 18, 13 };
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
myAVL.insert(2);
myAVL.insert(4);
myAVL.insert(7);
myAVL.insert(13);
myAVL.insert(9);
myAVL.insert(18);
myAVL.insert(17);
myAVL.insert(20);
myAVL.remove(15);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testRemove3() {
Integer[] preOrder = { 13, 3, 2, 6, 4, 17, 15, 18, 20 };
Integer[] order = { 2, 3, 4, 6, 13, 15, 17, 18, 20 };
Integer[] postOrder = { 2, 4, 6, 3, 15, 20, 18, 17, 13 };
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
myAVL.insert(2);
myAVL.insert(4);
myAVL.insert(7);
myAVL.insert(13);
myAVL.insert(9);
myAVL.insert(18);
myAVL.insert(17);
myAVL.insert(20);
myAVL.remove(9);
myAVL.remove(7);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testRemove4() {
Integer[] preOrder = { 13, 4, 3, 6, 17, 15, 18, 20 };
Integer[] order = { 3, 4, 6, 13, 15, 17, 18, 20 };
Integer[] postOrder = { 3, 6, 4, 15, 20, 18, 17, 13 };
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
myAVL.insert(2);
myAVL.insert(4);
myAVL.insert(7);
myAVL.insert(13);
myAVL.insert(9);
myAVL.insert(18);
myAVL.insert(17);
myAVL.insert(20);
myAVL.remove(2);
myAVL.remove(9);
myAVL.remove(7);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testRemove5() {
Integer[] preOrder = { 13, 6, 3, 2, 4, 7, 9, 19, 17, 20 };
Integer[] order = { 2, 3, 4, 6, 7, 9, 13, 17, 19, 20 };
Integer[] postOrder = { 2, 4, 3, 9, 7, 6, 17, 20, 19, 13 };
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
myAVL.insert(2);
myAVL.insert(4);
myAVL.insert(7);
myAVL.insert(13);
myAVL.insert(9);
myAVL.insert(20);
myAVL.insert(17);
myAVL.insert(19);
myAVL.remove(15);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testRemove6() {
Integer[] preOrder = { 15, 6, 3, 2, 4, 7, 9, 18, 17, 20 };
Integer[] order = { 2, 3, 4, 6, 7, 9, 15, 17, 18, 20 };
Integer[] postOrder = { 2, 4, 3, 9, 7, 6, 17, 20, 18, 15 };
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
myAVL.insert(2);
myAVL.insert(4);
myAVL.insert(7);
myAVL.insert(13);
myAVL.insert(9);
myAVL.insert(18);
myAVL.insert(17);
myAVL.insert(20);
myAVL.remove(13);
assertArrayEquals(preOrder, myAVL.preOrder());
assertArrayEquals(order, myAVL.order());
assertArrayEquals(postOrder, myAVL.postOrder());
}
@Test
public void testMaximum0() {
myAVL.insert(12);
assertEquals(new Integer(12), myAVL.maximum().getData());
}
@Test
public void testMaximum1() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
assertEquals(new Integer(12), myAVL.maximum().getData());
}
@Test
public void testMaximum2() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
assertEquals(new Integer(18), myAVL.maximum().getData());
}
@Test
public void testMaximum3() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(19), myAVL.maximum().getData());
}
@Test
public void testMaximum4() {
assertNull(myAVL.maximum());
}
@Test
public void testMinimum0() {
myAVL.insert(12);
assertEquals(new Integer(12), myAVL.minimum().getData());
}
@Test
public void testMinimum1() {
myAVL.insert(12);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(12), myAVL.minimum().getData());
}
@Test
public void testMinimum2() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(5), myAVL.minimum().getData());
}
@Test
public void testMinimum3() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(2);
myAVL.insert(9);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(2), myAVL.minimum().getData());
}
@Test
public void testMinimum4() {
assertNull(myAVL.minimum());
}
@Test
public void testSucessor0() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(5), myAVL.sucessor(2).getData());
}
@Test
public void testSucessor1() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(9), myAVL.sucessor(5).getData());
}
@Test
public void testSucessor2() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(12), myAVL.sucessor(9).getData());
}
@Test
public void testSucessor3() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(13), myAVL.sucessor(12).getData());
}
@Test
public void testSucessor4() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(18), myAVL.sucessor(17).getData());
}
@Test
public void testSucessor5() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertNull(myAVL.sucessor(19));
}
@Test
public void testSucessor6() {
myAVL.insert(15);
myAVL.insert(6);
myAVL.insert(3);
myAVL.insert(2);
myAVL.insert(4);
myAVL.insert(7);
myAVL.insert(13);
myAVL.insert(9);
myAVL.insert(18);
myAVL.insert(17);
myAVL.insert(20);
assertEquals(new Integer(15), myAVL.sucessor(13).getData());
}
@Test
public void testPredecessor0() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertNull(myAVL.predecessor(2));
}
@Test
public void testPredecessor1() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(2), myAVL.predecessor(5).getData());
}
@Test
public void testPredecessor2() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(5), myAVL.predecessor(9).getData());
}
@Test
public void testPredecessor3() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(9), myAVL.predecessor(12).getData());
}
@Test
public void testPredecessor4() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(12), myAVL.predecessor(13).getData());
}
@Test
public void testPredecessor5() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(new Integer(18), myAVL.predecessor(19).getData());
}
@Test
public void testSize1() {
myAVL.insert(19);
assertEquals(1, myAVL.size());
}
@Test
public void testSize2() {
myAVL.insert(12);
myAVL.insert(5);
myAVL.insert(9);
myAVL.insert(2);
myAVL.insert(18);
myAVL.insert(15);
myAVL.insert(17);
myAVL.insert(13);
myAVL.insert(19);
assertEquals(9, myAVL.size());
}
protected AVLTree<Integer> tree1;
protected AVLTree<Integer> tree2;
protected AVLTree<Integer> tree3;
protected AVLTree<Integer> tree4;
protected AVLTree<Integer> tree5;
protected AVLTree<Integer> tree6;
protected Integer[] data = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
protected static final int SIZE = 10;
@Before
public void setUp() throws Exception {
tree1 = new AVLTreeImpl<Integer>();
tree1.insert(1);
tree1.insert(4);
tree1.insert(7);
tree1.insert(10);
tree1.insert(13);
tree1.insert(2);
tree1.insert(5);
tree1.insert(8);
tree1.insert(11);
tree1.insert(14);
tree1.insert(3);
tree1.insert(15);
tree1.insert(6);
tree1.insert(12);
tree1.insert(9);
tree2 = new AVLTreeImpl<Integer>();
}
@Test
public void testInsert() {
Integer[] preOrder1 = {10,4,2,1,3,7,5,6,8,9,13,11,12,14,15};
assertEquals(Arrays.toString(preOrder1), Arrays.toString(tree1.preOrder()));
assertEquals("[]", Arrays.toString(tree2.preOrder()));
Integer[] preOrder2 = {10,4,2,1,3,7,5,6,8,9,13,11,12,15,14,20,18,22};
tree1.insert(22);
tree1.insert(18);
tree1.insert(20);
assertEquals(Arrays.toString(preOrder2), Arrays.toString(tree1.preOrder()));
}
@Test
public void testRemove() {
//removendo uma folha sem causar rebalanceamento
tree1.remove(6);
Integer[] preOrder1 = {10,4,2,1,3,7,5,8,9,13,11,12,14,15};
assertEquals(Arrays.toString(preOrder1), Arrays.toString(tree1.preOrder()));
//removendo no com um filho apenas sem causar rebaleanceamento
tree1.remove(11);
Integer[] preOrder2 = {10,4,2,1,3,7,5,8,9,13,12,14,15};
assertEquals(Arrays.toString(preOrder2), Arrays.toString(tree1.preOrder()));
//removendo um no com dois filhos que causa um rebalanceamento
tree1.remove(13);
Integer[] preOrder3 = {7,4,2,1,3,5,10,8,9,14,12,15};
assertEquals(Arrays.toString(preOrder3), Arrays.toString(tree1.preOrder()));
tree2.remove(10);
assertEquals("[]", Arrays.toString(tree2.preOrder()));
}
@Test
public void testHeight(){
assertEquals(4,tree1.height());
assertEquals(-1,tree2.height());
tree1.insert(22);
assertEquals(4,tree1.height());
tree1.insert(18);
assertEquals(4,tree1.height());
tree1.insert(20);
assertEquals(4,tree1.height());
tree1.insert(17);
assertEquals(4,tree1.height());
tree1.insert(16);
assertEquals(4,tree1.height());
tree1.insert(19);
assertEquals(4,tree1.height());
tree1.insert(21);
assertEquals(5,tree1.height());
}
}
Raw
AVLTeste2
package adt.avltree;
import static org.junit.Assert.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
import adt.bst.BSTNode;
/*
* Author: Ordan Santos
*/
public class AVLTeste2 {
private AVLTree<Integer> tree;
private BSTNode<Integer> NIL = new BSTNode<Integer>();
private void fillTree() {
for(int i = 0; i < 10 ; i++) {
tree.insert(i);
}
}
@Before
public void setUp() {
tree = new AVLTreeImpl<>();
}
@Test
public void testInit() {
assertTrue(tree.isEmpty());
assertEquals(0, tree.size());
assertEquals(-1, tree.height());
assertEquals(NIL, tree.getRoot());
assertArrayEquals(new Integer[] {}, tree.order());
assertArrayEquals(new Integer[] {}, tree.preOrder());
assertArrayEquals(new Integer[] {}, tree.postOrder());
assertEquals(NIL, tree.search(12));
assertEquals(NIL, tree.search(-23));
assertEquals(NIL, tree.search(0));
assertEquals(null, tree.minimum());
assertEquals(null, tree.maximum());
assertEquals(null, tree.sucessor(12));
assertEquals(null, tree.sucessor(-23));
assertEquals(null, tree.sucessor(0));
assertEquals(null, tree.predecessor(12));
assertEquals(null, tree.predecessor(-23));
assertEquals(null, tree.predecessor(0));
}
@Test
public void testMinMax() {
tree.insert(6);
assertEquals(new Integer(6), tree.minimum().getData());
assertEquals(new Integer(6), tree.maximum().getData());
tree.insert(23);
assertEquals(new Integer(6), tree.minimum().getData());
assertEquals(new Integer(23), tree.maximum().getData());
tree.insert(-34);
assertEquals(new Integer(-34), tree.minimum().getData());
assertEquals(new Integer(23), tree.maximum().getData());
tree.insert(5);
assertEquals(new Integer(-34), tree.minimum().getData());
assertEquals(new Integer(23), tree.maximum().getData());
tree.insert(9);
assertEquals(new Integer(-34), tree.minimum().getData());
assertEquals(new Integer(23), tree.maximum().getData());
}
@Test
public void testSucessorPredecessor() {
fillTree();
assertEquals(null, tree.predecessor(15));
assertEquals(new Integer(3), tree.sucessor(2).getData());
assertEquals(new Integer(3), tree.predecessor(4).getData());
assertEquals(new Integer(5), tree.sucessor(4).getData());
}
@Test
public void testSize() {
fillTree();
int size = 10;
assertEquals(size, tree.size());
while(!tree.isEmpty()) {
tree.remove(tree.getRoot().getData());
assertEquals(--size, tree.size());
}
}
@Test
public void testHeight() {
fillTree();
Integer[] preOrder = new Integer[] {3,1,0,2,7,5,4,6,8,9};
assertArrayEquals(preOrder, tree.preOrder());
assertEquals(3, tree.height());
tree.remove(0);
assertEquals(3, tree.height());
tree.remove(2);
assertEquals(3, tree.height());
tree.remove(1);
assertEquals(3, tree.height());
Integer[] preOrder2 = new Integer[] {7,5,3,4,6,8,9};
assertArrayEquals(preOrder2, tree.preOrder());
}
@Test
public void testRemove() {
fillTree();
//tente remover elementos e verificar se as rotacoes produzem uma AVL correta
}
@Test
public void testSearch() {
fillTree();
assertEquals(NIL, tree.search(-40));
assertEquals(new Integer(4), tree.search(4).getData());
}
@Test
public void bruteHeightTest(){
for (int i = 1; i <= 10000; i++){
tree.insert(i);
Assert.assertTrue(tree.height() <= maxPossibleHeight(i));
Assert.assertEquals(i, tree.size());
Assert.assertTrue(testBalance((BSTNode<Integer>) tree.getRoot()));
}
}
private double log2(double n){
return Math.log(n) / Math.log(2);
}
private int maxPossibleHeight(int n){
if (n==0)
return 0;
return (int) (2 * log2(n));
}
@Test
public void left(){
tree.insert(2);
tree.insert(1);
tree.insert(0);
Assert.assertEquals(1, tree.height());
Assert.assertEquals(new Integer(1), tree.getRoot().getData());
Assert.assertEquals(new Integer(0), tree.getRoot().getLeft().getData());
Assert.assertEquals(new Integer(2), tree.getRoot().getRight().getData());
Assert.assertEquals(tree.getRoot().getLeft().getParent(), tree.getRoot());
Assert.assertEquals(tree.getRoot().getRight().getParent(), tree.getRoot());
Assert.assertEquals(tree.getRoot().getParent(), null);
}
@Test
public void right(){
tree.insert(1);
tree.insert(2);
tree.insert(3);
Assert.assertEquals(1, tree.height());
Assert.assertEquals(new Integer(2), tree.getRoot().getData());
Assert.assertEquals(new Integer(1), tree.getRoot().getLeft().getData());
Assert.assertEquals(new Integer(3), tree.getRoot().getRight().getData());
Assert.assertEquals(tree.getRoot().getLeft().getParent(), tree.getRoot());
Assert.assertEquals(tree.getRoot().getRight().getParent(), tree.getRoot());
Assert.assertEquals(tree.getRoot().getParent(), null);
}
@Test
public void rightleft(){
tree.insert(5);
tree.insert(6);
tree.insert(0);
tree.insert(1);
tree.insert(-1);
tree.insert(2);
Assert.assertEquals(2, tree.height());
Assert.assertEquals(new Integer(1), tree.getRoot().getData());
Assert.assertEquals(new Integer(0), tree.getRoot().getLeft().getData());
Assert.assertEquals(new Integer(5), tree.getRoot().getRight().getData());
Assert.assertEquals(new Integer(-1), tree.getRoot().getLeft().getLeft().getData());
Assert.assertEquals(new Integer(2), tree.getRoot().getRight().getLeft().getData());
Assert.assertEquals(new Integer(6), tree.getRoot().getRight().getRight().getData());
Assert.assertArrayEquals(new Integer[]{1, 0, -1, 5, 2, 6}, tree.preOrder());
}
@Test
public void leftRight(){
tree.insert(3);
tree.insert(2);
tree.insert(7);
tree.insert(5);
tree.insert(8);
tree.insert(4);
Assert.assertEquals(2, tree.height());
Assert.assertEquals(new Integer(5), tree.getRoot().getData());
Assert.assertEquals(new Integer(3), tree.getRoot().getLeft().getData());
Assert.assertEquals(new Integer(7), tree.getRoot().getRight().getData());
Assert.assertEquals(new Integer(2), tree.getRoot().getLeft().getLeft().getData());
Assert.assertEquals(new Integer(4), tree.getRoot().getLeft().getRight().getData());
Assert.assertEquals(new Integer(8), tree.getRoot().getRight().getRight().getData());
Assert.assertArrayEquals(new Integer[]{5, 3, 2, 4, 7, 8}, tree.preOrder());
}
private boolean testParents(BSTNode<Integer> node, BSTNode<Integer> parent){
if (node.isEmpty()) return true;
if (!node.getParent().equals(parent)) return false;
return testParents((BSTNode<Integer>) node.getLeft(), node) && testParents((BSTNode<Integer>) node.getRight(), node);
}
private boolean testBalance(BSTNode<Integer> node){
if (node.isEmpty()) return true;
int balance = height((BSTNode<Integer>) node.getLeft()) - height((BSTNode<Integer>) node.getRight());
if (Math.abs(balance) > 1) return false;
return testBalance((BSTNode<Integer>) node.getLeft()) && testBalance((BSTNode<Integer>) node.getRight());
}
@Test
public void fuckingTest(){
ArrayList<Integer> myarray = new ArrayList<Integer>();
Random gerador = new Random();
for (int i = 0; i < 10000; i++){
int k = gerador.nextInt(2);
int element = gerador.nextInt(30);
if (k == 0){
if (myarray.contains(element) == true)
myarray.remove(myarray.indexOf(element));
tree.remove(element);
Collections.sort(myarray);
Assert.assertArrayEquals(myarray.toArray(), tree.order());
Assert.assertTrue(tree.height() <= maxPossibleHeight(myarray.size()));
Assert.assertEquals(tree.size(), myarray.size());
} else {
if (myarray.contains(element)) {
myarray.add(element);
tree.insert(element);
}
this.printArray(myarray.toArray());
this.printArray(tree.order());
Collections.sort(myarray);
Assert.assertArrayEquals(myarray.toArray(), tree.order());
Assert.assertTrue(tree.height() <= maxPossibleHeight(myarray.size()));
Assert.assertEquals(tree.size(), myarray.size());
}
Assert.assertTrue(testParents((BSTNode<Integer>) tree.getRoot(), NIL));
Assert.assertTrue(testBalance((BSTNode<Integer>) tree.getRoot()));
}
}
private void printArray(Object[] objects) {
for (Object e : objects) {
System.out.print(e + " ");
}
System.out.println();
}
private int height(BSTNode<Integer> node) {
if (node.isEmpty()) return -1;
return 1 + Math.max(height((BSTNode<Integer>)node.getLeft()), height((BSTNode<Integer>)node.getRight()));
}
}
Raw
AVLTeste3
package adt.avltree;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import org.junit.Before;
import org.junit.Test;
import adt.bst.BSTNode;
public class AVLTeste3 {
private AVLTree<Integer> tree;
private BSTNode<Integer> NIL = new BSTNode<Integer>();
private void fillTree() {
for(int i = 0; i < 10 ; i++) {
tree.insert(i);
}
// nível 0: 3
// nível 1: 1|>>>>>> <<<<<<|7
// nível 2: 0|>> <<|2 5|>> <<|8
// nível 3: 4|>> <<|6 <<|9
// pré-ordem: 3 1 0 2 7 5 4 6 8 9
}
@Before
public void setUp() {
tree = new AVLTreeImpl<>();
}
@Test
public void testInit() {
assertTrue(tree.isEmpty());
assertEquals(0, tree.size());
assertEquals(-1, tree.height());
assertEquals(NIL, tree.getRoot());
assertArrayEquals(new Integer[] {}, tree.order());
assertArrayEquals(new Integer[] {}, tree.preOrder());
assertArrayEquals(new Integer[] {}, tree.postOrder());
assertEquals(NIL, tree.search(12));
assertEquals(NIL, tree.search(-23));
assertEquals(NIL, tree.search(0));
assertEquals(null, tree.minimum());
assertEquals(null, tree.maximum());
assertEquals(null, tree.sucessor(12));
assertEquals(null, tree.sucessor(-23));
assertEquals(null, tree.sucessor(0));
assertEquals(null, tree.predecessor(12));
assertEquals(null, tree.predecessor(-23));
assertEquals(null, tree.predecessor(0));
}
@Test
public void testInsert() throws Exception {
fillTree();
Integer[] expecteds = {3, 1, 0, 2, 7, 5, 4, 6, 8, 9};
assertArrayEquals(expecteds, tree.preOrder());
Integer[] expect2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
assertArrayEquals(expect2, tree.order());
Integer[] expect3 = {0, 2, 1, 4, 6, 5, 9, 8, 7, 3};
assertArrayEquals(expect3, tree.postOrder());
assertEquals(expecteds.length, tree.size());
assertEquals(3, tree.height());
}
@Test
public void testMinMax() {
tree.insert(6);
assertEquals(new Integer(6), tree.minimum().getData());
assertEquals(new Integer(6), tree.maximum().getData());
tree.insert(23);
assertEquals(new Integer(6), tree.minimum().getData());
assertEquals(new Integer(23), tree.maximum().getData());
tree.insert(-34);
assertEquals(new Integer(-34), tree.minimum().getData());
assertEquals(new Integer(23), tree.maximum().getData());
tree.insert(5);
assertEquals(new Integer(-34), tree.minimum().getData());
assertEquals(new Integer(23), tree.maximum().getData());
tree.insert(9);
assertEquals(new Integer(-34), tree.minimum().getData());
assertEquals(new Integer(23), tree.maximum().getData());
}
@Test
public void testSucessorPredecessor() {
fillTree();
assertEquals(null, tree.predecessor(15));
assertEquals(new Integer(3), tree.sucessor(2).getData());
assertEquals(new Integer(3), tree.predecessor(4).getData());
assertEquals(new Integer(5), tree.sucessor(4).getData());
}
@Test
public <T> void testSize() {
fillTree();
int size = 10;
assertEquals(tree.size(), 10);
while(!tree.isEmpty()) {
tree.remove(tree.getRoot().getData());
assertEquals(--size, tree.size());
}
}
@Test
public void testHeight() {
fillTree();
Integer[] preOrder = new Integer[] {3,1,0,2,7,5,4,6,8,9};
assertArrayEquals(preOrder, tree.preOrder());
assertEquals(3, tree.height());
tree.remove(0);
assertEquals(3, tree.height());
tree.remove(2);
assertEquals(3, tree.height());
tree.remove(1);
assertEquals(3, tree.height());
Integer[] preOrder2 = new Integer[] {7,5,3,4,6,8,9};
assertArrayEquals(preOrder2, tree.preOrder());
}
@Test
public void testRemove() {
fillTree();
tree.remove(0);
assertEquals(3, tree.height());
tree.remove(2);
assertEquals(3, tree.height());
Integer[] preOrder = new Integer[]{ 7,3,1,5,4,6,8,9 };
assertArrayEquals(preOrder, tree.preOrder());
tree.remove(7);
assertEquals(2, tree.height());
Integer[] preOrder2 = new Integer[]{ 5, 3, 1, 4, 8, 6, 9 };
assertArrayEquals(preOrder2, tree.preOrder());
}
@Test
public void testSearch() {
fillTree();
assertEquals(NIL, tree.search(-40));
assertEquals(new Integer(4), tree.search(4).getData());
}
}
Raw
StudentAVLTest2
package adt.avltree;
import static org.junit.Assert.*;
import org.junit.Test;
import org.junit.Before;
import adt.bst.BSTNode;
public class StudentAVLTest2 {
private AVLTree<Integer> avl;
private BSTNode<Integer> NIL = new BSTNode<Integer>();
@Before
public void setUp() {
avl = new AVLTreeImpl<>();
}
@Test
public void testInit() {
assertTrue(avl.isEmpty());
assertEquals(0, avl.size());
assertEquals(-1, avl.height());
assertEquals(NIL, avl.getRoot());
}
@Test
public void testInsert() {
avl.insert(-10);
assertEquals(1, avl.size());
assertEquals(0, avl.height());
assertArrayEquals(new Integer[] { -10 }, avl.preOrder());
assertFalse(avl.isEmpty());
assertEquals(new Integer(-10), avl.getRoot().getData());
avl.insert(-15);
assertEquals(2, avl.size());
assertEquals(1, avl.height());
assertArrayEquals(new Integer[] { -10, -15 }, avl.preOrder());
avl.insert(20);
assertEquals(3, avl.size());
assertEquals(1, avl.height());
assertArrayEquals(new Integer[] { -10, -15, 20 }, avl.preOrder());
}
@Test
public void testRemove() {
avl.insert(55);
avl.insert(9);
avl.insert(91);
avl.insert(12);
avl.remove(-1);
assertEquals(4, avl.size());
avl.remove(91);
assertEquals(3, avl.size());
assertArrayEquals(new Integer[] { 12, 9, 55 }, avl.preOrder());
avl.remove(12);
assertEquals(2, avl.size());
assertArrayEquals(new Integer[] { 55, 9 }, avl.preOrder());
avl.remove(9);
avl.remove(55);
assertEquals(NIL, avl.getRoot());
assertTrue(avl.isEmpty());
}
private void fillTree() {
for (int i = 1; i < 11; i++) {
avl.insert(i);
}
}
@Test
public void testRemove2() {
fillTree();
avl.remove(new Integer(6));
assertEquals(new Integer(8), avl.search(7).getParent().getData());// parent
assertEquals(new Integer(7), avl.search(5).getParent().getData());// parent
assertEquals(new Integer(7), avl.search(8).getLeft().getData());// leftNode
avl.remove(new Integer(7));
assertEquals(new Integer(8), avl.search(5).getParent().getData());// parent
assertEquals(new Integer(5), avl.search(8).getLeft().getData());// leftNode
avl.remove(new Integer(5));
assertEquals(new Integer(9), avl.search(8).getParent().getData());// parent
assertEquals(new Integer(4), avl.search(9).getParent().getData());// parent
assertEquals(new Integer(8), avl.search(9).getLeft().getData());// leftNode
assertEquals(new Integer(10), avl.search(9).getRight().getData());// rightNode
avl.remove(new Integer(3));
avl.remove(new Integer(1));
avl.remove(new Integer(2));
assertEquals(new Integer(4), avl.search(8).getParent().getData());// parent
assertEquals(new Integer(9), avl.search(4).getParent().getData());// parent
assertEquals(null, avl.search(9).getParent());// parent
assertEquals(new Integer(9), avl.search(10).getParent().getData());// parent
assertEquals(null, avl.search(8).getLeft().getData());// leftNode
assertEquals(null, avl.search(4).getLeft().getData());// leftNode
assertEquals(new Integer(4), avl.search(9).getLeft().getData());// leftNode
assertEquals(null, avl.search(10).getLeft().getData());// leftNode
assertEquals(null, avl.search(8).getRight().getData());// rightNode
assertEquals(new Integer(8), avl.search(4).getRight().getData());// rightNode
assertEquals(new Integer(10), avl.search(9).getRight().getData());// rightNode
assertEquals(null, avl.search(10).getRight().getData());// rightNode
}
}
Raw
StudentBSTTest
package adt.avltree;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import org.junit.Before;
import org.junit.Test;
import adt.bst.BSTImpl;
import adt.bt.BTNode;
public class StudentBSTTest {
private BSTImpl<Integer> tree;
private BTNode<Integer> NIL = new BTNode<Integer>();
private void fillTree() {
Integer[] array = { 6, 23, -34, 5, 9, 2, 0, 76, 12, 67, 232, -40 };
for (int i : array) {
tree.insert(i);
}
}
@Before
public void setUp() {
tree = new BSTImpl<>();
}
@Test
public void prePostOrdeTest() {
fillTree();// 6, 23, -34, 5, 9, 2, 0, 76, 12, 67, 232, -40
assertArrayEquals(
new Integer[] { 6, -34, -40, 5, 2, 0, 23, 9, 12, 76, 67, 232 },
tree.preOrder());
assertArrayEquals(
new Integer[] { -40, -34, 0, 2, 5, 6, 9, 12, 23, 67, 76, 232 },
tree.order());
assertArrayEquals(
new Integer[] { -40, 0, 2, 5, -34, 12, 9, 67, 232, 76, 23, 6 },
tree.postOrder());
tree.remove(6);
assertArrayEquals(
new Integer[] { 9, -34, -40, 5, 2, 0, 23, 12, 76, 67, 232 },
tree.preOrder());
assertArrayEquals(
new Integer[] { -40, -34, 0, 2, 5, 9, 12, 23, 67, 76, 232 },
tree.order());
assertArrayEquals(
new Integer[] { -40, 0, 2, 5, -34, 12, 67, 232, 76, 23, 9 },
tree.postOrder());
tree.remove(5);
tree.remove(23);
tree.remove(-34);
assertArrayEquals(new Integer[] { 9, 0, -40, 2, 67, 12, 76, 232 },
tree.preOrder());
assertArrayEquals(new Integer[] { -40, 0, 2, 9, 12, 67, 76, 232 },
tree.order());
assertArrayEquals(new Integer[] { -40, 2, 0, 12, 232, 76, 67, 9 },
tree.postOrder());
tree.remove(9);
tree.remove(67);
tree.remove(0);
assertArrayEquals(new Integer[] { 12, 2, -40, 76, 232 },
tree.preOrder());
assertArrayEquals(new Integer[] { -40, 2, 12, 76, 232 }, tree.order());
assertArrayEquals(new Integer[] { -40, 2, 232, 76, 12 },
tree.postOrder());
tree.remove(12);
tree.remove(76);
tree.remove(2);
assertArrayEquals(new Integer[] { 232, -40 }, tree.preOrder());
assertArrayEquals(new Integer[] { -40, 232 }, tree.order());
assertArrayEquals(new Integer[] { -40, 232 }, tree.postOrder());
tree.remove(-40);
assertArrayEquals(new Integer[] { 232 }, tree.preOrder());
assertArrayEquals(new Integer[] { 232 }, tree.order());
assertArrayEquals(new Integer[] { 232 }, tree.postOrder());
}
@Test
public void countingTest() {
tree.insert(50);
tree.insert(17);
tree.insert(9);
tree.insert(14);
tree.insert(12);
tree.insert(23);
tree.insert(19);
tree.insert(76);
tree.insert(54);
tree.insert(72);
tree.insert(67);
fillTree();
}
@Test
public void testInit() {
assertTrue(tree.isEmpty());
assertEquals(0, tree.size());
assertEquals(-1, tree.height());
assertEquals(NIL, tree.getRoot());
assertArrayEquals(new Integer[] {}, tree.order());
assertArrayEquals(new Integer[] {}, tree.preOrder());
assertArrayEquals(new Integer[] {}, tree.postOrder());
assertEquals(NIL, tree.search(12));
assertEquals(NIL, tree.search(-23));
assertEquals(NIL, tree.search(0));
assertEquals(null, tree.minimum());
assertEquals(null, tree.maximum());
assertEquals(null, tree.sucessor(12));
assertEquals(null, tree.sucessor(-23));
assertEquals(null, tree.sucessor(0));
assertEquals(null, tree.predecessor(12));
assertEquals(null, tree.predecessor(-23));
assertEquals(null, tree.predecessor(0));
}
@Test
public void removeLeafsTest() {
fillTree();
assertEquals(4, tree.height());
tree.remove(0);
assertEquals(3, tree.height());
tree.remove(2);
tree.remove(12);
tree.remove(67);
tree.remove(232);
assertEquals(2, tree.height());
tree.remove(-40);
tree.remove(5);
tree.remove(9);
tree.remove(76);
assertEquals(1, tree.height());
tree.remove(-34);
tree.remove(23);
assertEquals(0, tree.height());
tree.remove(6);
assertEquals(-1, tree.height());
}
@Test
public void parentTest() {
fillTree();
assertEquals(null, tree.search(6).getParent());
assertEquals(new Integer(6), tree.search(-34).getParent().getData());
assertEquals(new Integer(-34), tree.search(-40).getParent().getData());
assertEquals(new Integer(-34), tree.search(5).getParent().getData());
assertEquals(new Integer(5), tree.search(2).getParent().getData());
assertEquals(new Integer(2), tree.search(0).getParent().getData());
assertEquals(new Integer(6), tree.search(23).getParent().getData());
assertEquals(new Integer(23), tree.search(9).getParent().getData());
assertEquals(new Integer(9), tree.search(12).getParent().getData());
assertEquals(new Integer(23), tree.search(76).getParent().getData());
assertEquals(new Integer(76), tree.search(67).getParent().getData());
assertEquals(new Integer(76), tree.search(232).getParent().getData());
assertEquals(new Integer(-34), tree.search(6).getLeft().getData());
assertEquals(new Integer(-40), tree.search(-34).getLeft().getData());
assertEquals(null, tree.search(-40).getLeft().getData());
assertEquals(new Integer(2), tree.search(5).getLeft().getData());
assertEquals(new Integer(0), tree.search(2).getLeft().getData());
assertEquals(null, tree.search(0).getLeft().getData());
assertEquals(new Integer(9), tree.search(23).getLeft().getData());
assertEquals(null, tree.search(9).getLeft().getData());
assertEquals(null, tree.search(12).getLeft().getData());
assertEquals(new Integer(67), tree.search(76).getLeft().getData());
assertEquals(null, tree.search(67).getLeft().getData());
assertEquals(null, tree.search(232).getLeft().getData());
assertEquals(null, tree.search(-40).getRight().getData());
assertEquals(new Integer(5), tree.search(-34).getRight().getData());
assertEquals(null, tree.search(5).getRight().getData());
assertEquals(null, tree.search(2).getRight().getData());
assertEquals(null, tree.search(0).getRight().getData());
assertEquals(new Integer(23), tree.search(6).getRight().getData());
assertEquals(new Integer(76), tree.search(23).getRight().getData());
assertEquals(new Integer(232), tree.search(76).getRight().getData());
assertEquals(null, tree.search(232).getRight().getData());
assertEquals(null, tree.search(67).getRight().getData());
assertEquals(new Integer(12), tree.search(9).getRight().getData());
assertEquals(null, tree.search(12).getRight().getData());
}
@Test
public void removedParentTest() {
fillTree();
assertEquals(12, tree.size());
tree.remove(76);
assertEquals(null, tree.search(76).getData());
assertEquals(new Integer(232), tree.search(23).getRight().getData());
assertEquals(new Integer(67), tree.search(232).getLeft().getData());
assertEquals(null, tree.search(232).getRight().getData());
assertEquals(new Integer(23), tree.search(232).getParent().getData());
assertEquals(11, tree.size());
tree.remove(232);
assertEquals(null, tree.search(232).getData());
assertEquals(new Integer(67), tree.search(23).getRight().getData());
assertEquals(null, tree.search(67).getLeft().getData());
assertEquals(null, tree.search(67).getRight().getData());
assertEquals(new Integer(23), tree.search(67).getParent().getData());
assertEquals(10, tree.size());
tree.remove(67);
assertEquals(null, tree.search(67).getData());
assertEquals(null, tree.search(23).getRight().getData());
assertEquals(9, tree.size());
tree.remove(9);
assertEquals(null, tree.search(9).getData());
assertEquals(new Integer(12), tree.search(23).getLeft().getData());
assertEquals(null, tree.search(12).getLeft().getData());
assertEquals(new Integer(23), tree.search(12).getParent().getData());
assertEquals(8, tree.size());
tree.remove(23);
assertEquals(null, tree.search(23).getData());
assertEquals(new Integer(12), tree.search(6).getRight().getData());
assertEquals(null, tree.search(12).getRight().getData());
assertEquals(null, tree.search(12).getLeft().getData());
assertEquals(new Integer(6), tree.search(12).getParent().getData());
assertEquals(7, tree.size());
tree.remove(-34);
assertEquals(null, tree.search(-34).getData());
assertEquals(new Integer(0), tree.search(6).getLeft().getData());
assertEquals(new Integer(5), tree.search(0).getRight().getData());
assertEquals(new Integer(-40), tree.search(0).getLeft().getData());
assertEquals(new Integer(6), tree.search(0).getParent().getData());
assertEquals(6, tree.size());
tree.remove(6);
assertEquals(null, tree.search(6).getData());
assertEquals(new Integer(12), tree.getRoot().getData());
assertEquals(null, tree.search(12).getRight().getData());
assertEquals(new Integer(0), tree.search(12).getLeft().getData());
assertEquals(new Integer(12), tree.search(0).getParent().getData());
assertEquals(5, tree.size());
tree.remove(0);
assertEquals(null, tree.search(0).getData());
assertEquals(new Integer(12), tree.getRoot().getData());
assertEquals(new Integer(2), tree.getRoot().getLeft().getData());
assertEquals(new Integer(12), tree.search(2).getParent().getData());
assertEquals(new Integer(-40), tree.search(2).getLeft().getData());
assertEquals(new Integer(5), tree.search(2).getRight().getData());
assertEquals(new Integer(2), tree.search(-40).getParent().getData());
assertEquals(new Integer(2), tree.search(5).getParent().getData());
assertEquals(4, tree.size());
tree.remove(12);
assertEquals(null, tree.search(12).getData());
assertEquals(new Integer(2), tree.getRoot().getData());
assertEquals(new Integer(-40), tree.search(2).getLeft().getData());
assertEquals(new Integer(5), tree.search(2).getRight().getData());
assertEquals(new Integer(2), tree.search(-40).getParent().getData());
assertEquals(new Integer(2), tree.search(5).getParent().getData());
assertEquals(3, tree.size());
tree.remove(tree.getRoot().getData());
assertEquals(null, tree.search(2).getData());
assertEquals(new Integer(5), tree.getRoot().getData());
assertEquals(new Integer(-40), tree.search(5).getLeft().getData());
assertEquals(null, tree.search(5).getRight().getData());
assertEquals(new Integer(5), tree.search(-40).getParent().getData());
assertEquals(2, tree.size());
tree.remove(tree.getRoot().getData());
assertEquals(null, tree.search(5).getData());
assertEquals(new Integer(-40), tree.getRoot().getData());
assertEquals(null, tree.search(-40).getLeft().getData());
assertEquals(null, tree.search(-40).getRight().getData());
assertEquals(null, tree.search(-40).getParent());
assertEquals(1, tree.size());
tree.remove(-40);
assertEquals(null, tree.search(-40).getData());
assertEquals(null, tree.getRoot().getData());
assertEquals(null, tree.getRoot().getLeft());
assertEquals(null, tree.getRoot().getRight());
assertEquals(0, tree.size());
}
@Test
public void heightTest() {
fillTree();
tree.remove(-40);
tree.remove(23);
tree.remove(9);
tree.remove(76);
tree.remove(67);
tree.remove(12);
tree.remove(232);
assertEquals(4, tree.height());
tree.insert(3);
assertEquals(4, tree.height());
tree.insert(4);
assertEquals(5, tree.height());
tree.remove(0);
assertEquals(5, tree.height());
tree.remove(2);
assertEquals(4, tree.height());
}
@Test
public void predecessorSucessorTest() {
fillTree();
assertEquals(new Integer(9), tree.sucessor(6).getData());
assertEquals(new Integer(5), tree.predecessor(6).getData());
assertEquals(new Integer(0), tree.sucessor(-34).getData());
assertEquals(new Integer(-40), tree.predecessor(-34).getData());
assertEquals(new Integer(-34), tree.sucessor(-40).getData());
assertEquals(null, tree.predecessor(-40));
assertEquals(new Integer(6), tree.sucessor(5).getData());
assertEquals(new Integer(2), tree.predecessor(5).getData());
assertEquals(new Integer(5), tree.sucessor(2).getData());
assertEquals(new Integer(0), tree.predecessor(2).getData());
assertEquals(new Integer(2), tree.sucessor(0).getData());
assertEquals(new Integer(-34), tree.predecessor(0).getData());
assertEquals(new Integer(67), tree.sucessor(23).getData());
assertEquals(new Integer(12), tree.predecessor(23).getData());
assertEquals(new Integer(12), tree.sucessor(9).getData());
assertEquals(new Integer(6), tree.predecessor(9).getData());
assertEquals(new Integer(23), tree.sucessor(12).getData());
assertEquals(new Integer(9), tree.predecessor(12).getData());
assertEquals(new Integer(232), tree.sucessor(76).getData());
assertEquals(new Integer(67), tree.predecessor(76).getData());
assertEquals(new Integer(76), tree.sucessor(67).getData());
assertEquals(new Integer(23), tree.predecessor(67).getData());
assertEquals(null, tree.sucessor(232));
assertEquals(new Integer(76), tree.predecessor(232).getData());
}
@Test
public void testMinMax() {
tree.insert(6);
assertEquals(new Integer(6), tree.minimum().getData());
assertEquals(new Integer(6), tree.maximum().getData());
tree.insert(23);
assertEquals(new Integer(6), tree.minimum().getData());
assertEquals(new Integer(23), tree.maximum().getData());
tree.insert(-34);
assertEquals(new Integer(-34), tree.minimum().getData());
assertEquals(new Integer(23), tree.maximum().getData());
tree.insert(5);
assertEquals(new Integer(-34), tree.minimum().getData());
assertEquals(new Integer(23), tree.maximum().getData());
tree.insert(9);
assertEquals(new Integer(-34), tree.minimum().getData());
assertEquals(new Integer(23), tree.maximum().getData());
}
@Test
public void testSucessorPredecessor() {
fillTree(); // -40 -34 0 2 5 6 9 12 23 67 76 232
assertEquals(null, tree.predecessor(-40));
assertEquals(new Integer(-34), tree.sucessor(-40).getData());
assertEquals(new Integer(-40), tree.predecessor(-34).getData());
assertEquals(new Integer(0), tree.sucessor(-34).getData());
assertEquals(new Integer(-34), tree.predecessor(0).getData());
assertEquals(new Integer(2), tree.sucessor(0).getData());
assertEquals(new Integer(0), tree.predecessor(2).getData());
assertEquals(new Integer(5), tree.sucessor(2).getData());
}
@Test
public void testSize() {
fillTree(); // -40 -34 0 2 5 6 9 12 23 67 76 232
int size = 12;
assertEquals(size, tree.size());
while (!tree.isEmpty()) {
tree.remove(tree.getRoot().getData());
assertEquals(--size, tree.size());
}
}
@Test
public void equalsElementTest() {
assertEquals(-1, tree.height());
assertEquals(0, tree.size());
tree.insert(10);
assertEquals(0, tree.height());
assertEquals(1, tree.size());
tree.insert(9);
assertEquals(1, tree.height());
assertEquals(2, tree.size());
tree.insert(10);
assertEquals(1, tree.height());
assertEquals(2, tree.size());
tree.insert(9);
assertEquals(1, tree.height());
assertEquals(2, tree.size());
}
@Test
public void invalidInsert() {
tree.insert(null);
tree.insert(null);
// tree.remove(new Integer(null));
assertEquals(0, tree.size());
assertEquals(-1, tree.height());
assertEquals(null, tree.getRoot().getData());
assertEquals(null, tree.getRoot().getLeft());
assertEquals(null, tree.getRoot().getRight());
assertEquals(null, tree.maximum());
assertEquals(null, tree.minimum());
assertTrue(tree.isEmpty());
}
@Test
public void minimumMaximum() {
fillTree();// -40 -34 0 2 5 6 9 12 23 67 76 232
assertEquals(new Integer(-40), tree.minimum().getData());
assertEquals(new Integer(232), tree.maximum().getData());
tree.remove(-40);
tree.remove(232);
assertEquals(new Integer(-34), tree.minimum().getData());
assertEquals(new Integer(76), tree.maximum().getData());
tree.remove(-34);
tree.remove(76);
assertEquals(new Integer(0), tree.minimum().getData());
assertEquals(new Integer(67), tree.maximum().getData());
tree.remove(0);
tree.remove(67);
assertEquals(new Integer(2), tree.minimum().getData());
assertEquals(new Integer(23), tree.maximum().getData());
tree.remove(2);
tree.remove(23);
assertEquals(new Integer(5), tree.minimum().getData());
assertEquals(new Integer(12), tree.maximum().getData());
tree.remove(5);
tree.remove(12);
assertEquals(new Integer(6), tree.minimum().getData());
assertEquals(new Integer(9), tree.maximum().getData());
tree.remove(6);
tree.remove(9);
assertEquals(null, tree.minimum());
assertEquals(null, tree.maximum());
assertTrue(tree.isEmpty());
}
@Test
public void testHeight() {
fillTree(); // -40 -34 0 2 5 6 9 12 23 67 76 232
Integer[] preOrder = new Integer[] { 6, -34, -40, 5, 2, 0, 23, 9, 12,
76, 67, 232 };
assertArrayEquals(preOrder, tree.preOrder());
assertEquals(4, tree.height());
tree.remove(0);
assertEquals(3, tree.height());
tree.remove(2);
assertEquals(3, tree.height());
}
@Test
public void testRemove() {
fillTree(); // -40 -34 0 2 5 6 9 12 23 67 76 232
Integer[] order = { -40, -34, 0, 2, 5, 6, 9, 12, 23, 67, 76, 232 };
assertArrayEquals(order, tree.order());
tree.remove(6);
order = new Integer[] { -40, -34, 0, 2, 5, 9, 12, 23, 67, 76, 232 };
assertArrayEquals(order, tree.order());
tree.remove(9);
order = new Integer[] { -40, -34, 0, 2, 5, 12, 23, 67, 76, 232 };
assertArrayEquals(order, tree.order());
assertEquals(NIL, tree.search(6));
assertEquals(NIL, tree.search(9));
}
@Test
public void testSearch() {
fillTree(); // -40 -34 0 2 5 6 9 12 23 67 76 232
assertEquals(new Integer(-40), tree.search(-40).getData());
assertEquals(new Integer(-34), tree.search(-34).getData());
assertEquals(NIL, tree.search(2534));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment