Created
June 21, 2017 14:45
-
-
Save leandrovianna/dfff333562c5a68e21646a4c2116f314 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| #include <stdlib.h> | |
| typedef struct cel{ | |
| int chave; | |
| struct cel *esq; | |
| struct cel *dir; | |
| int bal; | |
| }NO; | |
| typedef NO *arvore; | |
| arvore New_Node(int chave){ | |
| arvore new = (NO *) malloc(sizeof(NO)); | |
| arvore->chave = chave; | |
| arvore->esq = NULL; | |
| arvore->dir = NULL; | |
| arvore->bal = 0; | |
| return new; | |
| } | |
| int Height(arvore r) { | |
| if (r == NULL) return 0; | |
| else 1 + Max(Height(r->esq), Height(r->dir)); | |
| } | |
| arvore Insert(arvore r, int chave){ | |
| arvore f, n; | |
| char insertLeft; | |
| if(r->chave > chave){ | |
| if(r->esq == NULL){ | |
| r->esq = New_Node(chave); | |
| r->bal+=1; | |
| } | |
| else | |
| r->esq = Insert(r->esq , chave); | |
| insertLeft = 1; | |
| } | |
| else{ | |
| if(r->dir == NULL){ | |
| r->dir = New_Node(chave); | |
| r->bal-=1; | |
| } | |
| else | |
| r->dir = Insert(r->dir , chave); | |
| insertLeft = 0; | |
| } | |
| if(insertLeft){ | |
| r->bal += (r->esq->bal != 0) ? 1 : 0; | |
| } | |
| else{ | |
| r->bal -= (r->dir->bal != 0) ? 1 : 0; | |
| } | |
| if(r->bal > 1 || r->bal < -1){ | |
| if (insertLeft) { | |
| f = r->esq; | |
| if (f->chave < chave) { | |
| // call simple rotation (left left) | |
| r->esq = f->dir; | |
| f->dir = r; | |
| r = f; | |
| } | |
| else { | |
| n = f->dir; | |
| // call double rotation (left right) | |
| // right simple rotation with f and n | |
| f->dir = n->esq; | |
| n->esq = f; | |
| f = n; | |
| // left simple rotation with r and f | |
| r->esq = f->dir; | |
| f->dir = r; | |
| r = f; | |
| } | |
| } else { | |
| f = r->dir; | |
| if (f->chave < chave) { | |
| n = f->esq; | |
| // call double rotation (right left) | |
| // left simple rotation with f and n | |
| f->esq = n->dir; | |
| n->dir = f; | |
| f = n; | |
| // right simple rotation with r and f | |
| r->dir = f->esq; | |
| f->esq = r; | |
| r = f; | |
| } | |
| else { | |
| // call simple rotation (right right) | |
| r->dir = f->esq; | |
| f->esq = r; | |
| r = f; | |
| } | |
| } | |
| } | |
| return r; | |
| } | |
| int main(void) { | |
| int n; | |
| arvore tree = NULL; | |
| scanf("%d", &n); | |
| for (i = 0; i < n; i++) { | |
| scanf("%d", &x); | |
| tree = Insert(tree, x); | |
| } | |
| return 0; | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment