ASSIGNMENT 6:

PROBLEM 1: WRITE FUNCTIONS FOR INSERTION AND DELETION(OPTIONAL) FOR AN AVL TREE.

CODE:

#include<iostream>

#include<algorithm>

#include<stack>

using namespace std;

class Node

public:

int data;

int height;

Node* lchild;

Node* rchild;

};

class AVL

private:

Node* root;

public:

Node* insert(Node*p,int key);

int height(Node* p);

int balancefactor(Node* p);

Node* RRotation(Node* p);

Node* LRotation(Node* p);

Node* RL(Node* p);

Node* getRoot()

return root;

Node* LR(Node* p);

void inorder(Node* p);

void postorder(Node* p);

};

int AVL::height(Node* p)

if(p==NULL)

return 0;

return 1+max(height(p->lchild),height(p->rchild));

int AVL::balancefactor(Node* p)

return (height(p->lchild)-height(p->rchild));

Node* AVL::insert(Node* p,int key)

if(!p)

p=new Node;

p->data=key;

p->lchild=p->rchild=NULL;

p->height=0;

return p;

if(key<p->data)

p->lchild=insert(p->lchild,key);

else if(key>p->data)

p->rchild=insert(p->rchild,key);
 }

else

p->height=height(p);

if(balancefactor(p)==2&&balancefactor(p->lchild)==1)

return LRotation(p);

else if(balancefactor(p)==2&&balancefactor(p->lchild)==-1)

return LR(p);

else if(balancefactor(p)==-2&&balancefactor(p->rchild)==1)

return RL(p);

else if(balancefactor(p)==-2&&balancefactor(p->rchild)==-1)

return RRotation(p);

return p;

void AVL::inorder(Node* p)

stack<Node*> stk;

//Node* curr=p;

while(p||!(stk.empty()))

if(p)

stk.push(p);
 p=p->lchild;

else

p=stk.top();

stk.pop();

cout<<p->data<<" ";

p=p->rchild;

cout<<endl;

void AVL::preorder(Node* p)

stack<Node*> stk;

while(p||!stk.empty())

if(p)

cout<<p->data<<" ";

stk.push(p);

p=p->lchild;

else

p=stk.top();

stk.pop();

p=p->rchild;

}
 cout<<endl;

Node* AVL::RRotation(Node* p)

Node* pr=p->rchild;

Node* prl=pr->lchild;

p->rchild=prl;

pr->lchild=p;

p->height=1+max(height(p->rchild),height(p->lchild));

pr->height=1+max(height(pr->rchild),height(pr->lchild));

return pr;

Node* AVL::LRotation(Node* p)

Node* pl=p->lchild;

Node* plr=pl->rchild;

p->lchild=plr;

pl->rchild=p;

p->height=1+max(height(p->rchild),height(p->lchild));

pl->height=1+max(height(pl->rchild),height(pl->lchild));

return pl;

Node* AVL::LR(Node* p)

Node* pl=p->lchild;

Node* plr=pl->rchild;

p->lchild=plr->rchild;

pl->rchild=plr->lchild;

plr->rchild=p;

plr->lchild=pl;

plr->height=1+max(height(plr->rchild),height(plr->lchild));
 pl->height=1+max(height(pl->rchild),height(pl->lchild));

p->height=1+max(height(p->rchild),height(p->lchild));

return plr;

Node* AVL::RL(Node* p)

Node* pr=p->rchild;

Node* prl=pr->lchild;

pr->lchild=prl->rchild;

p->rchild=prl->lchild;

prl->rchild=pr;

prl->lchild=p;

prl->height=1+max(height(prl->rchild),height(prl->lchild));

pr->height=1+max(height(pr->rchild),height(pr->lchild));

p->height=1+max(height(p->rchild),height(p->lchild));

return prl;

int main()

AVL avl;

Node* rt=avl.getRoot();

rt=avl.insert(rt,10);

rt=avl.insert(rt,20);

rt=avl.insert(rt,12);

rt=avl.insert(rt,21);

rt=avl.insert(rt,54);

rt=avl.insert(rt,32);

rt=avl.insert(rt,224);

cout<<”Inorder : ”;

avl.inorder(rt);
 return 0;}

OUTPUT:

PROBLEM 2 : WRITE SIX OPERATIONS FOR SPLAYING AT A NODE IN A BST AND PERFORM SPLAYING
AT 3 NODES ONE AFTER ANOTHER.

CODE:

#include<iostream>

using namespace std;

class Node {

public:

int key;

Node* left;

Node* right;

};

Node* newNode(int key) {

Node* node = new Node();

node->key = key;

node->left = NULL;

node->right = NULL;

return node;

Node* insert(Node* root, int key) {

if (!root)

return newNode(key);
 if (key < root->key)

root->left = insert(root->left, key);

else if (key > root->key)

root->right = insert(root->right, key);

else

return root; // duplicate

return root;

Node* leftrotate(Node* p) {

Node* pl = p->left;

p->left = pl->right;

pl->right = p;

return pl;

Node* rightrotate(Node* p) {

Node* pr = p->right;

p->right = pr->left;

pr->left = p;

return pr;

Node* splay(Node* root, int key) {

if (!root || root->key == key)

return root;

if (root->key > key) {

if (!root->left)
 return root;

if (root->left->key > key) {

root->left->left = splay(root->left->left, key);

root = leftrotate(root);

} else if (root->left->key < key) {

root->left->right = splay(root->left->right, key);

if (root->left->right)

root->left = rightrotate(root->left);

return (root->left == NULL) ? root : leftrotate(root);

} else {

if (!root->right)

return root;

if (root->right->key > key) {

root->right->left = splay(root->right->left, key);

if (root->right->left)

root->right = leftrotate(root->right);

} else if (root->right->key < key) {

root->right->right = splay(root->right->right, key);

root = rightrotate(root);

return (root->right == NULL) ? root : rightrotate(root);

void preorder(Node* root) {

if (root) {
 cout << root->key << " ";

preorder(root->left);

preorder(root->right);

int main() {

Node* root = NULL;

root = insert(root, 10);

root = insert(root, 20);

root = insert(root, 30);

root = insert(root, 15);

root = insert(root, 19);

root = insert(root, 25);

root = insert(root, 50);

cout << "Inorder: ";

preorder(root);

cout << endl;

int k=3;

int i=0;

while(i<k)

cout << "Enter the node to splay: ";

int N;

cin >> N;

cout << "Preorder After splaying at " << N << ": ";

root = splay(root, N);

preorder(root);

cout << endl;

return 0;

OUTPUT: