RedBlackTreeTest.java

package collection;

import static org.junit.jupiter.api.Assertions.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

import org.junit.jupiter.api.*;

public class RedBlackTreeTest {
  @Test
  void addContainsRemove() {
    RedBlackTree<Integer> t = new RedBlackTree<>();
    assertTrue(t.add(5));
    assertTrue(t.contains(5));
    assertFalse(t.add(5)); // no duplicates
    assertTrue(t.add(3));
    assertTrue(t.add(7));
    assertEquals(3, t.size());
    assertTrue(t.remove(3));
    assertFalse(t.contains(3));
    assertEquals(2, t.size());
  }

  @Test
  void inOrderTraversalIsSorted() {
    RedBlackTree<Integer> t = new RedBlackTree<>();
    List<Integer> vals = Arrays.asList(5, 2, 8, 1, 3, 7, 9);
    Collections.shuffle(vals, new Random(42));
    t.addAll(vals);
    int prev = Integer.MIN_VALUE;
    for (Integer v : t) {
      assertTrue(v > prev);
      prev = v;
    }
  }

  @Test
  void largeRandomInsertions() {
    RedBlackTree<Integer> t = new RedBlackTree<>();
    int n = 10000;
    Random rnd = new Random(123);
    List<Integer> arr = new ArrayList<>();
    for (int i = 0; i < n; i++)
      arr.add(i);
    Collections.shuffle(arr, rnd);
    for (int x : arr)
      t.add(x);
    assertEquals(n, t.size());
    for (int i = 0; i < n; i++)
      assertTrue(t.contains(i));
  }
}