RedBlackTreeMapTestClass

RedBlackTreeMapTestClass.java

package lab4;

import lab4.rbtree.RedBlackTreeMap;
import java.util.List;
import java.util.Random;
import java.util.function.Consumer;

/**
 * Тестовий клас для демонстрації функціональності червоно-чорного дерева
 */
public class Task10 {
    
    public static void main(String[] args) {
        // Тестуємо основні операції
        testBasicOperations();
        
        // Тестуємо видалення елементів
        testDeletion();
        
        // Тестуємо дерево з цілими числами
        testIntegerTree();
        
        // Тестуємо продуктивність
        testPerformance();
    }
    
    /**
     * Тестування основних операцій: put, get, containsKey, size
     */
    private static void testBasicOperations() {
        System.out.println("=== Тестування основних операцій ===");
        
        // Створюємо нове дерево зі String ключами та Integer значеннями
        RedBlackTreeMap<String, Integer> tree = new RedBlackTreeMap<>();
        
        // Перевіряємо, що дерево порожнє
        System.out.println("Дерево порожнє: " + tree.isEmpty());
        System.out.println("Розмір дерева: " + tree.size());
        
        // Додаємо елементи
        System.out.println("\nДодаємо елементи:");
        tree.put("A", 1);
        tree.put("B", 2);
        tree.put("C", 3);
        tree.put("D", 4);
        tree.put("E", 5);
        
        // Виводимо структуру дерева
        tree.printTree();
        
        // Перевіряємо розмір після додавання
        System.out.println("\nРозмір дерева після додавання: " + tree.size());
        
        // Отримуємо значення за ключами
        System.out.println("\nОтримуємо значення за ключами:");
        System.out.println("Значення для ключа 'A': " + tree.get("A"));
        System.out.println("Значення для ключа 'C': " + tree.get("C"));
        System.out.println("Значення для ключа 'Z' (не існує): " + tree.get("Z"));
        
        // Перевіряємо наявність ключів
        System.out.println("\nПеревіряємо наявність ключів:");
        System.out.println("Ключ 'B' існує: " + tree.containsKey("B"));
        System.out.println("Ключ 'X' існує: " + tree.containsKey("X"));
        
        // Оновлюємо значення існуючого ключа
        System.out.println("\nОновлюємо значення для ключа 'D':");
        Integer oldValue = tree.put("D", 44);
        System.out.println("Старе значення: " + oldValue + ", Нове значення: " + tree.get("D"));
        
        // Виводимо всі ключі
        List<String> keys = tree.keys();
        System.out.println("\nВсі ключі (в порядку зростання): " + keys);
        
        // Очищаємо дерево
        System.out.println("\nОчищаємо дерево");
        tree.clear();
        System.out.println("Дерево порожнє: " + tree.isEmpty());
    }
    
    /**
     * Тестування операції видалення
     */
    private static void testDeletion() {
        System.out.println("\n=== Тестування операції видалення ===");
        
        RedBlackTreeMap<Character, String> tree = new RedBlackTreeMap<>();
        
        // Додаємо елементи
        tree.put('A', "Alpha");
        tree.put('B', "Beta");
        tree.put('C', "Gamma");
        tree.put('D', "Delta");
        tree.put('E', "Epsilon");
        tree.put('F', "Phi");
        
        System.out.println("Початкове дерево:");
        tree.printTree();
        
        // Видаляємо листовий вузол
        System.out.println("\nВидаляємо листовий вузол 'F':");
        tree.remove('F');
        tree.printTree();
        
        // Видаляємо вузол з одним дочірнім
        System.out.println("\nВидаляємо вузол 'E' (може мати одного дочірнього):");
        tree.remove('E');
        tree.printTree();
        
        // Видаляємо вузол з двома дочірніми
        System.out.println("\nВидаляємо вузол 'B' (може мати двох дочірніх):");
        tree.remove('B');
        tree.printTree();
        
        // Видаляємо корінь
        System.out.println("\nВидаляємо корінь:");
        tree.remove(tree.keys().get(0));
        tree.printTree();
        
        // Перевіряємо розмір
        System.out.println("\nРозмір дерева після видалень: " + tree.size());
    }
    
    /**
     * Тестування дерева з числовими ключами
     */
    private static void testIntegerTree() {
        System.out.println("\n=== Тестування дерева з числовими ключами ===");
        
        RedBlackTreeMap<Integer, String> tree = new RedBlackTreeMap<>();
        
        // Додаємо елементи в зростаючому порядку
        System.out.println("Додаємо елементи в зростаючому порядку (1-10):");
        for (int i = 1; i <= 10; i++) {
            tree.put(i, "Value-" + i);
        }
        
        tree.printTree();
        
        // Додаємо елементи в спадаючому порядку
        System.out.println("\nДодаємо елементи в спадаючому порядку (20-11):");
        for (int i = 20; i > 10; i--) {
            tree.put(i, "Value-" + i);
        }
        
        tree.printTree();
        
        // Видаляємо елементи
        System.out.println("\nВидаляємо елементи 5, 15, 20:");
        tree.remove(5);
        tree.remove(15);
        tree.remove(20);
        
        tree.printTree();
    }
    
    /**
     * Тестування продуктивності
     */
    private static void testPerformance() {
        System.out.println("\n=== Тестування продуктивності ===");
        
        final int COUNT = 10000;
        RedBlackTreeMap<Integer, Integer> tree = new RedBlackTreeMap<>();
        
        // Генератор випадкових чисел
        Random random = new Random(42); // Фіксуємо seed для повторюваності
        
        // Додавання елементів
        System.out.println("Додавання " + COUNT + " елементів...");
        measureTime(() -> {
            for (int i = 0; i < COUNT; i++) {
                int key = random.nextInt(COUNT * 10);
                tree.put(key, i);
            }
        });
        
        // Пошук елементів
        System.out.println("Пошук " + COUNT + " елементів...");
        measureTime(() -> {
            for (int i = 0; i < COUNT; i++) {
                int key = random.nextInt(COUNT * 10);
                tree.get(key);
            }
        });
        
        // Видалення елементів
        System.out.println("Видалення " + COUNT / 2 + " елементів...");
        measureTime(() -> {
            for (int i = 0; i < COUNT / 2; i++) {
                int key = random.nextInt(COUNT * 10);
                tree.remove(key);
            }
        });
        
        System.out.println("Кінцевий розмір дерева: " + tree.size());
    }
    
    /**
     * Вимірює час виконання операції
     */
    private static void measureTime(Runnable operation) {
        long startTime = System.currentTimeMillis();
        operation.run();
        long endTime = System.currentTimeMillis();
        System.out.println("Час виконання: " + (endTime - startTime) + " мс");
    }
}