Please enable JavaScript.

Coggle requires JavaScript to display documents.

Árvores ! image, image, image, image, image, image, image, download__1_…

- - - - Em uma árvore binária simples, a inserção não segue uma regra específica sobre onde o novo nó deve ser colocado.
      - Começa pela raiz.
      - Se o novo valor for menor que o valor do nó atual, move-se para o filho à esquerda.
      - Se for maior, move-se para o filho à direita.
      - Continua até encontrar um lugar onde o nó pode ser inserido.
    - - Envolve os três casos:
      - Nó sem filhos: O nó é simplesmente removido.
      - Nó com um único filho: O filho substitui o nó.
      - Nó com dois filhos: O nó é substituído pelo sucessor (ou predecessor), e o sucessor (ou predecessor) é removido.
    - - busca pode ser realizada usando travessias como pré-ordem, em-ordem ou pós-ordem.
    - - Existem várias formas de percorrer uma árvore binária:
        
        Pré-Ordem: Visita a raiz, depois o filho à esquerda e, finalmente, o filho à direita.
        
        Em-Ordem: Percorre o filho à esquerda, depois visita a raiz e, finalmente, o filho à direita. (Em uma BST, isso resulta em uma lista ordenada.)
        
        Pós-Ordem: Percorre o filho à esquerda, depois o filho à direita e, finalmente, visita a raiz.
        
        Nível a Nível (Level-Order): Visita os nós nível por nível, começando pela raiz e descendo até as folhas.
    - - Verificação de Completa: Verifica se a árvore binária é completa, ou seja, se todos os níveis estão totalmente preenchidos, exceto possivelmente o último nível, que deve ser preenchido da esquerda para a direita.
      - Verificação de Cheia: Verifica se todos os nós têm 0 ou 2 filhos.
      - Verificação de Perfeita: Verifica se a árvore é cheia e completa, ou seja, todos os nós têm 0 ou 2 filhos, e todas as folhas estão no mesmo nível.
- - - - A inserção em uma BST é feita de modo a manter a propriedade
      - Passos
        
        Comece na raiz da árvore.
        
        Compare o valor a ser inserido com o valor do nó atual.
        
        Se o valor a ser inserido for menor que o valor do nó atual, mova-se para o filho à esquerda.
        
        Se o valor a ser inserido for maior, mova-se para o filho à direita.
        
        Repita o processo até encontrar um nó que tenha uma posição vazia ('null') onde o novo nó possa ser inserido como filho à esquerda ou à direita.
    - - Nó sem filhos (folha): Simplesmente remova o nó
      - Nó com um único filho:
        Remova o nó e conecte seu filho diretamente ao pai do nó removido.
      - Nó com dois filhos:
        
        Encontre o sucessor in-order (o menor valor na subárvore direita) ou o predecessor in-order (o maior valor na subárvore esquerda).
        
        Substitua o valor do nó a ser removido pelo valor do sucessor ou predecessor.
        
        Remova o sucessor ou predecessor, que será uma folha ou terá, no máximo, um filho.
    - - A busca é eficiente devido à propriedade ordenada da árvore
      - Pode-se decidir, em cada passo, se deve mover-se para a esquerda ou para a direita, de acordo com o valor da chave que está sendo procurada.
    - - Pré-Ordem (Pre-Order): Visita a raiz, depois a subárvore esquerda, seguida da subárvore direita. Útil para copiar a árvore.
      - Em-Ordem (In-Order): Visita a subárvore esquerda, depois a raiz, e por fim a subárvore direita. Em uma BST, isso resulta em uma lista de valores em ordem crescente.
      - Pós-Ordem (Post-Order): Visita a subárvore esquerda, depois a subárvore direita, e finalmente a raiz. Útil para deletar ou liberar a árvore.
      - Nível a Nível (Level-Order): Visita os nós nível por nível, da raiz até as folhas.
    - - Verificação de Balanceamento: Verifica se a árvore está balanceada, o que é importante para garantir a eficiência das operações.
      - Verificação de Propriedade BST: Verifica se a árvore mantém a propriedade de que para cada nó, todos os valores na subárvore esquerda são menores e na subárvore direita são maiores.
- - - - Insere-se a chave na posição correta, como em uma BST.
      - Após a inserção, verifica-se o fator de balanceamento dos nós antecessores, a partir do nó inserido até a raiz.
      - Se o fator de balanceamento de um nó for 2 ou -2 (indicando que o nó está desbalanceado), realiza-se uma rotação (simples ou dupla) para reequilibrar a árvore.
    - - Encontra-se o nó a ser removido, da mesma forma que em uma BST.
      - Remove-se o nó, garantindo que a árvore continue sendo uma BST.
      - Após a remoção, verifica-se o fator de balanceamento dos nós afetados, subindo em direção à raiz.
      - Se um nó estiver desbalanceado, realiza-se uma rotação para restaurar o balanceamento.
    - - Começa-se pela raiz e compara-se a chave procurada com a chave do nó atual.
      - Se a chave procurada for menor, segue-se para a subárvore esquerda; se for maior, segue-se para a subárvore direita.
      - O processo continua até encontrar a chave ou alcançar uma folha.
    - - Em-Ordem (In-Order): Visita os nós em ordem crescente de suas chaves. Usada quando se deseja obter os elementos em ordem ordenada. Ideal para obter todos os valores de uma Árvore AVL em sequência ordenada. Para cada nó, visita-se primeiro a subárvore esquerda, depois o próprio nó, e finalmente a subárvore direita.
      - Pré-Ordem (Pre-Order) Visita o nó atual antes de suas subárvores. Útil para copiar a árvore ou para processar cada nó antes de suas subárvores. Para cada nó, visita-se primeiro o próprio nó, depois a subárvore esquerda e, por último, a subárvore direita.
      - Pós-Ordem (Post-Order) Visita as subárvores antes de visitar o nó atual. Útil para operações que necessitam processar as subárvores antes do próprio nó, como a exclusão de todos os nós de uma árvore. Para cada nó, visita-se primeiro a subárvore esquerda, depois a subárvore direita e, finalmente, o próprio nó.
      - Nível (Level-Order) Visita os nós nível por nível, começando pela raiz e movendo-se para baixo. Útil para percorrer a árvore em ordem de profundidade, normalmente implementada usando uma fila. Cada nível da árvore é visitado sequencialmente, da esquerda para a direita.
    - - Propriedade de Balanceamento: Em uma Árvore AVL, a diferença de altura entre as subárvores esquerda e direita de qualquer nó (fator de balanceamento) deve ser no máximo 1. Após cada inserção ou remoção, calcula-se o fator de balanceamento para cada nó a partir do nó afetado até a raiz. Se o fator de balanceamento de um nó estiver fora do intervalo [-1, 1], a árvore está desbalanceada, e uma rotação (simples ou dupla) é realizada para restaurar o equilíbrio.
      - Propriedade de Ordem das Chaves: A Árvore AVL também deve manter as propriedades de uma Árvore Binária de Busca (BST). Para cada nó n, todas as chaves na subárvore esquerda devem ser menores que a chave em n, e todas as chaves na subárvore direita devem ser maiores. Durante a inserção e remoção, verifica-se se essa propriedade é mantida.
- - - - insere uma nova chave na árvore, mantendo a propriedade balanceada da estrutura.
      - Busca do Local de Inserção: Navega-se pela árvore a partir da raiz para encontrar o nó folha onde a nova chave deve ser inserida.
      - Divisão do Nó (Split): Se o nó folha estiver cheio, ele é dividido em dois nós, e o valor do meio é promovido ao nó pai.
      - Inserção no Nó Folha: Se o nó folha tem espaço (menos de m - 1 chaves, onde m é a ordem da árvore), a chave é simplesmente adicionada ao nó.
      - Propagação para Cima: Se a divisão do nó causa o pai também ficar cheio, o processo de divisão pode continuar subindo na árvore, até possivelmente dividir a raiz e aumentar a altura da árvore.
    - - Encontra a chave a ser removida.
      - Se a chave estiver em um nó folha, remove-a diretamente.
      - Se a chave estiver em um nó interno:
        
        Substitui pela chave predecessora ou sucessora.
        
        Remove a chave da folha correspondente.
      - Reequilibra a árvore se um nó cair abaixo do número mínimo de chaves:
        
        Funde o nó com um irmão ou redistribui as chaves entre irmãos.
        
        Ajusta a raiz, se necessário, reduzindo a altura da árvore.
      - Travessia
        
        Em-Ordem (In-Order): Visita as chaves em cada nó em ordem crescente. Isso envolve a travessia recursiva de cada subárvore à esquerda, seguida pela visita às chaves no nó, e depois a travessia das subárvores à direita.
        
        Pré-Ordem (Pre-Order): Visita cada nó antes de visitar suas subárvores, o que é útil para copiar a árvore ou processar cada nó antes de suas subárvores.
        
        Pós-Ordem (Post-Order): Visita as subárvores antes de visitar o nó em si, o que é útil para operações que precisam processar as subárvores antes do nó.
    - - Inicia a partir da raiz.
      - Compara a chave desejada com as chaves em cada nó.
      - Segue o ponteiro adequado para descer na árvore até encontrar a chave ou alcançar uma folha.
    - - É feito verificando o número de chaves por nó, a ordem das chaves, a uniformidade da altura, a estrutura de ponteiros, e realizando fusões ou redistribuições conforme necessário.
      - Essas verificações são cruciais para manter as características de desempenho da Árvore B, especialmente em sistemas que lidam com grandes volumes de dados.
- - - - A inserção em uma Árvore de Segmentos não é uma operação típica, pois a árvore é construída a partir de um array inicial. A construção da árvore é feita uma única vez e envolve a criação de nós que representam segmentos do array.
        
        Ao construir a árvore, cada nó é preenchido com informações sobre o intervalo que ele representa (por exemplo, a soma dos elementos nesse intervalo). A árvore é criada de baixo para cima, combinando os segmentos dos nós filhos para formar nós pais.
    - - A remoção direta de elementos em uma Árvore de Segmentos não é uma operação suportada de forma convencional. Em vez disso, a árvore é ajustada para refletir as mudanças feitas no array, usando atualizações.
        
        Em vez de remover, você pode atualizar o valor em um índice específico e a árvore será ajustada para refletir essa mudança.
    - - A busca é a operação de consultar um intervalo específico no array para obter informações como soma, mínimo ou máximo. A árvore é percorrida para combinar os intervalos que cobrem o intervalo da consulta.
        
        A busca divide o intervalo de consulta em segmentos que são representados pelos nós da árvore e combina os resultados desses nós.
    - - Pré-Ordem: Visita o nó atual antes de suas subárvores. Pode ser usada para percorrer e processar todos os nós na árvore.
        
        Em-Ordem: Visita a subárvore esquerda, depois o nó atual, e depois a subárvore direita. Menos comum, mas pode ser usada para percorrer a árvore de uma maneira específica.
        
        *Pós-Ordem: Visita as subárvores antes do nó atual. Útil para liberar a memória da árvore ou para outras operações que requerem processamento das subárvores antes do nó atual.
    - - Cada nó da Árvore de Segmentos representa um intervalo específico do array original. A propriedade fundamental que deve ser verificada é que a informação armazenada em cada nó deve refletir corretamente a informação do intervalo que o nó cobre.
        
        Após uma atualização em um índice específico ou intervalo, a árvore deve garantir que todos os nós afetados sejam ajustados corretamente para refletir a nova informação.
        
        Lazy propagation é uma técnica usada para otimizar atualizações de intervalo em uma Árvore de Segmentos. Em vez de atualizar imediatamente todos os nós afetados, a atualização é marcada e aplicada somente quando necessário.
        
        A árvore deve manter a consistência entre os nós e seus filhos, garantindo que a informação agregada nos nós pais esteja correta em relação aos seus filhos.
- - - - Inserção de uma string na Trie é feita caractere por caractere, criando novos nós conforme necessário para cada caractere da string.
      - Começa-se pela raiz e para cada caractere da string, segue-se para o nó correspondente ao caractere.
      - Se o nó para o caractere não existir, cria-se um novo nó.
      - Marca-se o final da string em um nó específico (usualmente com um indicador booleano).
    - - Remover uma string da Trie envolve a remoção de nós que não são mais necessários após a remoção da string.
      - Primeiro, busca-se a string para garantir que ela está na Trie.
      - Remove-se a string caractere por caractere, começando do final da string.
      - Se um nó não é mais necessário (não faz parte de outras strings), ele é removido.
    - - A busca em uma Trie é feita caractere por caractere, seguindo os nós correspondentes a cada caractere da string de busca.
      - Começa-se pela raiz e para cada caractere da string, segue-se para o nó correspondente.
      - Se um caractere não corresponder a um nó existente, a string não está na Trie.
      - Verifica-se se o último nó da busca é um nó de término de string (indicando que a string completa está presente).
    - - Pré-Ordem: Visita o nó atual antes de suas subárvores. Pode ser usada para listar todas as strings armazenadas na Trie, ou para processar as strings de forma específica.
      - Em-Ordem: Não é comumente aplicada em Tries, pois a estrutura não é binária e não possui uma ordem natural de filhos.
      - Pós-Ordem: Visita as subárvores antes de visitar o nó atual. Pode ser utilizada para liberar memória ou para processar strings de forma específica, processando as strings antes de retornar à raiz.
    - - A verificação de propriedades em uma Trie envolve garantir que a estrutura da árvore está correta e que todas as strings estão corretamente representadas.
      - Consistência: Verifica-se se os nós representam corretamente os prefixos das strings armazenadas.
      - Marcadores de Fim de String: Verifica-se se os nós que representam o final de uma string estão corretamente marcados.
      - Integridade da Estrutura: Garante-se que os nós e arestas estão corretamente conectados e que não há nós desnecessários.