Back to Repositories

Validating Splay Tree Operations in williamfiset/Algorithms

This test suite validates the functionality of a Splay Tree implementation, focusing on core operations like insertion, deletion, and searching. The tests ensure proper splaying behavior and compare the implementation against Java’s built-in PriorityQueue for consistency verification.

Test Coverage Overview

The test suite provides comprehensive coverage of Splay Tree operations:

Root node validation after insertions
Combined insert-delete-search operations
Maximum element finding functionality
Consistency verification against PriorityQueue
Edge cases using Integer.MAX_VALUE/MIN_VALUE boundaries

Implementation Analysis

The testing approach employs JUnit Jupiter framework with Google Truth assertions for enhanced readability and precise verification. Random data generation utilities ensure diverse test scenarios, while structured test methods isolate specific functionality for targeted validation.

Technical Details

Testing tools and configuration:

JUnit Jupiter test framework
Google Truth assertion library
TestUtils for random data generation
Custom MIN/MAX constants for boundary testing
Integration with Java Collections framework for comparison testing

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Isolated test methods for specific functionality
Comprehensive edge case coverage
Comparative testing against standard library implementations
Consistent assertion patterns
Clear test method naming conventions

williamfiset/algorithms

src/test/java/com/williamfiset/algorithms/datastructures/binarysearchtree/SplayTreeTest.java

            
package com.williamfiset.algorithms.datastructures.binarysearchtree;

import static com.google.common.truth.Truth.assertThat;

import com.williamfiset.algorithms.datastructures.utils.TestUtils;
import java.util.*;
import org.junit.jupiter.api.Test;

public class SplayTreeTest {

  public static final int MAX = Integer.MAX_VALUE / 4, MIN = Integer.MIN_VALUE / 4;

  @Test
  public void getRoot() {
    SplayTree<Integer> splayTree = new SplayTree<>();
    List<Integer> data = TestUtils.randomIntegerList(100, MIN, MAX);
    for (int i : data) {
      splayTree.insert(i);
      assertThat(splayTree.getRoot().getData()).isEqualTo(i);
    }
  }

  @Test
  public void splayInsertDeleteSearch() {
    SplayTree<Integer> splayTree = new SplayTree<>();
    List<Integer> data =
        TestUtils.randomUniformUniqueIntegerList(
            100); // Note : we dont want duplicate values here to test "search" after "delete"
    // should assertNull
    for (int i : data) {
      splayTree.insert(i);
      assertThat(splayTree.getRoot().getData()).isEqualTo(i);
    }
    for (int i : data) {
      assertThat(splayTree.search(i)).isNotNull();
    }
    for (int i : data) {
      splayTree.delete(i);
      assertThat(splayTree.search(i)).isNull();
    }
  }

  @Test
  public void insertSearch() {
    SplayTree<Integer> splayTree = new SplayTree<>();
    List<Integer> data = TestUtils.randomIntegerList(100, MIN, MAX);
    for (int i : data) {
      splayTree.insert(i);
      assertThat(splayTree.getRoot().getData()).isEqualTo(i);
    }
  }

  @Test
  public void findMax() {
    SplayTree<Integer> splayTree = new SplayTree<>();
    List<Integer> data = TestUtils.sortedIntegerList(-50, 50);
    for (int i : data) {
      splayTree.insert(i);
      assertThat(splayTree.findMax(splayTree.getRoot())).isEqualTo(i);
    }
  }

  /** Comparison With Built In Priority Queue* */
  @Test
  public void splayTreePriorityQueueConsistencyTest() {
    SplayTree<Integer> splayTree = new SplayTree<>();
    List<Integer> data = TestUtils.randomUniformUniqueIntegerList(100);
    Queue<Integer> pq = new PriorityQueue<>(100, Collections.reverseOrder());

    // insertion
    for (int i : data) {
      assertThat(pq.add(i)).isEqualTo(splayTree.insert(i) != null);
    }
    // searching
    for (int i : data) {
      assertThat(splayTree.search(i).getData().equals(i)).isEqualTo(pq.contains(i));
    }
    // findMax & delete
    while (!pq.isEmpty()) {
      Integer splayTreeMax = splayTree.findMax();
      assertThat(pq.peek()).isEqualTo(splayTreeMax);

      splayTree.delete(splayTreeMax);
      assertThat(splayTree.search(splayTreeMax)).isNull();
      pq.remove(splayTreeMax);
      assertThat(pq.contains(splayTreeMax)).isFalse();
    }
  }
}