Untitled

package Exercise3;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class CodeExercise3 {
    private static AVLTree avlTree = new AVLTree();
    private static RedBlackTree rbTree = new RedBlackTree();
    private static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        while (true) {
            System.out.println("Choose the tree type:");
            System.out.println("1. AVL Tree");
            System.out.println("2. Red-Black Tree");
            System.out.println("3. Exit");
            int choice = scanner.nextInt();
            switch (choice) {
                case 1:
                    avlTreeMenu();
                    break;
                case 2:
                    rbTreeMenu();
                    break;
                case 3:
                    scanner.close(); // Close scanner to release resources
                    System.exit(0);
                    break;
                default:
                    System.out.println("Invalid choice! Try again.");
            }
        }
    }

    private static void avlTreeMenu() {
        while (true) {
            System.out.println("\nAVL Tree Menu:");
            System.out.println("1. Insert");
            System.out.println("2. In-order Traversal");
            System.out.println("3. BFS Traversal");
            System.out.println("4. Back to Main Menu");
            int choice = scanner.nextInt();
            switch (choice) {
                case 1:
                    System.out.print("Enter values to insert (space-separated): ");
                    scanner.nextLine(); // Consume newline
                    String[] values = scanner.nextLine().split("\\s+");
                    for (String value : values) {
                        avlTree.insert(Integer.parseInt(value));
                    }
                    break;
                case 2:
                    System.out.println("In-order Traversal:");
                    avlTree.inOrder();
                    break;
                case 3:
                    System.out.println("BFS Traversal:");
                    avlTree.bfs();
                    break;
                case 4:
                    return;
                default:
                    System.out.println("Invalid choice! Try again.");
            }
        }
    }

    private static void rbTreeMenu() {
        while (true) {
            System.out.println("\nRed-Black Tree Menu:");
            System.out.println("1. Insert");
            System.out.println("2. In-order Traversal");
            System.out.println("3. BFS Traversal");
            System.out.println("4. Back to Main Menu");
            int choice = scanner.nextInt();
            switch (choice) {
                case 1:
                    System.out.print("Enter values to insert (space-separated): ");
                    scanner.nextLine(); // Consume newline
                    String[] values = scanner.nextLine().split("\\s+");
                    for (String value : values) {
                        rbTree.insert(Integer.parseInt(value));
                    }
                    break;
                case 2:
                    System.out.println("In-order Traversal (with color):");
                    rbTree.inOrder();
                    break;
                case 3:
                    System.out.println("BFS Traversal (with color):");
                    rbTree.bfs();
                    break;
                case 4:
                    return;
                default:
                    System.out.println("Invalid choice! Try again.");
            }
        }
    }
}

// AVL Tree Implementation
class AVLTree {
    class Node {
        int data, height;
        Node left, right;

        public Node(int data) {
            this.data = data;
            this.height = 1;
        }
    }

    private Node root;

    private int height(Node N) {
        return N == null ? 0 : N.height;
    }

    private Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;

        return x;
    }

    private Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        return y;
    }

    private int getBalance(Node N) {
        return N == null ? 0 : height(N.left) - height(N.right);
    }

    public void insert(int data) {
        root = insert(root, data);
    }

    private Node insert(Node node, int data) {
        if (node == null) {
            return new Node(data);
        }
        if (data < node.data) {
            node.left = insert(node.left, data);
        } else if (data > node.data) {
            node.right = insert(node.right, data);
        } else {
            return node;
        }

        node.height = Math.max(height(node.left), height(node.right)) + 1;

        int balance = getBalance(node);

        if (balance > 1 && data < node.left.data) {
            return rightRotate(node);
        }

        if (balance < -1 && data > node.right.data) {
            return leftRotate(node);
        }

        if (balance > 1 && data > node.left.data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        if (balance < -1 && data < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    public void inOrder() {
        inOrder(root);
        System.out.println();
    }

    private void inOrder(Node node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.data + " ");
            inOrder(node.right);
        }
    }

    public void bfs() {
        if (root == null) return;

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.data + " ");
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        System.out.println();
    }
}

// Red-Black Tree Implementation
class RedBlackTree {
    private final int RED = 0;
    private final int BLACK = 1;

    class Node {
        int data, color;
        Node left, right, parent;

        Node(int data) {
            this.data = data;
            this.color = RED;
        }
    }

    private Node root;

    private void leftRotate(Node node) {
        Node right = node.right;
        node.right = right.left;
        if (right.left != null)
            right.left.parent = node;

        right.parent = node.parent;
        if (node.parent == null)
            root = right;
        else if (node == node.parent.left)
            node.parent.left = right;
        else
            node.parent.right = right;

        right.left = node;
        node.parent = right;
    }

    private void rightRotate(Node node) {
        Node left = node.left;
        node.left = left.right;
        if (left.right != null)
            left.right.parent = node;

        left.parent = node.parent;
        if (node.parent == null)
            root = left;
        else if (node == node.parent.left)
            node.parent.left = left;
        else
            node.parent.right = left;

        left.right = node;
        node.parent = left;
    }

    public void insert(int data) {
        Node node = new Node(data);
        root = insertBST(root, node);
        fixViolation(node);
    }

    private Node insertBST(Node root, Node node) {
        if (root == null)
            return node;

        if (node.data < root.data) {
            root.left = insertBST(root.left, node);
            root.left.parent = root;
        } else if (node.data > root.data) {
            root.right = insertBST(root.right, node);
            root.right.parent = root;
        }

        return root;
    }

    private void fixViolation(Node node) {
        Node parent = null, grandParent = null;

        while (node != root && node.color == RED && node.parent.color == RED) {
            parent = node.parent;
            grandParent = parent.parent;

            if (parent == grandParent.left) {
                Node uncle = grandParent.right;

                if (uncle != null && uncle.color == RED) {
                    grandParent.color = RED;
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    node = grandParent;
                } else {
                    if (node == parent.right) {
                        leftRotate(parent);
                        node = parent;
                        parent = node.parent;
                    }
                    rightRotate(grandParent);
                    int temp = parent.color;
                    parent.color = grandParent.color;
                    grandParent.color = temp;
                    node = parent;
                }
            } else {
                Node uncle = grandParent.left;

                if (uncle != null && uncle.color == RED) {
                    grandParent.color = RED;
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    node = grandParent;
                } else {
                    if (node == parent.left) {
                        rightRotate(parent);
                        node = parent;
                        parent = node.parent;
                    }
                    leftRotate(grandParent);
                    int temp = parent.color;
                    parent.color = grandParent.color;
                    grandParent.color = temp;
                    node = parent;
                }
            }
        }

        root.color = BLACK;
    }

    public void inOrder() {
        inOrder(root);
        System.out.println();
    }

    private void inOrder(Node node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.data + (node.color == RED ? "(R) " : "(B) "));
            inOrder(node.right);
        }
    }

    public void bfs() {
        if (root == null) return;

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.data + (node.color == RED ? "(R) " : "(B) "));
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        System.out.println();
    }
}