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

Printable View

• 06-24-2011
saintshion
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); }```
• 06-24-2011
anduril462
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.
• 06-24-2011
quzah
Code:

```int depthfind( tree *t, int d, int tofind ) {     int rval = -1     if( t )     {         if( t->value == tofind )             rval = d;         if( rval == -1 )             rval = depthfind( t->left, d+1, tofind );         if( rval == -1 )             rval = depthfind( t->right, d+1, tofind );     }     return rval; } ... depth = depthfind( firstnode, 0, 3 );```
That looks about right.

edit - too slow

Quzah.
• 06-24-2011
saintshion
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;                   }```
• 06-24-2011
quzah
You aren't even trying to understand what I wrote, are you?
Code:

```    return rval;     printf("caminho:", rval); }```
That line is never reachable.
Code:

```                    printf("\nDigite o codigo: ");                     scanf ("%d*c", &entrada);                     depth = depthfind(pai, 0, 3 );                     break;```
I'm not sure what entrada is, but you probably mean to be passing it as one of those arguments (the third one probably).

Quzah.
• 06-24-2011
saintshion
sorry!
Code:

```printf("caminho:", rval); return rval;```
entrada is the value that the user enters to show the depth
• 06-26-2011
saintshion
still does not work =/
• 06-26-2011
AndrewHunter
Don't bump your own thread, that is the quickest way to get ignored and have your thread locked. A great tutorial about everything you are looking to do can be found here. Read through that and then take a look at your code again. This will present you the information you have already been given in a more detailed manner. Take a look at it, understand it, and then work on your code.
• 06-26-2011
saintshion
Thank you and sorry I'll read
• 06-30-2011
saintshion
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*/          }```
• 06-30-2011
quzah
What are you trying to do?
Code:

```Perfume_ptr RotacaoSimplesEsquerda(Perfume_ptr K2) {             Perfume_ptr K1, K3;             K1 = K2->esq;                         K3 = K1->pai;             K1->pai = K2->pai;             K2->pai = K3;```
If that is NULL, then this crashes your program.

Quzah.
• 06-30-2011
anduril462
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.
• 06-30-2011
AndrewHunter
These questions that you have with AVL trees are all answered with this tutorial. I am more than positive you will be able to see what is presented there and compare that to your implementation.
• 06-30-2011
saintshion
﻿﻿Hello, I tried to translate into English what I'm trying to do the program, if they can help me get him packing to go I would be grateful.

* do not speak English, I'm using a translator gloogle
Code:

```      /* This function can be called only if K2 has a left child */       /* Perform a rotate between a node (K2) and its left child */         /* Update heights, then return new root */ Perfume_ptr RotacaoSimplesEsquerda(Perfume_ptr K2) {             Perfume_ptr K1, K3;             K1 = K2->esq;                         K3 = K2->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*/ new root }         /* This function can be called only if K1 has a right child */         /* Perform a rotate between a node (K1) and its right child*/         /* Update heights, then return new root */        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*/  new root        }         /* This function can be called only if K3 has a left */         /* child and K3's left child has a right child */         /* Do the left-right double rotation */         /* Update heights, then return new root */        Perfume_ptr RotacaoDuplaEsquerda(Perfume_ptr K3) {             /*Rotaciona entre K1 e K2*/           /* Rotate between K1 and K2 */             K3->esq = RotacaoSimplesDireita(K3->esq);             /*Rotaciona entre K3 e K2*/             /* Rotate between K3 and K2 */             return RotacaoSimplesEsquerda(K3);          }          /* This function can be called only if K1 has a right */         /* child and K1's right child has a left child */         /* Do the right-left double rotation */         /* Update heights, then return new root */        Perfume_ptr RotacaoDuplaDireita(Perfume_ptr K1) {             /*Rotaciona entre K3 e K2*/             /* Rotate between K3 and K2 */             K1->dir = RotacaoSimplesEsquerda(K1->dir);             /*Rotaciona entre K1 e K2*/           /* Rotate between K1 and K2 */             return RotacaoSimplesDireita(K1);    }```
• 07-01-2011
anduril462
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.

Attachment 10697

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).