Arvore Rubro Negra
Por: Jhordan Olv • 13/4/2017 • Relatório de pesquisa • 2.746 Palavras (11 Páginas) • 223 Visualizações
#include
#include
#define PRETO 0
#define VERMELHO 1
typedef struct no_arvore {
int n;
int cor;
struct no_arvore *esq, *dir, *pai;
} no_arvore;
no_arvore *SENTINELA;
void busca_pre_order(no_arvore *raiz) {
if (raiz != SENTINELA) {
printf("%d (%d)\t", raiz->n, raiz->cor);
busca_pre_order(raiz->esq);
busca_pre_order(raiz->dir);
}
}
int altura(no_arvore *raiz) {
if (raiz == NULL)
return -1;
else {
int h_esq, h_dir;
h_esq = altura(raiz->esq);
h_dir = altura(raiz->dir);
if (h_esq > h_dir)
return h_esq + 1;
else
return h_dir + 1;
}
}
no_arvore *rotacao_simples_esq(no_arvore *R) {
no_arvore *F = R->dir;
R->dir = F->esq;
F->esq = R;
return F;
}
no_arvore *rotacao_simples_dir(no_arvore *R) {
no_arvore *F = R->esq;
R->esq = F->dir;
F->dir = R;
return F;
}
no_arvore *retorna_tio(no_arvore *R, no_arvore *pai, no_arvore *avo) {
if (pai == avo->esq)
return avo->dir;
else
return avo->esq;
}
no_arvore *retorna_avo(no_arvore *R) {
return R->pai->pai;
}
no_arvore *verifica_balanceamento(no_arvore *R) {
if (R->pai != NULL && R->pai->cor != PRETO) {
}
}
no_arvore *insere(int x, no_arvore *raiz, no_arvore *pai) {
if (raiz == NULL || raiz == SENTINELA) { //Árvore vazia.
...