Rotate_left and Rotate_right functions for a treap
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Thread: Rotate_left and Rotate_right functions for a treap

  1. #1
    Join Date
    May 2013
    Posts
    1

    Question Rotate_left and Rotate_right functions for a treap

    Hi I have the following code for a treap but I don't know how to make roate_left and rotate_right functions to balance it. I need some explanations and some code. Thanks

    Code:
    #include<iostream>
    #include<utility>
    #include<stdlib.h>
    #include<time.h>
    #include<stdio.h>
    using namespace std;
    template<typename T> class Treap{
        public:
            unsigned int priority;
            Treap<T> *root, *left, *right, *parent;
            T *pinfo;
            
    
            Treap()
            {
                priority = rand();
                left = right = NULL;
                root = this;
                pinfo = NULL;
            }
    
            void insert(T x)
            {
                 if (pinfo == NULL)
                {
                    pinfo = new T;
                    *pinfo = x;
                }
                else
                {
                    if (x<=*pinfo){
                        if (left == NULL){
                            left = new Treap<T>;
                            left->pinfo = new T;
                            *(left->pinfo) = x;
                            //balance(left);
                            left->left = left->right = NULL;
                            left->parent = this;
                            left->root = root;
                        }
                    else
                        left->insert(x);
                    }
                    else{
                        if (right == NULL)
                        {
                            right = new Treap<T>;
                            right->pinfo = new T;
                            *(right->pinfo) = x;
                            //balance(right);
                            right->left = right->right = NULL;
                            right->parent = this;
                            right->root = root;
                        }
                        else
                            right->insert(x);
                    }
                }
            }
    
            Treap<T>* find(T x)
            {
                Treap<T> *rez;
    
                if (pinfo == NULL)
                    return NULL;
    
                if ((*pinfo) == x)
                    return this;
    
                if (x <= (*pinfo))
                {
                    if (left != NULL)
                        return left->find(x);
                    else
                        return NULL;
                }
                else
                {
                    if (right != NULL)
                        return right->find(x);
                    else
                        return NULL;
                }
            }
    
            void inOrderTraversal()
            {
                if (left != NULL)
                    left->inOrderTraversal();
    
                //std::cout<<pinfo->first<<" "<<pinfo->second<<std::endl;
                cout<<*pinfo<<" ";
                if (right != NULL)
                    right->inOrderTraversal();
            }
    };
    
    int main()
    {
        srand(23424);
        Treap<int> *r = new Treap<int>;
        r->insert(2);
        r->insert(5);
        r->insert(7);
        r->insert(1);
        r->insert(9);
        r->inOrderTraversal();
        return 0;
    }

  2. #2
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,854

    Re: Rotate_left and Rotate_right functions for a treap

    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center