Ronzii's Blog

Just your average geek's blog

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