F2024266263

ZARAN HAIDER
PROJECT:DATA STRUCTURES AND ALGORITHMS
RESOURCE PERSON : ARIFAH AZHAR

CODE
#include <iostream>
#include <string>

using namespace std;

class Node {
public:
int rollNo;
string name;
float cgpa;
Node* left;
Node* right;
int height;
Node(int r, string n, float c) {
 rollNo = r;
name = n;
cgpa = c;
left = nullptr;
right = nullptr;
height = 0;
}
};

struct QueueNode {
Node* treeNode;
QueueNode* next;
};

class Queue {
QueueNode* front;
QueueNode* rear;
public:
Queue() { front = rear = nullptr; }
bool isEmpty() { return front == nullptr; }
void enqueue(Node* n) {
QueueNode* temp = new QueueNode{n, nullptr};
 if (rear == nullptr) {
front = rear = temp;
return;
}
rear->next = temp;
rear = temp;
}
Node* dequeue() {
if (isEmpty()) return nullptr;
QueueNode* temp = front;
Node* res = front->treeNode;
front = front->next;
if (front == nullptr) rear = nullptr;
delete temp;
return res;
}
};

struct StackNode {
Node* treeNode;
StackNode* next;
};
class Stack {
StackNode* topNode;
public:
Stack() { topNode = nullptr; }
bool isEmpty() { return topNode == nullptr; }
void push(Node* n) {
StackNode* temp = new StackNode{n, topNode};
topNode = temp;
}
Node* pop() {
if (isEmpty()) return nullptr;
StackNode* temp = topNode;
Node* res = topNode->treeNode;
topNode = topNode->next;
delete temp;
return res;
}
};

class AVLTree {
private:
Node* root;
int llCount;
int rrCount;
int lrCount;
int rlCount;

int max(int a, int b) {

return (a > b) ? a : b;
}

int getHeight(Node* n) {
if (n == nullptr) return -1;
return n->height;
}

int getBalanceFactor(Node* n) {
if (n == nullptr) return 0;
return getHeight(n->left) - getHeight(n->right);
}

void updateHeight(Node* n) {
if (n != nullptr) {
 n->height = 1 + max(getHeight(n->left), getHeight(n->right));
}
}

Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
updateHeight(y);
updateHeight(x);
return x;
}

Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
updateHeight(x);
updateHeight(y);
return y;
}

Node* balanceNode(Node* node) {

updateHeight(node);
int bf = getBalanceFactor(node);

if (bf > 1 && getBalanceFactor(node->left) >= 0) {

llCount++;
return rightRotate(node);
}
if (bf < -1 && getBalanceFactor(node->right) <= 0) {
rrCount++;
return leftRotate(node);
}
if (bf > 1 && getBalanceFactor(node->left) < 0) {
lrCount++;
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (bf < -1 && getBalanceFactor(node->right) > 0) {
rlCount++;
node->right = rightRotate(node->right);
 return leftRotate(node);
}
return node;
}

Node* insert(Node* node, int rollNo, string name, float cgpa) {

if (node == nullptr) {
return new Node(rollNo, name, cgpa);
}
if (rollNo < node->rollNo) {
node->left = insert(node->left, rollNo, name, cgpa);
} else if (rollNo > node->rollNo) {
node->right = insert(node->right, rollNo, name, cgpa);
} else {
return node;
}
return balanceNode(node);
}

Node* search(Node* root, int rollNo) {

if (root == nullptr || root->rollNo == rollNo) {
return root;
 }
if (rollNo < root->rollNo) {
return search(root->left, rollNo);
}
return search(root->right, rollNo);
}

Node* deleteNode(Node* root, int rollNo) {

if (root == nullptr) return root;

if (rollNo < root->rollNo) {

root->left = deleteNode(root->left, rollNo);
} else if (rollNo > root->rollNo) {
root->right = deleteNode(root->right, rollNo);
} else {
if ((root->left == nullptr) || (root->right == nullptr)) {
Node* temp = root->left ? root->left : root->right;
if (temp == nullptr) {
temp = root;
root = nullptr;
} else {
*root = *temp;
 }
delete temp;
} else {
Node* temp = findMinNode(root->right);
root->rollNo = temp->rollNo;
root->name = temp->name;
root->cgpa = temp->cgpa;
root->right = deleteNode(root->right, temp->rollNo);
}
}
if (root == nullptr) return root;
return balanceNode(root);
}

void displayInorder(Node* root) {

if (root != nullptr) {
displayInorder(root->left);
cout << root->rollNo << " ";
displayInorder(root->right);
}
}
void displayPreorder(Node* root) {
if (root != nullptr) {
cout << root->rollNo << " ";
displayPreorder(root->left);
displayPreorder(root->right);
}
}

void displayPostorder(Node* root) {

if (root != nullptr) {
displayPostorder(root->left);
displayPostorder(root->right);
cout << root->rollNo << " ";
}
}

void printBalanceFactors(Node* root) {

if (root != nullptr) {
cout << root->rollNo << " -> " << getBalanceFactor(root) << endl;
printBalanceFactors(root->left);
printBalanceFactors(root->right);
}
 }

void printTree(Node* root, int space, int height) {

if (root == nullptr) return;
space += height;
printTree(root->right, space, height);
cout << endl;
for (int i = height; i < space; i++) cout << " ";
cout << root->rollNo << "\n";
printTree(root->left, space, height);
}

public:
AVLTree() {
root = nullptr;
llCount = 0;
rrCount = 0;
lrCount = 0;
rlCount = 0;
}

void insertRecord(int r, string n, float c) {

 root = insert(root, r, n, c);
}

void deleteRecord(int r) {
root = deleteNode(root, r);
}

void searchRecord(int r) {
Node* found = search(root, r);
if (found) cout << "Record Found\nRoll Number: " << found->rollNo
<< "\nName: " << found->name << "\nCGPA: " << found->cgpa << endl;
else cout << "Record Not Found\n";
}

Node* smartSearch(int rollNo) {

if (root == nullptr) return nullptr;
Node* curr = root;
Node* parent = nullptr;
while (curr != nullptr) {
if (curr->rollNo == rollNo) {
return curr;
}
 parent = curr;
if (rollNo < curr->rollNo) {
curr = curr->left;
} else {
curr = curr->right;
}
}
return parent;
}

Node* findMinNode(Node* node) {

Node* current = node;
while (current && current->left != nullptr) {
current = current->left;
}
return current;
}

Node* getMinNode() { return findMinNode(root); }

int findMinValue() {
Node* minNode = findMinNode(root);
 if (minNode != nullptr) return minNode->rollNo;
return -1;
}

Node* findMaxNode(Node* node) {

Node* current = node;
while (current && current->right != nullptr) {
current = current->right;
}
return current;
}

Node* getMaxNode() { return findMaxNode(root); }

int findMaxValue() {
Node* maxNode = findMaxNode(root);
if (maxNode != nullptr) return maxNode->rollNo;
return -1;
}

int getTreeHeight() { return getHeight(root); }

void showInorder() { displayInorder(root); cout << endl; }
void showPreorder() { displayPreorder(root); cout << endl; }
void showPostorder() { displayPostorder(root); cout << endl; }

void displayLevelOrder() {
if (root == nullptr) return;
Queue q;
[Link](root);
int level = 0;
while (![Link]()) {
int nodeCount = 0;
Queue tempQ;
while (![Link]()) {
Node* n = [Link]();
[Link](n);
nodeCount++;
}
cout << "Level " << level << " : ";
while (![Link]()) {
Node* n = [Link]();
cout << n->rollNo << " ";
if (n->left != nullptr) [Link](n->left);
 if (n->right != nullptr) [Link](n->right);
}
cout << endl;
level++;
}
}

void DFS() {
if (root == nullptr) return;
Stack s;
[Link](root);
while (![Link]()) {
Node* curr = [Link]();
cout << curr->rollNo << " ";
if (curr->right != nullptr) [Link](curr->right);
if (curr->left != nullptr) [Link](curr->left);
}
cout << endl;
}

void showBalanceFactors() { printBalanceFactors(root); }

void showTree() { printTree(root, 0, 6); }
 void printExitStats() {
cout << "There were " << llCount << " LL Rotations\n";
cout << "There were " << rrCount << " RR Rotations\n";
cout << "There were " << lrCount << " LR Rotations\n";
cout << "There were " << rlCount << " RL Rotations\n";
cout << "Height of tree: " << getTreeHeight() << endl;
cout << "Minimum Value: " << findMinValue() << endl;
cout << "Maximum Value: " << findMaxValue() << endl;
showTree();
}
};

int main() {
AVLTree tree;
int choice;

while (true) {
cout << "\nMenu:\n1. Insert\n2. Search\n3. Smart Search\n4.
Delete\n5. Traversals\n6. Level Order\n7. DFS\n8. Find Min\n9. Find
Max\n10. Balance Factors\n11. Print Tree\n12. Exit\nSelection: ";
cin >> choice;
if (choice == 12) {
[Link]();
break;
}

if (choice == 1) {
int r; string n; float c;
cin >> r >> n >> c;
[Link](r, n, c);
cout << "Current Tree Height: " << [Link]() << endl;
}
else if (choice == 2) {
int r; cin >> r;
[Link](r);
}
else if (choice == 3) {
int r; cin >> r;
Node* res = [Link](r);
if (res) cout << "Result Roll: " << res->rollNo << endl;
}
else if (choice == 4) {
int r; cin >> r;
 [Link](r);
cout << "Current Tree Height: " << [Link]() << endl;
}
else if (choice == 5) {
int sub; cin >> sub;
if (sub == 1) [Link]();
else if (sub == 2) [Link]();
else if (sub == 3) [Link]();
}
else if (choice == 6) {
[Link]();
}
else if (choice == 7) {
[Link]();
}
else if (choice == 8) {
int sub; cin >> sub;
if (sub == 1) cout << [Link]() << endl;
else cout << [Link]() << endl;
}
else if (choice == 9) {
int sub; cin >> sub;
 if (sub == 1) cout << [Link]() << endl;
else cout << [Link]() << endl;
}
else if (choice == 10) {
[Link]();
}
else if (choice == 11) {
[Link]();
}
}
return 0;
}