Ronzii's Blog

Just your average geek's blog

AVL Tree

Check out logic of AVL balancing here

#include<iostream>
using namespace std;
struct node
{
    int key;
    struct node *left;
    struct node *right;
    int height;
};
typedef struct node Node;
int height(Node *N)
{
    if (N == NULL)
        return 0;
    return N->height;
}

Node* newNode(int key)
{
    Node* node = new Node;
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return(node);
}
Node *rightRotate(Node *y)
{
    Node *x = y->left;
    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 x;
}
Node *leftRotate(Node *x)
{
    Node *y = x->right;
    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 y;
}
int getBalance(Node *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}
Node* insert(Node* node, int key)
{
    if (node == NULL)
        return(newNode(key));
    if (key < node->key)
        node->left  = insert(node->left, key);
    else
        node->right = insert(node->right, key);

    node->height = max(height(node->left), height(node->right)) + 1;
    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 node;
}
void preOrder(Node *root)
{
    if(root != NULL)
    {
        cout<<root->key<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}
int main()
{
    Node *root = NULL;
    root = insert(root, 15);
    root = insert(root, 22);
    root = insert(root, 35);
    root = insert(root, 45);
    root = insert(root, 55);
    root = insert(root, 30);

    /* The constructed AVL Tree would be
              35
             /  \
           22   45
          /  \     \
         15  30    55
    */
    preOrder(root);

    return 0;
}

March 30, 2012 Posted by | C++, Data Structures | , , , , | Leave a comment

Finding duplicates in O(n)

Input: Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times.

Goal : To find these repeating numbers in O(n) and using only constant memory space.

#include <iostream>
using namespace std;
void duplicates(int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        while(a[a[i]]!=a[i])
            swap(a[a[i]],a[i]);
    }
    for (int i = 0; i < n; i++)
        if (a[i] != i)
            cout<<a[i]<<" ";
}
int main()
{
    int x[] = {1, 2, 3, 1, 3, 0, 6};
    int n = sizeof x / sizeof x[0];
    duplicates(x, n);
    return 0;
}

March 30, 2012 Posted by | C++ | , , , , | Leave a comment

Ceiling and Floor Search

#include <iostream>
using namespace std;
int ceilSearch(int a[], int low, int high, int x)
{
    if(x<a[low]) return low;
    if(x>a[high]) return -1;
    int mid = (low+high)/2;
    if(a[mid]==x) return mid;
    /* If x is smaller than arr[mid], then either arr[mid]
    is ceiling of x or ceiling lies in arr[mid-1...high] */
    else if(x<a[mid])
    {
        if(x>=a[mid-1])
            return mid;
        else
            ceilSearch(a,low,mid-1,x);

    }
    /* If x is greater than arr[mid], then either arr[mid + 1]
        is ceiling of x or ceiling lies in arr[mid+1...high] */
    else
    {
        if(x<=a[mid+1])
            return mid+1;
        else
            ceilSearch(a,mid+1,high,x);

    }
}
int floorSearch(int a[], int low, int high, int x)
{
    if(x<a[low]) return -1;
    if(x>a[high]) return high;
    int mid = (low+high)/2;
    if(x==a[mid]) return mid;
    else if(x<a[mid])
    {
        if(x>=a[mid-1])
            return mid-1;
        else
            floorSearch(a,low,mid-1,x);
    }
    else
    {
        if(x<=a[mid+1])
            return mid;
        else
            floorSearch(a,mid+1,high,x);
    }
}
int main()
{
    int arr[] = {1, 2, 8, 10, 10, 12, 19};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x,index;
    while(1)
    {
        cin>>x;
        index = ceilSearch(arr, 0, n-1, x);
        if(index == -1)
            cout<<"Ceiling of "<<x<<" doesn't exist in array \n";
        else
            cout<<"Ceiling of "<<x<<" is "<<arr[index]<<endl;
        index = floorSearch(arr, 0, n-1, x);
        if(index == -1)
            cout<<"Floor of "<<x<<" doesn't exist in array \n";
        else
            cout<<"Floor of "<<x<<" is "<<arr[index]<<endl;

    }
    return 0;
}

March 30, 2012 Posted by | C++ | , , , , | Leave a comment

Random Number Generation

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
int rand5()
{
    return rand()%5;
}
int rand7()
{
    int vals[5][5] =
    {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}
int main()
{
    srand(time(NULL));
    cout<<rand7();
    return 0;
}

March 29, 2012 Posted by | C++ | , , , | Leave a comment

Shortest distance between 2 Integers


#include <iostream>
#include <climits>
using namespace std;
int dist(int a[],int n, int x, int y)
{
    int a1=-1,a2=-1, min_distance = INT_MAX;
    for(int i=0;i<n;i++)
    {
        if(a[i]==x)
        {
            a1 = i;
            int distance = a1-a2;
            if(a2>=0 && distance<min_distance)
            {
                min_distance = distance;
            }
        }
        else if(a[i]==y)
        {
            a2 = i;
            int distance = a2-a1;
            if(a1>=0 && distance<min_distance)
            {
                min_distance = distance;
            }
        }
    }
    return min_distance;
}
int main()
{
    int a[] = {6,5,5,5,1,2,4,4,6,6,3,4,3,4,1,2,4};
    int size= sizeof(a)/sizeof(a[0]);
    cout<<dist(a,size,1,6);
    return 0;
}

March 29, 2012 Posted by | C++ | , , , , | Leave a comment

Number to String

#include <iostream>
#include <cstring>
using namespace std;
string digits[] = {"one","two","three","four","five","six","seven","eight","nine"};
string teens[] = {"eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"};
string tens[] = {"ten","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"};
string bigs[] = {"","thousand","million"};
string numToString100(int n)
{
    string result = "";
    if(n>=100)
    {
        result+= digits[n/100-1] + " hundred ";
        n%=100;
    }
    if(n>=11 & n<=19)
    {
        result+= teens[n-11]+ " ";
    }
    else if(n==10 || n>=20)
    {
        result+= tens[n/10-1]+ " ";
        n%=10;
    }
    if(n>=1 && n<=9)
    {
        result += digits[n-1] + " ";
    }
    return result;
}
string numToString(int n)
{
    string result="";
    if(n==0)
    {
        return "zero";
    }
    else if(n<0)
    {
        result= "negative " + numToString(n*-1);
    }
    int count = 0;
    while(n>0)
    {
        if(n%1000!=0)
        {
            result = numToString100(n%1000) + bigs[count] + " " + result;
        }
        n/=1000;
        count++;
    }
    return result;
}

int main()
{
    cout<<numToString(-19323984);
    return 0;
}

March 29, 2012 Posted by | C++ | , , , | Leave a comment

Bit Set

#include <iostream>
using namespace std;
class BitSet
{
    int *bitset;
public:
    BitSet(int size)
    {
        bitset = new int[size>>5];
        for(int i=0; i<size>>5; i++)
        {
            bitset[i] = 0;
        }
    }
    bool get(int k)
    {
        return (bitset[k>>5] & (1<<(k&0x1F)))!=0;
    }
    void set(int k)
    {
        bitset[k>>5]|=1<<(k&0x1F);
    }
};
int main()
{
    BitSet s(100);
    int a[] = {1,5,1,7,8,3,7,8,7,2,67,9,54};
    int size = sizeof(a)/sizeof(a[0]);
    for(int i=0; i<size; i++)
    {
        if(s.get(a[i])) cout<<a[i]<<" ";
        else s.set(a[i]);
    }
    return 0;
}

March 29, 2012 Posted by | C++ | , , , , | Leave a comment