Untitled
Lab3package 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(); } }
Leave a Comment