aud.test.BinarySearchTreeTest Class Reference

Public Member Functions
void	testBinarySearchTree ()

Static Public Member Functions
static void	main (String args[])

Detailed Description

Definition at line 9 of file BinarySearchTreeTest.java.

Member Function Documentation

main()

static void aud.test.BinarySearchTreeTest.main ( String  args[] )

static

Definition at line 88 of file BinarySearchTreeTest.java.

                                         {
    org.junit.runner.JUnitCore.main("aud.test.BinarySearchTreeTest");
  }

testBinarySearchTree()

void aud.test.BinarySearchTreeTest.testBinarySearchTree

(

)

Definition at line 12 of file BinarySearchTreeTest.java.

                                     {
    String[] keys={"a","b","c","d","e","f"};
    int      n=keys.length;
 
    /* Includes most general case for removal:
 
       remove b of
 
             b
            / \
           a   e
              /
             c
              \
               d
 
        More entries are possible. However note that we are
        going to check *all* permutatiations for insertions,
        and for each one *all* permutatiations for removal!
        This yields O(n!*n!) iterations each of cost O(n*log n)!
     */
 
    BinarySearchTree<String,String> tree=new BinarySearchTree<String,String>();
 
    for (int[] p : new Permutations(n)) {
      for (int[] q : new Permutations(n)) {
        for (int i : p) {
          String k=tree.find(keys[i]);
          assertEquals(k,null);
          tree.insert(keys[i],keys[i]);
          k=tree.find(keys[i]);
          assertTrue(k!=null);
          assertTrue(k.compareTo(keys[i])==0);
          tree.checkConsistency();
        }
 
        assertTrue(tree.getMinimum().getValue().compareTo(keys[0])==0);
        assertTrue(tree.getMaximum().getValue().compareTo(keys[n-1])==0);
 
        {
          int i=0;
          for (BinarySearchTree<String,String>.Cursor c : tree) {
            assertTrue(c.getKey().compareTo(keys[i])==0);
            assertTrue(c.getValue().compareTo(keys[i])==0);
            ++i;
          }
          i=0;
          for (BinarySearchTree<String,String>.Cursor c : tree.range(null,null)) {
            assertTrue(c.getKey().compareTo(keys[i])==0);
            assertTrue(c.getValue().compareTo(keys[i])==0);
            ++i;
          }
          i=1;
          for (BinarySearchTree<String,String>.Cursor c :
                 tree.range(keys[1],keys[4])) {
            assertTrue(c.getKey().compareTo(keys[i])==0);
            assertTrue(c.getValue().compareTo(keys[i])==0);
            ++i;
          }
          assertSame(i,4);
        }
 
        for (int i : q) {
          String k=tree.find(keys[i]);
          assertTrue(k!=null);
          assertTrue(k.compareTo(keys[i])==0);
          tree.remove(keys[i]);
          k=tree.find(keys[i]);
          assertEquals(k,null);
          tree.checkConsistency();
        }
      }
      assertTrue(tree.isEmpty());
    }
  }

---

The documentation for this class was generated from the following file:

• BinarySearchTreeTest.java