Ronzii's Blog

Just your average geek's blog

Spiral Order Traversal in a Tree

void iterativeSpiralTraversal(TreeNode* root)
{
    stack<TreeNode*> currentLevel, nextLevel;
    currentLevel.push(root);
    bool direction = 1;
    while(!currentLevel.empty())
    {
        TreeNode* current = currentLevel.top();
        currentLevel.pop();
        if(current)
        {
            cout<<current->value<<" ";
            if(direction)
            {
                if(current->left)
                    nextLevel.push(current->left);
                if(current->right)
                    nextLevel.push(current->right);
            }
            else
            {
                if(current->right)
                    nextLevel.push(current->right);
                if(current->left)
                    nextLevel.push(current->left);
            }
        }
        if(currentLevel.empty())
        {
            cout<<endl;
            swap(currentLevel,nextLevel);
            direction = !direction;
        }
    }
}

April 1, 2012 Posted by | C++, Data Structures | , , , , | 1 Comment

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

Rank Tree

A ranked binary tree is a binary tree whose nodes have integer ranks, with leaves having rank zero and missing nodes having rank minus one. If x is a child, the rank di erence of x, x, is the rank of its parent minus the rank of x. The rank of a ranked tree is the rank of its root.

The following code is for an unbalanced Rank Tree i.e has a worst case of O(n^2) for sorted input. The worst case can be avoided by balancing the nodes. Also, we would need to set left_sum every time a rotation occurs.

#include <iostream>
using namespace std;
struct node
{
    int value,left_size;
    struct node *left;
    struct node *right;
};
typedef struct node TreeNode;
TreeNode* createNode(int n)
{
    TreeNode *temp = new TreeNode();
    temp->value = n;
    temp->left_size = 0;
    return temp;
}
void add(TreeNode* &root, int n)
{
    if(root==NULL)
        root  = createNode(n);
    else if(n<root->value)
    {
        add(root->left,n);
        root->left_size++;
    }
    else
        add(root->right,n);
}
int getRank(TreeNode* root, int n)
{
    if(root->value==n)
        return root->left_size;
    else if(n<root->value)
    {
        if(root->left==NULL) return -1;
        else return getRank(root->left,n);
    }
    else
    {
        int right_rank = (root->right)?getRank(root->right,n):-1;
        if(right_rank==-1) return -1;
        return 1 + root->left_size + right_rank;
    }
}
int main()
{
    TreeNode* root = NULL;
    int a[] = {11,7,13,5,15};
    int size = sizeof(a)/sizeof(a[0]);
    for(int i=0; i<size; i++)
    {
        add(root,a[i]);
    }
    for(int i=0; i<size; i++)
    {
        cout<<getRank(root,a[i])<<" ";
    }
    return 0;
}

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

AVL Rotation Logic

We only need to calculate the balance factors and check for the following cases

Left Left

Left Right

Right Right

Right Left

March 28, 2012 Posted by | C++, Data Structures | , , , | 1 Comment

Treap

This algorithm performs well since a treap is a complete binary search tree
Algorithm

  1. Insert according to key(similar to BST insert)
  2. Rotate Clockwise/Anticlockwise according to the priority during insertion.

For more details see here.

#include<iostream>
using namespace std;
class Treap
{
    class Node
    {
    public:
        int key,priority;
        Node *left;
        Node *right;
    };
    Node* root;
    void clockwiseRotate(Node* &x)
    {
        Node* temp = x->left;
        x->left = temp->right;
        temp->right = x;
        x = temp;
    }
    void anticlockwiseRotate(Node* &x)
    {
        Node* temp = x->right;
        x->right = temp->left;
        temp->left = x;
        x = temp;
    }
    Node* createNode(int key, int priority)
    {
        Node* temp = new Node;
        temp->key = key;
        temp->priority = priority;
        temp->left = NULL;
        temp->right = NULL;
        return temp;
    }
    void balance(Node* &x)
    {
        if(x->left!=NULL && (x->left->priority> x->priority))
        {
            clockwiseRotate(x);
        }
        else if(x->right!=NULL && (x->right->priority> x->priority))
        {
            anticlockwiseRotate(x);
        }
    }
    void insert(Node* &current, int key, int priority)
    {
        if(current==NULL)
            current = createNode(key,priority);
        else if(current->key>key)
            insert(current->left,key,priority);
        else
            insert(current->right,key,priority);
        balance(current);
    }
    void print(Node* x)
    {
        if(x == NULL ) return;
        print(x->left);
        cout<<"("<<x->key<<","<< x->priority<<")"<<endl;
        print(x->right);
    }
    bool search(Node* x, int key)
    {
        if(x==NULL) return false;
        if(x->key==key) return true;
        if(key<x->key) return search(x->left,key);
        else return search(x->right,key);
    }
    void deleteNode(Node* &x,int key)
    {
        if(x == NULL ) return;
        if(key<x->key) deleteNode(x->left,key);
        else if (key>x->key) deleteNode(x->right,key);
        else
        {
            if( x->left== NULL && x->right == NULL) x = NULL;
            else if (x->left==NULL) x = x->right;
            else if (x->right==NULL) x = x->left;
            else
            {
                if (x->left->priority>x->right->priority) clockwiseRotate(x);
                else anticlockwiseRotate(x);
                deleteNode(x,key);
            }
        }
    }
public:
    Treap(int key, int priority)
    {
        root = createNode(key,priority);
    }
    void insert(int key, int priority)
    {
        insert(root,key,priority);
    }
    void print()
    {
        print(root);
    }
    void search(int key)
    {
        search(root,key);
    }
    void deleteNode(int key)
    {
        deleteNode(root,key);
    }
};
int main()
{
    Treap t(1,4);
    t.insert(7,3);
    t.insert(8,10);
    t.insert(12,1);
    t.print();
    t.deleteNode(7);
    t.deleteNode(1);
    t.print();
    return 0;
}

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

Generalized Voting

Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list.
The algorithm should run in linear time. (n >=0 )

You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don’t use standard linear time deterministic selection algo

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
void generalizedVoting(vector<int> v, int m)
{
    int n = v.size();
    unordered_map<int,int> h;
    unordered_map<int,int>::iterator iter;
    // Treat numbers as blocks of size m similar to the game tetris
    // There are n/m blocks of size m
    for(int i=0; i<n; i++)
    {
        iter = h.find(v[i]);
        if(iter!=h.end())
        {
            iter->second++;
        }
        else
            h.insert(pair<int,int>(v[i],1));
        if(h.size()==m)
        {
            unordered_map<int,int>::iterator iter = h.begin();
            while(iter!=h.end())
            {
                --(*iter).second;
                if((*iter).second == 0)
                    h.erase(iter++);
                else
                    iter++;
            }
        }
    }
    // Reset values in unordered map
    for(iter = h.begin(); iter!=h.end(); iter++)
    {
        iter->second = 0;
    }
    // find exact count of numbers present in unordered map
    for(int i=0; i<n; i++)
    {
        iter = h.find(v[i]);
        if(iter!=h.end())
            iter->second++;
    }
    // Remove numbers with frequency less than equal to n/m
    for(iter = h.begin(); iter!=h.end(); iter++)
    {
        if(iter->second<=n/m)
            h.erase(iter);
    }
    for(iter = h.begin(); iter!=h.end(); iter++)
    {
        cout<<iter->first<<" ";
    }
}
int main()
{
    //int arr[] = {5,6,7,8,10,10,10,10,10,10,4,4,4,4,4,1,1,1,1};
    int arr[] = {4,3,3,2,1,2,3,4,4,7};
    //int arr[] = {5,6,7,8,10,4,4,4,4,1,1,1};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector<int> v(arr,arr+n);
    int k = 4;
    generalizedVoting(v,k);
    return 0;
}

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

The Least K Numbers

We maintain a max heap of size k and keep inserting/deleting values according the largest value in the heap

#include <iostream>
#include <vector>
#include <set>
using namespace std;
void GetLeastNumbers(const vector<int>& data, multiset< int,greater<int> >& answer, int k)
{
    answer.clear();
    multiset<int, greater<int> >::iterator  leastIterator;
    for(vector<int>::const_iterator iter = data.begin(); iter!=data.end(); iter++)
    {
        if(answer.size()<k)
        {
            answer.insert(*iter);
        }
        else
        {
            leastIterator = answer.begin();
            if(*(answer.begin())>*iter)
            {
                answer.erase(leastIterator);
                answer.insert(*iter);
            }
        }
    }
}
int main()
{
    int a[] = {3,1,23,4,6,2,56,7};
    int size = sizeof(a)/sizeof(a[0]);
    vector<int> v(a,a+size);
    multiset< int,greater<int> > answer;
    int k = 4;
    GetLeastNumbers(v,answer,k);
    for(multiset<int, greater<int> >::iterator  x=answer.begin(); x!=answer.end(); x++)
    {
        cout<<*x<<" ";
    }
    return 0;
}

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