Cum se fac rotirile unui treap?

Intrebari despre limbajul C++, standardul C++, STL, OOP in C++ sau alte subiecte nelegate de VisualC++
Post Reply
alex_sailor
Junior
Junior
Posts: 1
Joined: 23 May 2013, 09:55
Judet: Bucureşti

Cum se fac rotirile unui treap?

Post by alex_sailor » 23 May 2013, 10:07

Salut. Am implementat urmatorul treap dar nu reusesc sa fac functiile de rotire. Am facut functiile de inserare, cautare si parcurgere in ordine. Deocamdata fara functiile alea de rotire ce am facut eu e doar un arbore binar de cautare. Daca ma puteti ajuta v-as fi recunoscator. Multumesc

Code: Select all

#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;
}



User avatar
Marius Bancila
Fondator
Fondator
Posts: 2344
Joined: 11 Jul 2007, 11:45
Judet: Timiş
Location: Timisoara
Contact:

Re: Cum se fac rotirile unui treap?

Post by Marius Bancila » 27 May 2013, 10:27

Uite aici sunt explicatii cu exemple si implementare http://opendatastructures.org/ods-java/ ... inary.html.
Marius Bancila
Fondator Codexpert, Microsoft MVP VC++
Site personal | Blog

Post Reply