22F-3575 - Emaan Mahdi - Lab No 10

2024
DATA LAB 10
EMAAN MAHDI
22F-3575
BS (CS) | 4-B
TASK NO 1:
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node* left;
Node* right;
int height;
Node(int val) : data(val), left(nullptr), right(nullptr), height(1) {}
};
int max(int a, int b)

{
return (a > b) ? a : b;
}
int height(Node* node)
{
if (node == nullptr)
return 0;
return node->height;
}
int balanceFactor(Node* node)
{
return 0;
return height(node->left) - height(node->right);
}
Node* RotateRight(Node* y)
{
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;

x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
Node* RotateLeft(Node* x)
{
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;

return y;
}
Node* insert(Node* node, int val)
{
{
return new Node(val);
}
if (val < node->data)
{
node->left = insert(node->left, val);
}
else if (val > node->data)
{
node->right = insert(node->right, val);
}
else
return node;
node->height = 1 + max(height(node->left), height(node->right));
int bf = balanceFactor(node);
if (bf > 1 && val < node->left->data)

{
return RotateRight(node);
}
if (bf < -1 && val > node->right->data)
{
return RotateLeft(node);
}
if (bf > 1 && val > node->left->data)
{
node->left = RotateLeft(node->left);
return RotateRight(node);
}
if (bf < -1 && val < node->right->data)
{
node->right = RotateRight(node->right);
return RotateLeft(node);
}
return node;
}
bool isAVL(Node* node)
{
return true;
int bf = balanceFactor(node);
if (abs(bf) <= 1 && isAVL(node->left) && isAVL(node->right))

return true;
return false;
}
bool search(Node* node, int val)
{
return false;
if (val == node->data)
return true;
if (val < node->data)

return search(node->left, val);
return search(node->right, val);

}
int findMin(Node* node)
{
return -1;
while (node->left != nullptr)

node = node->left;
return node->data;
}
int find2ndMin(Node* node)
{
return -1;
if (node->left == nullptr && node->right == nullptr)

return -1;
if (node->left != nullptr && node->right == nullptr)

return findMin(node->left);
if (node->left != nullptr && node->right != nullptr)

return findMin(node->right);
return -1;
}
void printInorder(Node* node)
{
return;
printInorder(node->left);
cout << node->data << " ";
printInorder(node->right);
}
void printPreorder(Node* node)
{
return;

printPreorder(node->left);
printPreorder(node->right);
}
void printPostorder(Node* node)
{
return;
printPostorder(node->left);
printPostorder(node->right);
}
int main()
{
Node* root = nullptr;
root = insert(root, 10);

cout << "Inorder traversal: ";

printInorder(root);
cout << endl;
cout << "Preorder traversal: ";

printPreorder(root);
cout << endl;
cout << "Postorder traversal: ";

printPostorder(root);
cout << endl;
cout << "is AVL " << isAVL(root) << endl;
cout << "Search 25: " << search(root, 25) << endl;
cout << "Min " << findMin(root) << endl;
cout << "2nd Min " << find2ndMin(root) << endl;
system("pause");
return 0;
}
TASK NO 2:
#include <iostream>
using namespace std;
struct Node {
int key;
int height;
Node* left;
Node* right;
};
Node* newNode(int key) {
Node* node = new Node();
node->key = key;
node->height = 1;
node->left = node->right = nullptr;
return node;
}
int height(Node* node) {
return 0;
return node->height;
}
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;

return x;
}
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
return y;
}
int getBalance(Node* node) {
return 0;
return height(node->left) - height(node->right);
}
Node* insert(Node* node, int key) {
return newNode(key);
if (key < node->key)

node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node;
node->height = 1 + max(
int balance = getBalance(node);
if (balance > 1 && key < node->left->key)
return rightRotate(node);
if (balance < -1 && key > node->right->key)
return leftRotate(node);
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void inorder(Node* node) {
return;
inorder(node->left);
cout << node->key << " ";
inorder(node->right);
}
int main()
{
Node* root = nullptr;
inorder(root);
return 0;
}

22F-3575 - Emaan Mahdi - Lab No 10

Uploaded by

Copyright:

Available Formats

22F-3575 - Emaan Mahdi - Lab No 10

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

22F-3575 - Emaan Mahdi - Lab No 10

Uploaded by

Copyright:

Available Formats

2024

int max(int a, int b)

y->height = max(height(y->left), height(y->right)) + 1;

x->height = max(height(x->left), height(x->right)) + 1;

node->height = 1 + max(height(node->left), height(node->right));

if (bf > 1 && val < node->left->data)

if (abs(bf) <= 1 && isAVL(node->left) && isAVL(node->right))

if (val < node->data)

return search(node->right, val);

while (node->left != nullptr)

if (node->left == nullptr && node->right == nullptr)

if (node->left != nullptr && node->right == nullptr)

if (node->left != nullptr && node->right != nullptr)

cout << node->data << " ";

root = insert(root, 10);

cout << "Inorder traversal: ";

cout << "Preorder traversal: ";

cout << "Postorder traversal: ";

cout << "is AVL " << isAVL(root) << endl;

cout << "Min " << findMin(root) << endl;

cout << "2nd Min " << find2ndMin(root) << endl;

y->height = max(height(y->left), height(y->right)) + 1;

if (key < node->key)

You might also like