Thread: How do I find and show the "uncle" of an element And How do I show the depth of a cer

title: How do I find and show the "uncle" of an element
And How do I show the depth of a certain element of the tree


Hello, I have an avl tree and I'm trying to make two functions. The first is to show the "uncle" of an element and the second is to show the depth of an element, for example: element = 3

4
/ \
2 6
/ \ / \
1 3 5 7

showing 4, 2 and 3. Here is the code it's still unfinished

esq = left
dir = right
pai = root
altura = height


arvoreperfume.h:

Code:

#ifndef _Perfume_Arvore_H
#define _Perfume_Arvore_H

struct PERFUME
{
    struct PERFUME *esq; 
    struct PERFUME *dir; 
    int cod; 
    char nome[30];
    float preco;
    int altura; 
    int depth;
};

typedef struct PERFUME Perfume;
typedef struct PERFUME * Perfume_ptr;

Perfume_ptr inserir(Perfume_ptr pai, int c, char n[30], float p);
#endif

arvoreperfumeMain.c:

Code:

#include "arvoreperfume.h"
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h>
#include <conio.h>

int main()
{
	int existe;
	Perfume_ptr pai=NULL;
	int opcao = 1; 
	int entrada = 0;
	char nomep[30];
	int altura;
	float precop;
	char temp[30];

	while(opcao!=0)
	{
	        system("color Fc");//primeiro digito muda o fundo, o segundo muda a cor do texto
	          printf(" ________________________\n");
	          printf("|________________________|\n\n\n\n");
	          printf("=====>Menu<=====\n");
	          printf("________________\n");
	          printf("1-->Inserir\n");
	          printf("6-->Mostrar tio");
                        printf("7-->Mostrar caminho");
	          printf("0-->Sair        \n");
	          printf("________________\n");   
	          printf("Opcao:");
               scanf("%d%*c", &opcao); //*c é pra não deixar um enter no buffer
               system("cls");

		switch(opcao)
		{
			case 1:{
				    printf("\nDigite o codigo: "); 
				    scanf ("%d*c", &entrada);

				    printf("digite o nome: ");
				    scanf ("%s*c", &nomep);
				
				    printf("digite o preco: ");
				    scanf ("%f*c", &precop);
                    system("cls");
				    pai = inserir(pai, entrada, nomep, precop);
				    break;
                   }
                   
            case 6:{ 
                    printf("\nDigite o codigo: ");
                    scanf ("%d*c", &entrada);
                    //function here
                    break;       
                   }
            case 7:{ 
                    printf("\nDigite o codigo: ");
                    scanf ("%d*c", &entrada);
                    //function here
                    break;
                   }           	
		}	
	}
	getchar();
	return 0;
}

arvoreperfume.c:

Code:

#include "arvoreperfume.h"
#include <stdlib.h>
#include <stdio.h> 
#include <string.h>

int altura (Perfume_ptr P) {
            if(P == NULL)
                return -1;
            else
                return P->altura;
}

int Max (int Lhs, int Rhs){
            return Lhs > Rhs ? Lhs : Rhs;
}

Perfume_ptr RotacaoSimplesEsquerda( Perfume_ptr K2 ) {
            Perfume_ptr K1;

            K1 = K2->esq;
            K2->esq = K1->dir;
            K1->dir = K2;

            K2->altura = Max( altura( K2->esq ), altura( K2->dir ) ) + 1;
            K1->altura = Max( altura( K1->esq ), K2->altura ) + 1;

            return K1;  /* New root */
        }
        
Perfume_ptr RotacaoSimplesDireita( Perfume_ptr K1 ) {
            Perfume_ptr K2;

            K2 = K1->dir;
            K1->dir = K2->esq;
            K2->esq = K1;

            K1->altura = Max( altura( K1->esq ), altura( K1->dir ) ) + 1;
            K2->altura = Max( altura( K2->esq ), K1->altura ) + 1;

            return K2;  /* New root */
        } 
        
Perfume_ptr RotacaoDuplaEsquerda( Perfume_ptr K3 ) {
            /* Rotate between K1 and K2 */
            K3->esq = RotacaoSimplesDireita( K3->esq );

            /* Rotate between K3 and K2 */
            return RotacaoSimplesEsquerda( K3 );
        }   
        
Perfume_ptr RotacaoDuplaDireita( Perfume_ptr K1 ) {
            /* Rotate between K3 and K2 */
            K1->dir = RotacaoSimplesEsquerda( K1->dir );

            /* Rotate between K1 and K2 */
            return RotacaoSimplesDireita( K1 );
        }  

Perfume_ptr inserir(Perfume_ptr pai, int c, char n[30], float p)
{
	if (pai)
	{
		if (c < (pai) -> cod)
		{
			pai->esq = inserir(((pai)->esq), c, n, p);
              if (altura (pai->esq) - altura (pai->dir) == 2)
                if (c < (pai)->dir->cod)
                  (pai) = RotacaoSimplesEsquerda (pai);
                else
                  (pai) = RotacaoDuplaEsquerda (pai);
		}
		else 
		if (c > (pai) -> cod)
		{
			pai->dir = inserir(((pai)->dir), c, n, p);
			  if (altura (pai->dir) - altura (pai->esq) == 2)
			    if (c > pai->dir->cod)
                  (pai) = RotacaoSimplesDireita (pai);
                else 
                  (pai) = RotacaoDuplaDireita (pai);     
		}
	}
	else 
	{ 
		pai = (Perfume_ptr)malloc(sizeof (PERFUME));
		if (pai)
		{ 
			(pai) -> cod = c; 
			strcpy((pai) -> nome, n);
			(pai) -> preco = p;
			(pai) -> esq = NULL; 
			(pai) -> dir = NULL;
		}
		else
		{
			printf("Nao foi possivel alocar memoria!\n");
		}
	}
    (pai)->altura = Max (altura(pai->esq), altura(pai->dir)) +1;
	return pai;
}
Perfume_ptr
grandparent(Perfume_ptr pai)
{
        if ((pai != NULL) && (pai->cod != NULL))
                return pai->cod->cod;
        else
                return NULL;
}
 
Perfume_ptr
uncle(Perfume_ptr pai)
{
        Perfume_ptr g = grandparent(pai);
        if (g == NULL)
                return NULL; 
        if (pai->cod == g->esq)
                return g->dir;
        else
                return g->esq;
}

Perfume_ptr
avl_tree_subtract_depth(Perfume_ptr pai)
{
	if(pai == NULL) {
		return NULL;
	}

	pai->depth--;

	avl_tree_subtract_depth(pai->esq);
	avl_tree_subtract_depth(pai->dir);
}

Perfume_ptr
avl_tree_add_depth(Perfume_ptr pai)
{
	if (pai == NULL) {
		return NULL;
	}

	pai->depth++;

	avl_tree_add_depth(pai->esq);
	avl_tree_add_depth(pai->dir);
}

Add a struct PERFUME *pai; to your struct PERFUME. Make sure it always points to the current node's parent/father. Set it when you insert a node, and update it when you delete a node or rotate some part of your tree. When you do this, finding the uncle should be easy, since your uncle is just your father's brother, or your father's father's other child. Follow the parent link up to your grandfather, then down to the left child. If that's the same as your father, then your uncle must be your grandfather's right child. Otherwise, it must be your grandfather's left child.

Once you add this parent link, it will be much easier to find the height of the node. I think you can figure this out yourself.

Note: You can do this without a link back to the father node, but the code is much more complicated, and involves traversing the tree.

aduril462: thanks!

quzah: ok, and to print the depth?
example: 4,5,6,1,2

thanks

arvoreperfume.c:

Code:

int depthfind(Perfume_ptr pai, int c, int tofind )
{
    int rval = -1;
    if( pai )
    {
        if( pai->cod == tofind )
            rval = c;
        if( rval == -1 )
            rval = depthfind( pai->esq, c+1, tofind );
        if( rval == -1 )
            rval = depthfind( pai->dir, c+1, tofind );
    }
    return rval;
    printf("caminho:", rval);
}

arvoreperfume.h:

Code:

int depthfind(Perfume_ptr pai, int c, int tofind );

arvoreperfumeMain.c:

Code:

int main()...
int depth;
...

case 7:{ 
                    printf("\nDigite o codigo: ");
                    scanf ("%d*c", &entrada);
                    depth = depthfind(pai, 0, 3 );
                    break;
                   }

sorry!

Code:

printf("caminho:", rval);
return rval;

entrada is the value that the user enters to show the depth

still does not work =/

Thank you and sorry I'll read

anduril462:
I tried to do as you said but did not work.

Look:

arvore.h:

Code:

struct PERFUME
{
    struct PERFUME *esq; 
    struct PERFUME *dir; 
    struct PERFUME *pai;    int cod; 
    char nome[30];
    float preco;
    int altura; 
};

arvore.c:

Code:

Perfume_ptr 
RotacaoSimplesEsquerda(Perfume_ptr K2)
{
            Perfume_ptr K1, K3;

            K1 = K2->esq;
            
            K3 = K1->pai;
            K1->pai = K2->pai;
            K2->pai = K3;            
            K2->esq = K1->dir;
            K1->dir = K2;

            K2->altura = Max( altura(K2->esq), altura(K2->dir )) + 1;
            K1->altura = Max( altura(K1->esq), K2->altura) + 1;
            
            return K1;  /*Nova raiz*/  
}
        
Perfume_ptr 
RotacaoSimplesDireita(Perfume_ptr K1) 
{
            Perfume_ptr K2, K3;

            K2 = K1->dir;
            
            K3 = K2->pai;
            K2->pai = K1->pai;
            K1->pai = K3;            
            K1->dir = K2->esq;
            K2->esq = K1;

            K1->altura = Max( altura(K1->esq), altura(K1->dir)) + 1;
            K2->altura = Max( altura(K2->dir), K1->altura) + 1;

            return K2;  /*Nova raiz*/           
}

Some code comments would help you explain what you're doing, and if you make them in English then I can see what you're doing too, since I don't speak Portuguese . Those look like rotate functions. Just looking at Esquerda, you're improperly setting K3 (it should be set to K2->pai), and K2->pai should be K1, not K3. Also, I think you're incorrectly using K2 in your K1->altura statement. Lastly, you need to change K3's child pointer to point to K1. To do this, you need to know if K2 was the left or right child of K3. You probably have similar issues with your Direita function.

I recommend you read up on tree rotation, and draw some diagrams on paper with nodes and pointer arrows. Make sure your diagrams include one generation above where you're rotating (parents), and two generations below (children and grandchildren). Then write out the steps in plain Portuguese, and lastly translate that to code.

EDIT: And like Quzah said, check for NULL pointers. Not just the one he pointed out, but everywhere it could be a problem.

Your rotate functions are still incomplete. If you look at the attached diagram, the node, parent, child and grandchild all have pointers to be adjusted. All in all, you need to change 6 pointers, but your code is only changing 4.



Study the attached diagram, paying attention to how the pointers (arrows) between nodes change. node is the one passed into your function. parent, child and grandchild are local variables. Set them up first, then make the following 6 changes. Hopefully it translates well.

1. Set parent's appropriate child link (left or right) to child
2. Set child's parent link to parent
3. Set node's parent link to child
4. Set child's right link to node
5. Set node's left link to grandchild (it's okay if grandchild is NULL)
6. If there is a grandchild, set grandchild's parent link to node

The left rotation is very similar, but a mirror image of this. Draw out a diagram for that, and figure out which instances of right and left pointers need to be swapped. For the double rotations, read the tutorial Andrew linked you to, and read the Wikipedia article on AVL trees and draw some diagrams to figure out which node is being rotated left and which is being rotated right, and in what order (I think your current implementation might be incorrect).