DAA_Assignment

#include<bits/stdc++.h>
using namespace std;

// Defining node class

class Node {
    public:
    int X, Y;
    Node *left;
    Node *right;
    int height;
};

// Height calculation

int height(Node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}

//New node creation

Node* newNode(int X, int Y)
{
    Node* node = new Node();
    node->X = X;
    node->Y = Y;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return(node);
}

//Perform left rotation incase of leftt imbalance i.e. the height of the left subtree is more than the right subtree

Node *rightRotate(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;
}

//Perform left rotation incase of right imbalance i.e. the height of the right subtree is more than the left subtree

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

    y->left = x;
    x->right = T2;

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

    return y;
}

/*
Balancing Factor calculation
BF = Height of left subtree - Height of right subtree
Tree is said to be balnced incases where BF lies in the following set : {-1,0,1}
*/


int getBalance(Node *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

// Inserting new point as node while maintaining the balanced nature of the tree

Node* insert(Node* node, int X, int Y)
{
    if (node == NULL)
        return(newNode(X, Y));

    //Insertion based on x and y values

    if (Y < node->Y || Y == node->Y && X > node->X)
        node->left = insert(node->left, X, Y);
    else if (Y > node->Y)
        node->right = insert(node->right, X, Y);
    else
        return node;

    // Height recalculation

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

    //BF calculation

    int balance = getBalance(node);

    //Roations based on BF

    if (balance > 1 && (Y < node->left->Y || Y == node->left->Y && X > node->left->X))
        return rightRotate(node);

    if (balance < -1 && Y > node->right->Y)
        return leftRotate(node);

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

    if (balance < -1 && (Y < node->right->Y || Y == node->right->Y && X > node->right->X))
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

//Pre-order traversal of the tree

void preOrder(Node *root)
{
    if(root != NULL)
    {
        cout << root->X << " " << root->Y << endl;
        preOrder(root->left);
        preOrder(root->right);
    }
}

int main()
{
    Node *root = NULL;

    root = insert(root, 10, 1);
    root = insert(root, 20, 2);
    root = insert(root, 30, 3);
    root = insert(root, 40, 4);
    root = insert(root, 50, 3);
    root = insert(root, 25, 2);

    preOrder(root);

    return 0;
}