AVL tree and other homeworks

AVL Tree:

#include<stdio.h>
#include<stdlib.h>

// An AVL tree node
struct Node
{
    int key;
    struct Node *left;
    struct Node *right;
    int height;
};
int max(int a, int b);

// A utility function to get the height of the tree
int height(struct Node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}

// A utility function to get maximum of two integers
int max(int a, int b)
{
    return (a > b)? a : b;
}

/* Helper function that allocates a new node with the given key and
    NULL left and right pointers. */
struct Node* newNode(int key)
{
    struct Node* node = (struct Node*)
                        malloc(sizeof(struct Node));
    node->key   = key;
    node->left   = NULL;
    node->right  = NULL;
    node->height = 1;  // new node is initially added at leaf
    return(node);
}

// A utility function to right rotate subtree rooted with y
// See the diagram given above.
struct Node *rightRotate(struct Node *y)
{
    struct Node *x = y->left;
    struct Node *T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

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

    // Return new root
    return x;
}

// A utility function to left rotate subtree rooted with x
// See the diagram given above.
struct Node *leftRotate(struct Node *x)
{
    struct Node *y = x->right;
    struct Node *T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

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

    // Return new root
    return y;
}

// Get Balance factor of node N
int getBalance(struct Node *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

// Recursive function to insert a key in the subtree rooted
// with node and returns the new root of the subtree.
struct Node* insert(struct Node* node, int key)
{
    /* 1.  Perform the normal BST insertion */
    if (node == NULL)
        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 // Equal keys are not allowed in BST
        return node;

    /* 2. Update height of this ancestor node */
    node->height = 1 + max(height(node->left),
                           height(node->right));

    /* 3. Get the balance factor of this ancestor
          node to check whether this node became
          unbalanced */
    int balance = getBalance(node);

    // If this node becomes unbalanced, then
    // there are 4 cases

    // Left Left Case
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    // Right Right Case
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    // Left Right Case
    if (balance > 1 && key > node->left->key)
    {
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }

    // Right Left Case
    if (balance < -1 && key < node->right->key)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    /* return the (unchanged) node pointer */
    return node;
}

// A utility function to print preorder traversal
// of the tree.
// The function also prints height of every node
void preOrder(struct Node *root)
{
    if(root != NULL)
    {
        printf("%d ", root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}

/* Driver program to test above function*/
int main()
{
  struct Node *root = NULL;

  /* Constructing tree given in the above figure */
  root = insert(root, 10);
  root = insert(root, 20);
  root = insert(root, 30);
  root = insert(root, 40);
  root = insert(root, 50);
  root = insert(root, 25);

  preOrder(root);

  return 0;
}



Success #stdin #stdout 0s 9424KB

 comments (0)

 stdin

 copy




Standard input is empty




 stdout

 copy




30 20 10 25 40 50 

Splay tree:

#include<stdio.h> 
#include<stdlib.h> 
  
// An AVL tree node 
struct node 
{ 
    int key; 
    struct node *left, *right; 
}; 
struct node* newNode(int key) 
{ 
    struct node* node = (struct node*)malloc(sizeof(struct node)); 
    node->key   = key; 
    node->left  = node->right  = NULL; 
    return (node); 
} 
  
struct node *rightRotate(struct node *x) 
{ 
    struct node *y = x->left; 
    x->left = y->right; 
    y->right = x; 
    return y; 
} 
  
struct node *leftRotate(struct node *x) 
{ 
    struct node *y = x->right; 
    x->right = y->left; 
    y->left = x; 
    return y; 
} 
  
// This function brings the key at root if key is present in tree. 
// If key is not present, then it brings the last accessed item at 
// root.  This function modifies the tree and returns the new root 
struct node *splay(struct node *root, int key) 
{ 
    // Base cases: root is NULL or key is present at root 
    if (root == NULL || root->key == key) 
        return root; 
  
    // Key lies in left subtree 
    if (root->key > key) 
    { 
        // Key is not in tree, we are done 
        if (root->left == NULL) return root; 
  
        // Zig-Zig (Left Left) 
        if (root->left->key > key) 
        { 
            // First recursively bring the key as root of left-left 
            root->left->left = splay(root->left->left, key); 
  
            // Do first rotation for root, second rotation is done after else 
            root = rightRotate(root); 
        } 
        else if (root->left->key < key) // Zig-Zag (Left Right) 
        { 
            // First recursively bring the key as root of left-right 
            root->left->right = splay(root->left->right, key); 
  
            // Do first rotation for root->left 
            if (root->left->right != NULL) 
                root->left = leftRotate(root->left); 
        } 
  
        // Do second rotation for root 
        return (root->left == NULL)? root: rightRotate(root); 
    } 
    else // Key lies in right subtree 
    { 
        // Key is not in tree, we are done 
        if (root->right == NULL) return root; 
  
        // Zag-Zig (Right Left) 
        if (root->right->key > key) 
        { 
            // Bring the key as root of right-left 
            root->right->left = splay(root->right->left, key); 
  
            // Do first rotation for root->right 
            if (root->right->left != NULL) 
                root->right = rightRotate(root->right); 
        } 
        else if (root->right->key < key)// Zag-Zag (Right Right) 
        { 
            // Bring the key as root of right-right and do first rotation 
            root->right->right = splay(root->right->right, key); 
            root = leftRotate(root); 
        } 
  
        // Do second rotation for root 
        return (root->right == NULL)? root: leftRotate(root); 
    } 
} 
  
// The search function for Splay tree.  Note that this function 
// returns the new root of Splay Tree.  If key is present in tree 
// then, it is moved to root. 
struct node *search(struct node *root, int key) 
{ 
    return splay(root, key); 
} 
  
// A utility function to print preorder traversal of the tree. 
// The function also prints height of every node 
void preOrder(struct node *root) 
{ 
    if (root != NULL) 
    { 
        printf("%d ", root->key); 
        preOrder(root->left); 
        preOrder(root->right); 
    } 
} 
  
/* Driver program to test above function*/
int main() 
{ 
    struct node *root = newNode(100); 
    root->left = newNode(50); 
    root->right = newNode(200); 
    root->left->left = newNode(40); 
    root->left->left->left = newNode(30); 
    root->left->left->left->left = newNode(20); 
  
    root = search(root, 20); 
    printf("Preorder traversal of the modified Splay tree is \n"); 
    preOrder(root); 
    return 0; 
} 

Success #stdin #stdout 0s 9424KB
Preorder traversal of the modified Splay tree is 
20 50 30 40 100 200 


Queue using two stacks:


#include <stdio.h> 
#include <stdlib.h> 
  
typedef struct sNode { 
    int data; 
    struct sNode* next; 
}stack; 
void push(stack** top_ref, int new_data); 
int pop(stack** top_ref); 
  
/* structure of queue having two stacks */
struct queue { 
    stack* stack1; 
    stack* stack2; 
}; 
void enQueue(struct queue* q, int x) 
{ 
    push(&q->stack1, x); //& refers to the value in the address
} 
int deQueue(struct queue* q) 
{ 
    int x; 
  
    /* If both stacks are empty then error */
    if (q->stack1 == NULL && q->stack2 == NULL) { 
        printf("Q is empty"); 
        getchar(); 
        exit(0); 
    } 
  
    /* Move elements from stack1 to stack 2 only if 
       stack2 is empty */
    if (q->stack2 == NULL) { 
        while (q->stack1 != NULL) { 
            x = pop(&q->stack1); 
            push(&q->stack2, x); 
        } 
    } 
  
    x = pop(&q->stack2); 
    return x; 
} 
  
/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data) 
{ 
    /* allocate node */
    struct sNode* new_node = (struct sNode*)malloc(sizeof(struct sNode)); 
    if (new_node == NULL) { 
        printf("Stack overflow \n"); 
        getchar(); 
        exit(0); 
    } 
  
    /* put in the data */
    new_node->data = new_data; 
  
    /* link the old list off the new node */
    new_node->next = (*top_ref); 
  
    /* move the head to point to the new node */
    (*top_ref) = new_node; 
} 
  
/* Function to pop an item from stack*/
int pop(struct sNode** top_ref) 
{ 
    int res; 
    struct sNode* top; 
  
    /*If stack is empty then error */
    if (*top_ref == NULL) { 
        printf("Stack underflow \n"); 
        getchar(); 
        exit(0); 
    } 
    else { 
        top = *top_ref; 
        res = top->data; 
        *top_ref = top->next; 
        free(top); 
        return res; 
    } 
} 
  
/* Driver program*/
int main() 
{ 
    struct queue* q = (struct queue*)malloc(sizeof(struct queue)); 
    q->stack1 = NULL; 
    q->stack2 = NULL; 
    enQueue(q, 1); 
    enQueue(q, 2); 
    enQueue(q, 3); 
  
    printf("%d ", deQueue(q)); 
    printf("%d ", deQueue(q)); 
    printf("%d ", deQueue(q)); 
  
    return 0; 
} 




 stdout


 copy






1 2 3 







#include<stdio.h> 



#include<stdlib.h> 






struct node 



{ 



int key; 



struct node *left, *right; 



}; 






// A utility function to create a new BST node 



struct node *newNode(int item) 



{ 



struct node *temp =  (struct node *)malloc(sizeof(struct node)); 



temp->key = item; 



temp->left = temp->right = NULL; 



return temp; 



} 






// A utility function to do inorder traversal of BST 



void inorder(struct node *root) 



{ 



if (root != NULL) 



{ 



inorder(root->left); 



printf("%d ", root->key); 



inorder(root->right); 



} 



} 






/* A utility function to insert a new node with given key in BST */



struct node* insert(struct node* node, int key) 



{ 



/* If the tree is empty, return a new node */



if (node == NULL) return newNode(key); 






/* Otherwise, recur down the tree */



if (key < node->key) 



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



else



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






/* return the (unchanged) node pointer */



return node; 



} 









struct node * minValueNode(struct node* node) 



{ 



struct node* current = node; 






/* loop down to find the leftmost leaf */



while (current->left != NULL) 



current = current->left; 






return current; 



} 









struct node* deleteNode(struct node* root, int key) 



{ 



// base case 



if (root == NULL) return root; 






// If the key to be deleted is smaller than the root's key, 



// then it lies in left subtree 



if (key < root->key) 



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






// If the key to be deleted is greater than the root's key, 



// then it lies in right subtree 



else if (key > root->key) 



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






// if key is same as root's key, then This is the node 



// to be deleted 



else



{ 



// node with only one child or no child 



if (root->left == NULL) 



{ 



struct node *temp = root->right; 



free(root); 



return temp; 



} 



else if (root->right == NULL) 



{ 



struct node *temp = root->left; 



free(root); 



return temp; 



} 






// node with two children: Get the inorder successor (smallest 



// in the right subtree) 



struct node* temp = minValueNode(root->right); 






// Copy the inorder successor's content to this node 



root->key = temp->key; 






// Delete the inorder successor 



root->right = deleteNode(root->right, temp->key); 



} 



return root; 



} 






// Driver Program to test above functions 



int main() 



{ 






struct node *root = NULL; 



root = insert(root, 50); 



root = insert(root, 30); 



root = insert(root, 20); 



root = insert(root, 40); 



root = insert(root, 70); 



root = insert(root, 60); 



root = insert(root, 80); 






printf("Inorder traversal of the given tree \n"); 



inorder(root); 






printf("\nDelete 20\n"); 



root = deleteNode(root, 20); 



printf("Inorder traversal of the modified tree \n"); 



inorder(root); 






printf("\nDelete 30\n"); 



root = deleteNode(root, 30); 



printf("Inorder traversal of the modified tree \n"); 



inorder(root); 






printf("\nDelete 50\n"); 



root = deleteNode(root, 50); 



printf("Inorder traversal of the modified tree \n"); 



inorder(root); 






return 0; 



} 









Success #stdin #stdout 0s 9424KB


 comments (0)


 stdin



 copy

Standard input is empty



 stdout



 copy


Inorder traversal of the given tree 
20 30 40 50 60 70 80 
Delete 20
Inorder traversal of the modified tree 
30 40 50 60 70 80 
Delete 30
Inorder traversal of the modified tree 
40 50 60 70 80 
Delete 50
Inorder traversal of the modified tree 
40 60 70 80 

These codes are not written by the site owner. To complete the data structure portion, these are mentioned here. Feel free to contact for any details regarding this.