Help with red black tree

This is a discussion on Help with red black tree within the C++ Programming forums, part of the General Programming Boards category; Hi! My friend gave me a solution for red black tree, but in fuction rn_insere he uses a lot of ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    1

    Help with red black tree

    Hi! My friend gave me a solution for red black tree, but in fuction rn_insere he uses a lot of returns and for me (a noob in C ^^) is very difficult to understand... Can someone give me the same solution for only this function without these returns? Thank u (the file is here with all the code)!!!

    //nivel is level, tio is uncle, pai is father, esquerda is left, direita is right

    #include<iostream>
    using namespace std;

    void rotacao_esquerda(struct arvore_no **praiz);
    void rotacao_direita(struct arvore_no **praiz);
    void rn_insere_no(struct arvore_no **praiz,int valor);
    int rn_insere(struct arvore_no **praiz, int valor);
    struct arvore_no **direito(struct arvore_no **praiz);
    void imprimir(struct arvore_no *raiz);

    struct arvore_no
    {
    int valor;
    struct arvore_no *esquerda, *direita;
    int cor;
    };

    int nivel = 0;

    int main(void)
    {
    struct arvore_no *raiz, *temp1, **temp2;
    char rn;
    int nivel = 0, valor;

    raiz = NULL;

    while(!feof(stdin))
    {
    cin >> valor;
    if(rn_insere(&raiz, valor) != -1)
    {
    (raiz)->cor = 0;
    }
    }

    imprimir(raiz);

    while(raiz != NULL)
    {
    &(raiz)->esquerda;
    &(raiz)->direita;
    if(&raiz != NULL)
    {
    temp1 = raiz;
    raiz = (raiz)->esquerda;
    temp2 = direito(&raiz);
    *temp2 = temp1->direita;
    free(temp1);

    return(1);
    }
    else
    {
    return(0);
    }
    }

    return 0;
    }

    void rotacao_direita(struct arvore_no **praiz)
    {
    struct arvore_no *temp;
    temp = *praiz;
    (*praiz) = (*praiz)->esquerda;
    temp->esquerda = (*praiz)->direita;
    (*praiz)->direita = temp;
    }

    void rotacao_esquerda(struct arvore_no **praiz)
    {
    struct arvore_no *temp;
    temp = *praiz;
    (*praiz) = (*praiz)->direita;
    temp->direita = (*praiz)->esquerda;
    (*praiz)->esquerda = temp;
    }

    void rn_insere_no(struct arvore_no **praiz,int valor)
    {
    struct arvore_no *temp;
    temp = (struct arvore_no*) malloc(sizeof(struct arvore_no));
    temp->valor = valor;
    temp->direita = NULL;
    temp->esquerda = NULL;
    temp->cor = 1;
    *praiz = temp;
    }

    int rn_insere(struct arvore_no **praiz, int valor)
    {
    struct arvore_no **pai, **tio;
    int alavanca1, alavanca2;

    if(*praiz == NULL)
    {
    rn_insere_no(praiz, valor);
    return(3);
    }
    if(*praiz != NULL)
    {
    if(valor == (*praiz)->valor)
    {
    return(-1);
    }

    if(valor < (*praiz)->valor)
    {
    alavanca1 = rn_insere(&((*praiz)->esquerda), valor);
    alavanca2 = 1;
    }
    if(valor > (*praiz)->valor)
    {
    alavanca1 = rn_insere(&((*praiz)->direita), valor);
    alavanca2 = 2;
    }

    if(alavanca1 <= 0)
    {
    return(alavanca1);
    }
    if(alavanca1 == 3)
    {
    if((*praiz)->cor == 1)
    {
    return(alavanca2);
    }
    else
    {
    return(0);
    }
    }

    if(alavanca2 == 1)
    {
    tio = &((*praiz)->direita);
    pai = &((*praiz)->esquerda);
    }
    else
    {
    tio = &((*praiz)->esquerda);
    pai = &((*praiz)->direita);
    }

    if((*tio != NULL) && ((*tio)->cor == 1))
    {
    (*praiz)->cor = 1;
    (*pai)->cor = 0;
    (*tio)->cor = 0;
    return(3);
    }
    else
    {
    if(alavanca2 == 1)
    {
    if(alavanca1 == 2)
    {
    rotacao_esquerda(pai);
    }
    rotacao_direita(praiz);
    (*praiz)->direita->cor = 1;
    (*praiz)->cor = 0;
    return(0);
    }
    if(alavanca2 == 2)
    {
    if(alavanca1 == 1)
    {
    rotacao_direita(pai);
    }
    rotacao_esquerda(praiz);
    (*praiz)->esquerda->cor = 1;
    (*praiz)->cor = 0;
    return(0);
    }
    }
    }
    }

    struct arvore_no **direito(struct arvore_no **praiz)
    {
    struct arvore_no **p;
    p = praiz;
    while((*p) != NULL)
    {
    p = &(*p)->direita;
    }

    return(p);
    }

    void imprimir(struct arvore_no *raiz)
    {
    char rn;
    if(raiz != NULL)
    {
    imprimir(raiz->esquerda);
    nivel += 1;
    if(raiz->cor == 0)
    {
    rn = 'N';
    }
    if(raiz->cor != 0)
    {
    rn = 'R';
    }
    cout << raiz->valor << " " << rn << endl;
    imprimir(raiz->direita);
    nivel += 1;
    }
    }

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    //nivel is level, tio is uncle, pai is father, esquerda is left, direita is right
    A simple search and replace of your code would be better than having us learn some foreign words (no matter what quantity). English is the language of programming.

    Also it would be better if you posted your code in "[CODE ]" tags (of course without the space) so it is nicely formatted.

    Code:
    Can someone give me the same solution for only this function without these returns?
    If a function has to "return" a value, without using explicit "return" statement, the only other way is to modify a global variable(s) or pass the arguments by reference. They all achieve the same thing. If you are beginner or not, dont be worried or scared off by "return" statements--they are everywhere and if you want to program youll have to understand its concept. Its really not difficult, maybe youre just thinking it is.

    I imagine you understand how to simply use "return" to return a value, versus using references or global variables to exchange information between functions. If you must convert this to a program which doesnt return values, then give it an attempt and post your code. If you have problems give us all of the details and we can help.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    If it's hard for you to understand, just imagine how much harder it is for us to understand due to you not using [code][/code] tags to preserve the indentation, and it being in a foreign language to most of us!

    I'd feel somewhat arrogant using the same wording that nadroj used, but there is some truth that C++ does have entirely English keywords, and you have posted on an English forum. So I agree that doing a search-and-replace would be in your best interests.

    Many of those functions will need to return values and so most of the return statements are probably unaviodable. Perhaps a better idea would be to learn how they work. To what end can we help you understand what a return statement does?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. I need some ideas please>>
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 08-23-2002, 01:55 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21