Estrutura de Dados I - Pre-Ordem, In-Ordem e Inserção em Árvore Binária, Notas de estudo de Análise de Sistemas de Engenharia

Baixe Estrutura de Dados I - Pre-Ordem, In-Ordem e Inserção em Árvore Binária e outras Notas de estudo em PDF para Análise de Sistemas de Engenharia, somente na Docsity! 1 Instituto Luterano de Ensino Superior de Ji-Paraná Curso Bacharelado em Informática Estrutura de Dados I Prof.: José Luiz A. Duizith A B D . . C E . E C Pré: A B C D E B In : B C A E D D Pos: C B E D A A Usando Pilha Procedimento Pré_Ordem (nodo) { s/ recursividade } {escreve o caminhamento em Pré-Ordem a partir de um nodo da árvore raiz} Se (Nodo <> NIL) {raiz não vazia} Então Cria_pilha(Pilha) Empilha (Pilha,Nodo) Enquanto (Não Pilha_Vazia (Pilha)) Faça Aux ← Consulta_Pilha (Pilha) Desempilha (Pilha) Visita (Aux) Se (Aux↑.Dir <> NIL) Entao Empilha (Pilha, Aux↑.Dir) Se (Aux↑.Esq <> NIL) Entao Empilha (Pilha, Aux↑.Esq) Destroi_Pilha (Pilha) { fazer Pós-Ordem sem recursividade. Poderá cair na prova !!! } Procedimento Pré_Ordem (Nodo) { c/ recursividade } Se (Nodo <> Nil) Entao Visita (Nodo) Pre_Ordem (Nodo↑.Esq) Pre_Ordem (Nodo↑.Dir) Estrutura de Dados I Prof. José Luiz Andrade Duizith 2 Procedimento In_Ordem (Nodo) { c/ recursividade } Se (Nodo <> NIL) Entao In_Ordem (Nodo↑.Esq) Visita (Nodo) In_Ordem (Nodo↑.Dir) TIPOS DE ÁRVORES 1º Árvore binária de busca (ou de pesquisa) definição: Uma árvore binária é uma árvore binária de busca se para cada nó N da árvore for verdade que SEM <= N <= SDN , isto é, todos os nodos da subárvore à esquerda precedem a raiz e a raiz precede todos os nodos da subárvore à direita. SENSDN: Subárvore à esquerda/direita de N. 10 7 15 5 9 13 17 19 Nº acessos : log2 N 5 7 9 10 13 15 17 19 Procedimento Cria_Arvore_Binaria (Raiz) Raiz ← NIL Procedimento Arvore_Vazia (Raiz) : Lógico Logico ← (Raiz = NIL) Procedimento Destroi_Arvore_Binaria (Raiz) Se (Não_Arvore_Vazia (Raiz)) Entao Pos_Ordem (Raiz) { visita (nodo) na Pos-Ordem seria Raiz ← NIL desaloque (nodo) } Estrutura de Dados I Prof. José Luiz Andrade Duizith 5 REMOÇÃO: Nodo Folha: acerta subárvore do pai remove a folha Nodo com uma subárvore acerta o pai com a subárvore restante remove o nodo Nodo com duas subárvores: encontrar o predecessor / sucessor substituir o nodo pelo predecessor / sucessor remove o predecessor / sucessor Estrutura de Dados I Prof. José Luiz Andrade Duizith 6 Procedimento Remove (Nodo, Valor) Se (Arvore_Vazia (Nodo)) Entao ERRO1 Senao Se (Não Consulta (Nodo, Valor, Aux)) Entao ERRO2 Senao Se ((Aux↑.Esq = NIL) E (Aux↑.Dir = NIL)) {nodo folha} Entao Pai ← Encontra_Pai (Nodo,Valor) {achou o pai} Se (Pai = NIL) {nodo a remover é a raiz} Entao Nodo ← NIL Senao Se (Valor < Pai↑.Dado) Entao Pai↑.Esq ← NIL Senao Pai↑.Dir ← NIL Senao Se (aux↑.Esq = NIL) {nodo c/ subárvore à direita} Entao Pai ← Encontra_Pai (Nodo,Valor) Se (Pai = NIL){nodo a remover é a raiz} Entao Nodo ← Aux↑.Dir Senao Se (Valor < Pai↑.Dado) Entao Pai↑.Esq ← Aux↑.Dir Senao Pai↑.Dir ← Aux↑.Dir Senao Se (Aux↑.Dir = NIL) {nodo c/ subárvore a esquerda} Entao Pai ← Encontra_Pai (nodo,valor) Se (Pai = NIL) {nodo a remover é a raiz} Entao Raiz ← Aux↑.Esq Senao Se (Valor < Pai↑.Nodo) Entao Pai↑.Esq←Aux↑.Esq Senao Pai↑.Dir←Aux↑.Esq Senao Pred ← Predecessor (Aux,Valor) {nodo com 2 subárvores} Temp ← Pred↑.Dado Remove (Aux,Temp) Aux↑.Dado ← Temp Aux ← NIL Se (Aux <> NIL) Entao DESALOQUE (Aux) Estrutura de Dados I Prof. José Luiz Andrade Duizith 7 Função Predecessor (Nodo) : Aux_Pred Se (Nodo = NIL) Entao Aux ← NIL Senao Aux ← Nodo↑.Esq Enquanto (Aux↑.Dir <> NIL) Faça Aux ← Aux↑.Dir Aux_Pred ← Aux Árvore Amarrada (ou costurada - Alinhavadas (“Threaded Trees”) Amarras → referências a outros nós da árvore. Se subárvore da esq. De um nó é vazia, então a referência da esq. Deste nó aponta p/ o nó predecessor a este, com respeito a uma dada ordem de caminhamento. De forma similar, se a subárvore da direita de um nó é vazia, então a referência da direita do nó aponta p/ o nó que lhe sucede na mesma ordem de caminhamento. F ****** V Amarrada Ref. Estruturada Quando a árvore não for vazia, a ref. Da esq. Do nó descritor apontará p/ a raiz da árvore. Se a ordem de caminhamento p/ a qual a árvore for amarrada é a ordem central, então o nó descritor será o predecessor e sucessor do 1º e do último nó da árvore, respectivamente. Isto impõem, na realidade, uma característica circular à árvore. → Muitos nodos possuem referências nulas, tais referências podem servir para indicar uma determinada ordem de caminhamento. → Para distinguir uma ligação estrutural de uma amarrada acrescentam-se 2 campos lógicos adicionais. Estrutura de Dados I Prof. José Luiz Andrade Duizith 10 Procedimento Insere_Dir (Nodo, Aux) Aux↑.Dir ← Nodo↑.Dir Aux↑.DLIG ← Nodo↑.DLIG Nodo↑.Dir ← Aux Nodo↑.DLIG ← Verdadeiro Aux↑.Esq ← Nodo Aux↑.ELIG ← Falso Se (Aux↑.DLIG) {nodo possui Sub-direita} Entao Suc ← Aux↑.Dir Suc↑.Esq ← Aux Suc ↑.ELIG ← Falso Procedimento In_Ordem (Header) {caminhamento em In_Ordem s/ recursividade, sem estruturas adicionais} Se (Header↑.Esq = Header) {árvore vazia} Entao ERRO Senao Aux ← Sucessor_Central (Header) Enquanto (Aux <> NIL) Faça Visita (AUX) Aux ← Sucessor_Central (Aux) Estrutura de Dados I Prof. José Luiz Andrade Duizith 11 Árvore Tipo-B (“B Tree”) Def.: é uma árvore que possui as seguintes características: a) todos os nodos folhas estão no mesmo nível b) um nodo que possua “k” filhos, possui “k-1” chaves c) todo nodo, exceto a raiz, possui no máximo k / 2 filhos Aplicação: manipulação de índices de arquivos Conj. de Indice ordem:1 raiz 1 50 82 2 Variação de Knuth de Árvore-B 12 32 58 / ^ 89 / ^ 6 12 15 32 50 ^ / 52 58 82 ^ / 72 89 Ligações c/ os registros de dados → Achar onde está o reg do arq. 50 (1) → percorre a esquerda (2) → 50 é maior que 32? Então percorre a direita (3) Uma arvore-B de ordem n tem no mínimo n, mas não mais do que 2n valores de dados (chaves) em cada nodo → se um nodo possui k valores possui k + 1 ligações (apontadores) Ex.: ESQ DADO1 MEIO DADO2 DIR Estrutura de Dados I Prof. José Luiz Andrade Duizith