Wondershare EdrawMind
Galeria de mapas mentais estrutura de dados
- 1
estrutura de dados
A coisa mais básica e importante no campo da informática atual é a estrutura de dados. Este mapa mental contém o conhecimento básico de estruturas de dados, como estruturas lineares, estruturas em árvore, estruturas gráficas, seus métodos de implementação e algoritmos comuns, como classificação e pesquisa. Se você deseja obter uma base sólida em estruturas de dados, este mapa mental será um grande ajudante para você. Ajuda você a aprender e compreender diferentes tipos de estruturas de dados e como otimizar e melhorar algoritmos com estruturas de dados apropriadas.
Editado em 2023-02-16 10:18:56
- Microbiologia medica Infezione batterica e immunità
Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
- teoria cinetica dei gas
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
- Breve História do Tempo
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
estrutura de dados
- Microbiologia medica Infezione batterica e immunità
Microbiologia medica, Infezioni batteriche e immunità riassume e organizza i punti di conoscenza per aiutare gli studenti a comprendere e ricordare. Studia in modo più efficiente!
- teoria cinetica dei gas
La teoria cinetica dei gas rivela la natura microscopica dei fenomeni termici macroscopici e le leggi dei gas trovando la relazione tra quantità macroscopiche e quantità microscopiche. Dal punto di vista del movimento molecolare, vengono utilizzati metodi statistici per studiare le proprietà macroscopiche e modificare i modelli di movimento termico delle molecole di gas.
- Breve História do Tempo
Este é um mapa mental sobre uma breve história do tempo. "Uma Breve História do Tempo" é um trabalho científico popular com influência de longo alcance. Ele não apenas introduz os conceitos básicos da cosmologia e da relatividade, mas também discute os buracos negros e a expansão. Do universo. questões científicas de ponta, como inflação e teoria das cordas.
- Recomendado para você
- Descrição
Versão Anual de Ação BP do Plano de Marketing Farmacêutico (Versão de Prática de Execução)
- 6
estrutura de dados
Árvores Binárias e Árvores e Florestas
Árvores e árvores binárias
Como converter uma árvore em uma árvore binária?
Tanto a representação de irmão filho de uma árvore quanto a representação de lista vinculada binária de uma árvore binária usam dois ponteiros.
Entenda a representação do irmão filho como uma lista vinculada binária
Método de simulação manual para converter uma árvore em uma árvore binária:
① Conecte os filhos do mesmo nó com linhas
② Exclua os ramos da subárvore de cada nó da esquerda para a direita, exceto o primeiro.
exemplo
Como converter uma árvore binária em uma árvore?
Método de simulação manual para converter uma árvore binária em uma árvore:
① Divida a árvore binária de cima para baixo e ajuste-a na direção horizontal. (Método hierárquico: cada vez que você encontra o filho esquerdo, é uma camada)
② Encontre o nó pai de cada camada. O método é que o nó conectado à camada anterior seja o nó pai. Por exemplo, na camada bcd, o nó na camada superior conectado a ela é a, portanto, os nós pais dos três nós em bcd são todos a.
③ Conecte cada nó da camada ao seu nó pai e exclua as conexões entre os nós filhos do nó pai.
exemplo
Floresta e árvore binária
Floresta: Uma floresta é uma coleção de m (m≥0) árvores disjuntas.
Como converter floresta em árvore binária?
Método de simulação manual para converter floresta em árvore:
①Converta cada árvore da floresta em uma árvore binária
② Considere a segunda árvore como a subárvore direita do nó raiz da primeira árvore e a terceira árvore como a subárvore direita do nó raiz da segunda árvore... e assim por diante.
exemplo
Como converter árvore binária em floresta?
Método de simulação manual para converter uma árvore binária em uma floresta:
Desconecte repetidamente o ponteiro da subárvore direita do filho direito do nó raiz da árvore binária até que não haja nenhuma árvore binária com um filho direito do nó raiz.
exemplo
Atravessando árvores e florestas
Pré-encomenda: visite primeiro o nó raiz e, em seguida, visite cada subárvore do nó raiz. O acesso às subárvores também segue a ordem dos requisitos de precedência.
Pós-ordem: primeiro visite cada subárvore do nó raiz e, em seguida, visite o nó raiz. O acesso às subárvores também segue a ordem dos requisitos de precedência.
exemplo
A travessia de pré-ordem de uma árvore é igual à travessia de pré-ordem de sua árvore binária correspondente, e a travessia de pós-ordem é igual à travessia em ordem de sua árvore binária correspondente.
Capítulo 7: Classificação
Conhecimento básico de classificação
Definição: Classificar é reorganizar uma sequência originalmente não ordenada em uma sequência ordenada.
classificação de estabilidade
Se houver dois elementos Ri e Rj na lista a ser classificada, e suas palavras-chave correspondentes keyi = keyj, e Ri estiver na frente de Rj antes da classificação, se após a classificação usando um determinado algoritmo de classificação, Ri ainda estiver na frente de Rj, então isso é chamado O algoritmo de classificação é estável, caso contrário, é considerado instável.
Classificação de classe de inserção
classificação por inserção direta
Ordenação por inserção direta: primeiro use um elemento como uma sequência ordenada e, em seguida, insira os elementos subsequentes na sequência ordenada nas posições apropriadas até que todos os elementos sejam inseridos na sequência ordenada.
A complexidade do tempo é O (n)
A classificação por inserção direta é estável.
classificação de meia inserção
A classificação por inserção intermediária separa as duas operações de comparação e movimento, ou seja, primeiro usa a meia pesquisa para encontrar a posição de inserção, depois move o elemento de uma vez e depois insere o elemento.
A complexidade de tempo da classificação de meia inserção é O (n ^ 2)
Estabilidade: É igual à estabilidade da classificação por inserção direta e é estável.
Tipo de colina
A ideia básica da classificação de Hill: a classificação de Hill é essencialmente uma classificação por inserção, mas divide a sequência a ser classificada em várias subsequências e, em seguida, executa a classificação por inserção direta nessas subsequências.
① Primeiro divida a sequência pelo incremento 5, ou seja, as palavras-chave com subscritos 0, 5, 10, 15... são divididas em um grupo, e as palavras-chave com subscritos 1, 6, 11, 16.. são divididas em um grupo e, em seguida, esses grupos são submetidos à classificação por inserção direta, respectivamente, o que completa uma rodada de classificação Hill.
②Reduza o incremento (d1=n/2, di 1= [di/2], por exemplo, 10 sequências de dados, o primeiro incremento d1=10/2=5, o segundo incremento d2= [d1/2 ]= [5 /2]=2, e o último incremento é igual a 1), então a segunda rodada executa um processo de classificação semelhante com um incremento de 2.
③A próxima terceira rodada, quarta rodada... são processos semelhantes até a última rodada com um incremento de 1. Esta é a classificação por inserção direta mencionada anteriormente.
Complexidade de tempo:... A complexidade de tempo da classificação Hill é cerca de O (n ^ 1,3). No pior caso, a complexidade de tempo da classificação Hill é O (n ^ 2).
Complexidade espacial: A complexidade espacial da classificação Hill é O (1)
Estabilidade: Instável Devido a diferentes incrementos, palavras-chave iguais podem ser divididas em duas classificações de inserção direta para classificação, o que pode causar alterações de ordem relativa.
Classificação de troca
Tipo de bolha
Suponha que o comprimento da lista a ser classificada seja n. Compare os valores dos elementos adjacentes de trás para frente (ou de frente para trás) (ou seja, A[i-1]>A[). i]), troque-os até que a comparação de sequências seja concluída. Chamamos isso de passagem de bolha e o resultado é que o menor elemento é trocado para a primeira posição da coluna a ser classificada. Na próxima bolha, o elemento mínimo determinado na bolha anterior não participará mais da comparação, e a sequência a ser ordenada será reduzida em um elemento. O resultado de cada bolha colocará o menor elemento da sequência no final. posição da sequência,..., este é o máximo. Todos os elementos podem ser classificados fazendo n-1 bolhas.
Complexidade do espaço: O espaço de armazenamento é aberto para armazenar variáveis intermediárias durante a troca, então a complexidade do espaço é O(1)
complexidade de tempo
Estabilidade: quando duas palavras-chave são iguais, a condição de julgamento if não é válida, portanto, nenhuma movimentação de dados ocorrerá. Então está estável.
Ordenação rápida
A classificação rápida é um método de classificação baseado em dividir e conquistar. Cada classificação rápida seleciona qualquer elemento na sequência como o pivô (geralmente o primeiro elemento é selecionado), move todos os elementos na sequência que são menores que o pivô para a frente do pivô e move todos os elementos que são maiores que o pivô . Fique atrás do pivô.
1
2
complexidade de tempo: Na melhor das hipóteses, a complexidade do tempo é O(nlogn). Quanto mais desordenada for a sequência a ser ordenada, maior será a eficiência do algoritmo. No pior caso, a complexidade do tempo é O(n^2). Quanto mais ordenada for a sequência a ser classificada, menor será a eficiência do algoritmo.
Complexidade do espaço: Como a classificação rápida é recursiva, é necessária uma pilha de trabalho recursiva para salvar as informações necessárias para cada nível de chamadas recursivas. Sua capacidade deve ser consistente com a profundidade máxima das chamadas recursivas. O melhor cenário é ⌈log2(n 1)⌉ (cada partição é uniforme) e a profundidade da árvore recursiva é O(logn) Na pior das hipóteses, como são necessárias n-1 chamadas recursivas, a profundidade da pilha é O(n);
Estabilidade: a classificação rápida é instável devido à existência de palavras-chave de troca.
Selecione a classificação da classe
Ordenação por seleção simples
Complexidade do espaço: O espaço de armazenamento adicional necessário é apenas a variável intermediária usada na troca de elementos, portanto a complexidade do espaço é O(1)
complexidade de tempo: A operação principal é trocar elementos. Todo o algoritmo consiste em loops duplos. O loop externo vai de 0 a n-2 um total de n-2 1=n-1 vezes. Para o i-ésimo loop externo, o loop interno executa n-1-(i 1) 1=n-i-1 vezes. Quando i=0, o loop interno é executado n-1 vezes. Quando i=n-2, o loop interno é executado uma vez, portanto é uma soma de sequência aritmética, totalizando (1 n-1)(n-1) /. 2=n(n-1)/2, então a complexidade do tempo é O(n^2)
Estabilidade: instável A razão é que a parte cambial quebrará a ordem relativa
Classificação de pilha
O que é uma pilha?
O heap é uma árvore binária completa e o valor de qualquer nó não-folha não é maior (ou nem menor) que o valor de seus nós filhos esquerdo e direito.
Se o valor de cada nó não for menor que o valor de seus nós filhos esquerdo e direito, ele será chamado de big top heap.
Se o valor de cada nó não for maior que o valor de seus nós filhos esquerdo e direito, ele será chamado de pequeno heap superior.
O que é classificação de heap?
Sabemos que para um heap, seu nó raiz é o valor máximo (heap superior grande) ou o valor mínimo (heap superior pequeno) dos valores de todos os nós em todo o heap. Portanto, a ideia da classificação de heap é ajustar a sequência não ordenada em um heap a cada vez e, em seguida, selecionar o valor do elemento superior do heap, adicionar esse valor à sequência ordenada, reduzir a sequência não ordenada em um e, em seguida, repetidamente ajuste a sequência não ordenada até que todas as palavras-chave sejam adicionadas à sequência ordenada.
complexidade de tempo: O tempo total de classificação do heap pode ser dividido em ① parte de construção do heap ② n-1 ajustes descendentes no heap A complexidade de tempo da classificação de heap é O(n) O(nlog2n)=O(nlog2n)
A classificação de heap é instável
classificação por mesclagem
Supondo que a tabela a ser classificada contém n registros, ela pode ser considerada como n subtabelas ordenadas, cada uma com comprimento de 1, e então mescladas em pares para obter ⌈n/2⌉ tabelas ordenadas com comprimento de 2 ou 1 ; e, em seguida, mescle-os dois por dois... e repita isso até que sejam mesclados em uma lista ordenada de comprimento n. Esse método de classificação é chamado de classificação por mesclagem bidirecional.
Por exemplo: 49 38 65 97 76 13 27
①Primeiro, trate cada palavra-chave de toda a sequência como uma subsequência ordenada separada
② Mesclar dois a dois, 49 e 38 são mesclados em {38 49}, 65 e 97 são mesclados em {65 97}, 76 e 13 são mesclados em {13 76}, 27 não tem objeto de mesclagem
③ Mesclar dois a dois, {38 49} e {65 97} são mesclados em {38 49 65 97}, {13,76} e 27 são mesclados em {13 27 76}
④ Mesclar dois a dois, {38 49 65 97} e {13 27 76} mesclar em {13 27 38 49 65 76 97}
Complexidade de tempo: O (nlog2n)
Complexidade do espaço: Como a sequência a ser ordenada precisa ser transferida para um array, um espaço de armazenamento adicional de tamanho n precisa ser aberto, ou seja, a complexidade do espaço é O(n)
Estabilidade: estável
Classificação de raiz
A classificação Radix (também chamada de classificação por bucket) é um método de classificação muito especial. Não é classificado com base em comparação, mas usa a ideia de classificação de várias palavras-chave (ou seja, classificação com base no tamanho de cada palavra-chave), com o. ajuda de operações de "alocação" e "coleta" para classificar palavras-chave lógicas únicas. A classificação Radix é dividida em classificação do dígito mais alto primeiro (MSD) e classificação do dígito mais baixo primeiro (LSD).
Exemplos: 53, 3, 542, 748, 14, 214, 154, 63, 616
Dígitos suplementares: 053, 003, 542, 748, 014, 214, 154, 063, 616
O balde é na verdade uma fila, primeiro a entrar, primeiro a sair (entra por cima do balde e sai por baixo)
O número de palavras-chave é n, o número de dígitos da palavra-chave é d, por exemplo, 748 d=3, r é o número de bases da palavra-chave, que é o tipo de dado que compõe a palavra-chave, por exemplo, existem 10 dígitos decimais de 0 a 9 no total, ou seja, r = 10.
Complexidade do espaço: É necessário abrir várias filas de bases de palavras-chave, então a complexidade do espaço é O(r)
Complexidade de tempo: D tempos de "alocação" e "coleta" são necessários para o número de palavras-chave. Uma "alocação" requer que n palavras-chave sejam colocadas em cada fila, e uma "coleção" requer que r baldes sejam coletados. Portanto, a complexidade de tempo de uma "alocação" e uma "coleção" é O(n r). D vezes requer uma complexidade de tempo de O(d(n r)).
Estabilidade: Por se tratar de uma fila com natureza first in first out, ela é alocada em ordem quando alocada, o que é estável, portanto permanece estável durante a coleta. Ou seja, radix sort é um algoritmo de classificação estável.
classificação externa
É necessário armazenar os registros a serem classificados na memória externa e, em seguida, transferir os dados parte por parte para a memória para classificação. Durante o processo de classificação, são necessárias múltiplas trocas entre a memória e o armazenamento externo, e os resultados após a classificação dos registros no arquivo de armazenamento externo ainda são colocados no arquivo original. Este método de classificação é chamado de classificação externa.
A capacidade da memória não pode acomodar grandes quantidades de dados
Como obter o segmento de mesclagem inicial
Classificação por seleção de deslocamento: resolva o problema de colocar segmentos de classificação na memória
Como reduzir o número de mesclagens de vários segmentos de mesclagem
Árvore de mesclagem ideal: número mínimo de mesclagens (número de E/Ss)
Como obter rapidamente a menor palavra-chave para cada mesclagem m-way
Árvore perdedora: reduza o número de comparações
Capítulo 6: Pesquisa
Conceitos básicos de pesquisa e pesquisa sequencial
Definição de pesquisa: o processo de encontrar elementos de dados que atendam a certas condições em um conjunto de dados é chamado de pesquisa
Palavra-chave: um item de dados em um elemento de dados que identifica exclusivamente o elemento
Comprimento médio da pesquisa (ASL: comprimento médio da pesquisa): durante o processo de pesquisa, o comprimento de uma pesquisa refere-se ao número de palavras-chave que precisam ser comparadas, e o comprimento médio da pesquisa é o número médio de comparações de palavras-chave em todos os processos de pesquisa .
A pesquisa sequencial (pesquisa linear) é usada principalmente para pesquisar em tabelas lineares. Começando em uma extremidade da tabela de pesquisa, a tabela de pesquisa é verificada sequencialmente e as palavras-chave verificadas são comparadas com a chave de valor a ser encontrada. Se forem iguais, a pesquisa foi bem-sucedida. Se nenhum elemento de dados igual for encontrado no final da varredura, a pesquisa falhará.
1
2
3
4
A complexidade do tempo é O (n)
meia pesquisa
Ideia de algoritmo:
Primeiro, compare a chave de valor fornecida com a chave do elemento intermediário da tabela. Se forem iguais, a pesquisa será bem-sucedida e o local de armazenamento do elemento será retornado; se não forem iguais, o elemento a ser pesquisado só poderá. estar na primeira metade diferente do elemento intermediário ou na segunda metade. Em seguida, continue a mesma pesquisa dentro do intervalo restrito e repita até que seja encontrado ou seja determinado que o elemento a ser encontrado não existe na tabela, então a pesquisa não será bem-sucedida e uma mensagem de falha na pesquisa será retornada.
Análise de meia pesquisa
Meia árvore de decisão de pesquisa
Para pesquisa binária, o número de comparações é o número de nós passados do nó raiz para o nó.
A altura de uma árvore binária completa com N (N>0) nós é [log2(N 1)] ou [log2N] 1.
A complexidade do tempo é O (logn)
Bloquear pesquisa
A pesquisa de bloco também é chamada de pesquisa de sequência de índice
Ideia de pesquisa de bloco:
① Determine em qual bloco está o valor a ser encontrado (pesquisa pela metade) ② Busca pelo valor a ser buscado no bloco determinado (busca sequencial)
Bloquear análise de pesquisa
Como a pesquisa em bloco realmente realiza duas pesquisas, o comprimento médio da pesquisa de todo o algoritmo é a soma dos comprimentos médios das duas pesquisas. Ou seja, ASL chunking = ASL reduziu pela metade a ordem ASL
Árvore de classificação binária
Uma árvore de pesquisa binária (árvore de pesquisa binária, também chamada de árvore de pesquisa binária) é uma árvore vazia ou uma árvore binária com as seguintes propriedades ①Se a subárvore esquerda não estiver vazia, os valores de todos os nós da subárvore esquerda serão menores que o valor de seu nó raiz. ②Se a subárvore direita não estiver vazia, então os valores de todos os nós da subárvore direita são maiores que o valor de seu nó raiz. ③ Suas subárvores esquerda e direita também são uma árvore de classificação binária.
“A esquerda é pequena e a direita é grande”
Pensamento algorítmico
Devido às características das árvores de classificação binária (subárvore esquerda <nó raiz <subárvore direita), toda vez que você pesquisa uma palavra-chave, você precisa primeiro compará-la com o nó raiz: Se esta palavra-chave for menor que o valor do nó raiz, então a mesma operação de comparação é executada na subárvore esquerda do nó raiz e continua até que a palavra-chave seja encontrada, indicando uma pesquisa bem-sucedida, ou um ponteiro nulo, indicando uma falha na pesquisa . Se esta palavra-chave for maior que o valor do nó raiz, então a mesma operação de comparação é executada na subárvore direita do nó raiz e continua até que a palavra-chave seja encontrada, indicando uma pesquisa bem-sucedida, ou um ponteiro nulo, indicando uma falha na pesquisa .
Encontre códigos de palavras-chave
1
2
Insira o código da palavra-chave
1) Árvore vazia: insira diretamente um novo nó e retorne sucesso 2) A árvore não está vazia: verifique se existem nós com palavras-chave repetidas: ① Existe: Retorna falha na inserção ② Não existe: verifique a relação de tamanho entre o valor do nó raiz e o valor da chave a ser inserido e insira recursivamente as subárvores esquerda e direita.
Construir código
excluir nó
①Os nós folha são excluídos
Método: basta excluir o nó diretamente
② O que é excluído é o nó com apenas a subárvore esquerda ou a subárvore direita.
Método: “Filho herda o legado do pai”
③O que é excluído são os nós que possuem as subárvores esquerda e direita.
Seguindo o tipo ②, um filho “herdará a herança do pai” e o outro filho “se submeterá” a este filho. Método: Encontre o nó predecessor direto ou sucessor direto do nó a ser excluído, substitua o nó a ser excluído por este nó e, em seguida, exclua o nó.
Análise de árvore de classificação binária
A complexidade do tempo de pesquisa é O (n)
Árvore binária balanceada (árvore AVL)
Uma árvore binária balanceada (árvore AVL) é uma árvore de classificação binária especial. O especial é que o valor absoluto da diferença de altura entre as subárvores esquerda e direita não excede 1, e as subárvores esquerda e direita também são uma árvore binária balanceada. .
fator de equilíbrio
Defina a diferença de altura entre a subárvore esquerda e a subárvore direita de um nó como o fator de equilíbrio do nó. Então, o valor do fator de equilíbrio de um nó de árvore binária balanceado só pode ser −1, 0 ou 1.
Ajuste de saldo
O processo de estabelecimento de uma árvore binária balanceada é semelhante ao de uma árvore binária classificada. Ambos começam em uma árvore vazia e inserem nós um após o outro. A diferença é que no processo de estabelecimento de uma árvore binária balanceada, uma vez que a inserção de um nó pode destruir o equilíbrio do nó, é necessário um ajuste de equilíbrio.
Ajuste LL (causado pela inserção de um nó na subárvore esquerda do filho esquerdo)
O fator de equilíbrio do nó raiz da subárvore desbalanceada mínima é 2>0 O fator de equilíbrio de seu nó filho esquerdo é 1>0 Ambos são maiores que 0, então você pode ajustá-lo girando para a direita
"Rotação regular para a direita"
Ajuste RR (causado pela inserção de um nó na subárvore direita do filho certo)
O fator de equilíbrio do nó raiz da subárvore mínima desequilibrada é -2<0 Seu fator de equilíbrio do nó filho direito é -1<0 Ambos são menores que 0, então você pode ajustá-lo virando para a esquerda
"Negativo significa rotação para a esquerda"
Ajuste LR (causado pela inserção de um nó na subárvore direita do filho esquerdo)
Ajuste RL (causado pela inserção de um nó na subárvore esquerda do filho direito)
Primeiro converta localmente para LL ou RR e, finalmente, ajuste
analisar
A profundidade máxima de uma árvore binária balanceada com n nós é O(log2n). Portanto, o comprimento médio de pesquisa de uma árvore binária balanceada é O(log2n).
Árvore B e árvore B
2-3 árvores
A árvore 2-3 é uma árvore de pesquisa multidirecional: 2 e 3 significam que a árvore 2-3 contém dois tipos de nós
1) 2 nós contêm um elemento e dois filhos (ou nenhum filho). ①Os elementos contidos na subárvore esquerda são menores que o valor do elemento do nó, e os elementos contidos na subárvore direita são maiores que o valor do elemento do nó. ②O nó 2 tem dois filhos ou não tem filhos.
2) O nó 3 contém dois elementos, um grande e um pequeno, e três filhos (ou nenhum filho). (Os dois elementos estão organizados em ordem de tamanho) ①A subárvore esquerda contém elementos menores que o valor do elemento menor do nó, a subárvore direita contém elementos maiores que o valor do elemento maior do nó e a subárvore do meio contém elementos entre esses dois valores de elemento. ②O nó 3 tem três filhos ou nenhum filho. Um ou dois filhos não são permitidos.
3) Todos os nós folhas da árvore 2-3 estão no mesmo nível
Árvore 2-3-4
A árvore 2-3-4 também é uma árvore de pesquisa multidirecional: 2, 3 e 4 significam que a árvore 2-3-4 contém três tipos de nós
1) 2 nós contêm um elemento e dois filhos (ou nenhum filho). ①Os elementos contidos na subárvore esquerda são menores que o valor do elemento do nó, e os elementos contidos na subárvore direita são maiores que o valor do elemento do nó. ②O nó 2 tem dois filhos ou não tem filhos.
2) O nó 3 contém dois elementos, um grande e um pequeno, e três filhos (ou nenhum filho). ①A subárvore esquerda contém elementos menores que o valor do elemento menor do nó, a subárvore direita contém elementos maiores que o valor do elemento maior do nó e a subárvore do meio contém elementos entre esses dois valores de elemento. ②O nó 3 tem três filhos ou nenhum filho. Um ou dois filhos não são permitidos.
3) O nó 4 contém três elementos, pequeno, médio e grande, e quatro filhos (ou nenhum filho). ① A subárvore esquerda contém elementos menores que o menor valor do elemento do nó, a segunda subárvore contém elementos maiores que o menor valor do elemento e menores que o valor do elemento intermediário, a terceira subárvore contém elementos maiores que o valor do elemento intermediário e menores que o valor máximo do elemento, certo A subárvore contém elementos maiores que o maior valor do elemento do nó. ②O nó 4 tem quatro filhos ou nenhum filho. Um, dois ou três filhos não são permitidos.
4) Todos os nós folhas da árvore 2-3-4 estão no mesmo nível
Árvore B
A árvore B também é uma árvore de busca multicaminho balanceada. A árvore 2-3 e a árvore 2-3-4 são casos especiais da árvore B. Chamamos o maior número de filhos de um nó na árvore. a ordem da árvore B. Geralmente escrito como m. Uma árvore B de ordem m é uma árvore vazia ou uma árvore m-ária que satisfaz as seguintes características:
1) Cada nó da árvore possui no máximo m subárvores. (Ou seja, contém no máximo palavras-chave m-1) ("Dois ponteiros de subárvore colocam uma palavra-chave")
2) Se o nó raiz não for um nó terminal, existem pelo menos duas subárvores. (pelo menos uma palavra-chave)
3) Todos os nós não-folha, exceto o nó raiz, têm pelo menos ⌈m/2⌉ subárvores. (Ou seja, contém pelo menos ⌈m/2⌉-1 palavras-chave)
4) A estrutura de todos os nós não-folha é a seguinte:
5) Todos os nós folha aparecem no mesmo nível sem informação. (Assim como o nó onde a pesquisa falhou na árvore de julgamento de pesquisa binária)
1. Operação de pesquisa da árvore B
Processo de pesquisa: ① Primeiro compare a chave-chave a ser encontrada com as palavras-chave no nó. Se for igual a uma das palavras-chave, a pesquisa foi bem-sucedida. ② Se não for igual a todas as palavras-chave, verifique em qual intervalo a chave está e pesquise na subárvore apontada pelo ponteiro correspondente. Ex.: Se Key for menor que a primeira palavra-chave K1, pesquise na subárvore apontada pelo ponteiro P0. Se for maior que a última palavra-chave Kn, pesquise na subárvore apontada pelo ponteiro Pn.
2. Operação de inserção da árvore B
Método de divisão: pegue a palavra-chave do meio (⌈n/2⌉) nesta matriz de palavras-chave como o novo nó e, em seguida, use as outras palavras-chave para formar dois nós como filhos esquerdo e direito do novo nó.
3. Operação de exclusão da árvore B
A operação de exclusão na árvore B é semelhante à operação de inserção, mas é um pouco mais complicada. Ela deve fazer com que o número de palavras-chave no nó excluído seja ≥⌈m/2⌉-1, portanto envolverá a "fusão". problema dos nós. Devido às diferentes posições das palavras-chave excluídas, pode ser dividido em duas situações: a palavra-chave está no nó terminal e a palavra-chave não está no nó terminal.
1) Se a palavra-chave excluída estiver no nó terminal (o nó não folha mais baixo): ①O número de palavras-chave no nó é maior que ⌈m/2⌉-1. Nesse caso, a exclusão desta palavra-chave não destruirá os requisitos de definição da árvore B. Portanto, exclua-o diretamente. ② Se o número de palavras-chave em um nó for igual a ⌈m/2⌉-1, e houver nós com um número de palavras-chave maior que ⌈m/2⌉-1 em seus nós irmãos esquerdo e direito, então pegue palavras-chave emprestadas de o estágio de irmão. ③Se o número de palavras-chave em um nó for igual a ⌈m/2⌉-1, e não houver nenhum nó com um número de palavras-chave maior que ⌈m/2⌉-1 em seus nós irmãos esquerdo e direito, a fusão do nó é necessária .
2) Se a palavra-chave excluída não estiver no nó terminal (o nó não folha de nível mais baixo): ela precisa ser convertida primeiro para estar no nó terminal e, em seguida, os métodos correspondentes são considerados de acordo com a situação no nó terminal .
Palavras-chave adjacentes: para uma palavra-chave que não está em um nó terminal, sua palavra-chave adjacente é a palavra-chave com o maior valor em sua subárvore esquerda ou a palavra-chave com o menor valor em sua subárvore direita.
O primeiro caso: existe uma subárvore esquerda ou subárvore direita com um número de palavras-chave maior que ⌈m/2⌉-1. Encontre as palavras-chave adjacentes da palavra-chave na subárvore correspondente e, em seguida, substitua as palavras-chave adjacentes a serem excluídas. .
O segundo caso: o número de palavras-chave nas subárvores esquerda e direita é igual a ⌈m/2⌉-1, então os dois nós da subárvore esquerda e direita são mesclados e, em seguida, as palavras-chave a serem excluídas são excluídas.
Árvore B
Árvore B é uma estrutura de dados comumente usada em bancos de dados e sistemas de arquivos de sistemas operacionais para pesquisa.
A principal diferença entre a árvore B de ordem m e a árvore B de ordem m é: 1) Na árvore B, um nó com n palavras-chave contém apenas n subárvores, ou seja, cada palavra-chave corresponde a uma subárvore enquanto na árvore B, um nó com n palavras-chave contém (n 1) Uma árvore; 2) Na árvore B, o intervalo do número n de palavras-chave em cada nó (nó interno não raiz) é ⌈m/2⌉≤n≤m (nó raiz 1≤n≤m no B-). tree , o intervalo do número n de palavras-chave para cada nó (nó interno não raiz) é ⌈m/2⌉ -1≤n≤m-1 (nó raiz: 1≤n≤m-1). 3) Na árvore B, os nós folha contêm informações e todos os nós não folha servem apenas como índices. Cada item de índice em um nó não folha contém apenas a palavra-chave máxima da subárvore correspondente e um ponteiro para a subárvore. não contém o endereço de armazenamento do registro correspondente à palavra-chave. 4) Na árvore B, os nós folha contêm todas as palavras-chave, ou seja, as palavras-chave que aparecem nos nós não-folha também aparecerão nos nós folha na árvore B, os nós folha contêm palavras-chave e as palavras-chave contidas em outros nós não são; repetido.
tabela hash
Tabela hash: uma estrutura de dados que calcula o endereço da palavra-chave na tabela com base em uma determinada palavra-chave. Em outras palavras, a tabela hash estabelece um relacionamento de mapeamento direto entre palavras-chave e endereços de armazenamento.
Função hash: uma função que mapeia palavras-chave na tabela de pesquisa para o endereço correspondente à palavra-chave, registrada como Hash(key)=Addr.
A função hash pode mapear duas ou mais palavras-chave diferentes para o mesmo endereço, o que é chamado de "colisão". Essas palavras-chave diferentes que colidem são chamadas de sinônimos.
Dicas para construir funções hash:
1) O domínio da função hash deve incluir todas as palavras-chave que precisam ser armazenadas, e o intervalo do domínio de valor depende do tamanho da tabela hash ou do intervalo de endereços.
2) Os endereços calculados pela função hash devem ser distribuídos uniformemente por todo o espaço de endereçamento com igual probabilidade, reduzindo assim a ocorrência de conflitos.
3) A função hash deve ser o mais simples possível e pode calcular o endereço hash correspondente a qualquer palavra-chave em um curto espaço de tempo.
1. Métodos de construção de funções Hash comumente usadas:
1. Método de endereçamento aberto: considere diretamente um valor de função linear da palavra-chave como o endereço hash, e a função hash é H(chave)=a×chave b. Na fórmula, aeb são constantes. Este método é o mais simples de calcular e não causará conflitos
2. Método de divisão com resto: suponha que o comprimento da tabela hash seja m, pegue um número primo p que não seja maior que m, mas mais próximo ou igual a m, e use a seguinte fórmula para converter a palavra-chave em um endereço hash . A função hash é H(chave)=chave % p A chave para o método do resto é escolher p para que cada palavra-chave seja mapeada para qualquer endereço no espaço hash com igual probabilidade após ser convertida por esta função, reduzindo ao máximo a possibilidade de conflitos.
3. Método de análise digital: suponha que a palavra-chave seja um número de base r (como um número decimal) e a frequência de ocorrência de r números em cada posição não seja necessariamente a mesma. A chance de cada número aparecer Se alguns bits estiverem distribuídos de forma desigual e apenas determinados números aparecerem com frequência, então alguns bits com uma distribuição de números mais uniforme devem ser selecionados como endereço hash. Este método é adequado para conjuntos de palavras-chave conhecidos
4. Método do meio quadrado: como o nome sugere, os dígitos do meio do valor quadrado da palavra-chave são considerados o endereço hash. O número específico de bits a serem obtidos depende da situação real. O endereço hash obtido por este método está relacionado a cada bit da palavra-chave, tornando a distribuição do endereço hash mais uniforme.
5. Método de dobramento: divida a palavra-chave em várias partes com o mesmo número de dígitos (o número de dígitos na última parte pode ser menor) e, em seguida, considere a soma da superposição dessas partes como o endereço hash. método de dobramento. Quando há muitos dígitos na palavra-chave e os números de cada dígito na palavra-chave estão distribuídos de maneira aproximadamente uniforme, o método de dobramento pode ser usado para obter o endereço hash.
2. Métodos de tratamento de conflitos para funções Hash comumente usadas:
1. Método de endereçamento aberto: Use o endereço Hash conflitante como uma variável independente e obtenha um novo endereço Hash livre por meio de uma determinada função de resolução de conflitos.
1) Método de detecção linear: Quando ocorre um conflito, verifique a próxima unidade na tabela sequencialmente (quando o endereço no final da tabela m-1 é detectado, o próximo endereço de detecção é o endereço no início da tabela 0) até que uma unidade ociosa seja encontrada (quando a tabela não estiver. Uma unidade livre deve ser encontrada quando estiver cheia) ou a tabela inteira possa ser pesquisada.
2) Método de detecção quadrada: suponha que o endereço conflitante seja d, e a nova sequência de endereços obtida pelo método de detecção quadrada seja d 12, d-12, d 22, d-22... O método de detecção quadrada é a melhor maneira de lidar com conflitos e pode evitar o problema de "empilhamento". Sua desvantagem é que ele não consegue detectar todas as células na tabela hash, mas pode detectar pelo menos metade das células.
3) Método Rehash: também chamado de método de hash duplo. Duas funções hash precisam ser usadas Quando o endereço obtido por meio da primeira função hash H (Chave) entra em conflito, a segunda função hash Hash2 (Chave) é usada para calcular o incremento de endereço da palavra-chave.
4) Método de sequência pseudo-aleatória: Quando ocorre um conflito de endereço, o incremento de endereço é uma sequência numérica pseudo-aleatória, que é chamada de método de sequência pseudo-aleatória.
2. Método Zipper: Diferentes palavras-chave podem ser mapeadas para o mesmo endereço por meio de uma função hash. Para evitar conflitos entre não-sinônimos, todos os sinônimos podem ser armazenados em uma lista vinculada linear. endereço. . O método do zíper é indicado para situações onde as inserções e remoções são frequentes.
3. O processo de busca da tabela hash: semelhante à construção de uma tabela hash, dada uma palavra-chave Key. Primeiro calcule seu endereço hash com base na função hash. Em seguida, verifique se há uma palavra-chave no local do endereço hash. 1) Caso contrário, significa que a palavra-chave não existe e a falha na pesquisa é retornada. 2) Se houver, verifique se o registro é igual à palavra-chave. ①Se for igual à palavra-chave, retorne o sucesso da pesquisa. ② Se não for igual, calcule o próximo endereço hash de acordo com o método de tratamento de conflitos fornecido e, em seguida, use esse endereço para realizar o processo acima.
4. O desempenho de pesquisa da tabela hash: relacionado ao fator de preenchimento.
Quanto maior for α, mais “cheios” serão os registros preenchidos e maior será a possibilidade de conflito. Pelo contrário, menor será a possibilidade de conflito.
Capítulo 5: Imagem
Conceitos básicos de gráficos
definição: Uma árvore é um conjunto finito de N (N≥0) nós. Quando N=0, é chamada de árvore vazia, o que é um caso especial. Em qualquer árvore não vazia deve satisfazer: 1) Existe e existe apenas um nó específico chamado raiz. 2) Quando N>1, os nós restantes podem ser divididos em m (m>0) conjuntos finitos disjuntos T1, T2,..., Tm, cada um dos quais é ele próprio uma árvore e é chamado de subárvore da. nó.
O gráfico G consiste em um conjunto de vértices V e um conjunto de arestas E, denotado como G = (V, E)
V(G) representa um conjunto finito não vazio de vértices no grafo G. Use |V| para representar o número de vértices no grafo G, também chamado de ordem do grafo G.
E(G) representa o conjunto de relacionamentos (arestas) entre vértices no grafo G. Deixe |E| representar o número de arestas no gráfico G.
Classificação
gráfico direcionado
Um conjunto finito de arestas direcionadas (arcos)
Um arco é um par ordenado de vértices
v é a cauda do arco, w é a cabeça do arco
v é adjacente a w ou w é adjacente a v
Gráfico não direcionado
Conjunto finito de arestas não direcionadas
Arestas são pares não ordenados de vértices
(v, w)
(v,c)=(c,v)
w e v são pontos adjacentes entre si
diagrama simples
1. Não há aresta do vértice para ele mesmo.
2. A mesma borda não aparece repetidamente
vários gráficos
Se houver mais de uma aresta entre dois nós no grafo G, os vértices podem ser associados a si mesmos através da mesma aresta.
gráfico completo
gráfico completo não direcionado
Se existe uma aresta entre quaisquer dois vértices
Gráfico completo direcionado
Se houver dois arcos em direções opostas entre quaisquer dois vértices
subtrama
Gráfico conectado: quaisquer dois vértices no gráfico estão conectados
Componentes conectados: subgráficos conectados máximos em gráficos não direcionados
conectado
Existe um caminho do vértice A ao vértice B
ótimo
1. Existem vértices suficientes
2. Um subgrafo conectado máximo contém todas as arestas anexadas a esses vértices.
Como encontrar componentes conectados: Comece selecionando um vértice, use este vértice como um subgrafo e, em seguida, adicione vértices e arestas conectadas a este subgrafo, um por um, até que todos os vértices conectados sejam adicionados ao subgrafo.
Conclusão 1: Se um grafo tiver n vértices e menos de n-1 arestas, então o grafo deve ser um grafo desconectado.
Fortemente conectado: Existem caminhos do vértice V ao vértice W e do vértice W ao vértice V.
Gráfico fortemente conectado: qualquer par de vértices no gráfico está fortemente conectado
Árvore geradora de um grafo conectado: um subgrafo conectado mínimo que contém todos os n vértices do grafo, mas apenas n-1 arestas.
Conclusão 2: Remover uma aresta de uma árvore geradora resultará em um gráfico não conectado e adicionar uma aresta formará um ciclo.
Grau: o número de arestas com este vértice como ponto final
O grau de um vértice V em um gráfico não direcionado refere-se ao número de arestas anexadas ao vértice, registrado como TD(v)
O grau do vértice V em um gráfico direcionado é dividido em grau externo e grau interno
Indegree (ID) é o número de arestas direcionadas que terminam no vértice v
Out-degree (OD) é o número de arestas direcionadas começando no vértice V
Caminho simples e circuito simples: Um caminho cujos vértices não aparecem repetidamente é chamado de caminho simples. Para um loop, um loop no qual os vértices não aparecem repetidamente, exceto o primeiro e o último vértice, é chamado de loop simples.
Rede Quanhe: Cada aresta do gráfico recebe um determinado valor no vestibular de pós-graduação. Esse valor é chamado de peso dessa aresta. O gráfico ponderado é chamado de gráfico ponderado, também chamado de rede.
Caminho e comprimento do caminho: O caminho entre os vértices p a q refere-se à sequência de vértices que está armazenada, p, a, b, c, d,...q. O número acima do caminho é o comprimento do caminho
Loop (anel): Um caminho cujo primeiro e último vértices são iguais é chamado de loop ou loop
Distância: O comprimento do caminho mais curto do vértice u até v. Se não houver caminho, é infinito.
Estrutura de armazenamento de gráfico
Matriz de adjacência (armazenada sequencialmente)
Lista de adjacências (armazenamento vinculado)
Lista vinculada cruzada (gráfico direcionado)
Lista múltipla de adjacência (gráfico não direcionado)
Percurso gráfico
primeira travessia em profundidade
Pesquisa em profundidade (DFS: Pesquisa em profundidade): A pesquisa em profundidade é semelhante ao algoritmo de passagem de pré-ordem de uma árvore
Complexidade de espaço: como o DFS é um algoritmo recursivo, a recursão requer uma pilha de trabalho para auxiliar o trabalho. No máximo, todos os vértices do gráfico precisam ser colocados na pilha, então a complexidade de tempo é O(|V|)
Complexidade de tempo: 1) Lista de adjacências: A principal operação do processo de travessia é percorrer seus pontos adjacentes para um vértice. Como os pontos adjacentes são encontrados acessando a tabela de arestas, a complexidade de tempo é O(|E|), e a complexidade de tempo é O(|E|). o tempo para acessar os vértices é O. (|V|), então a complexidade de tempo total é O(|V| |E|) 2) Matriz de adjacência: A complexidade de tempo para encontrar os pontos adjacentes de cada vértice é O(|V|), e cada vértice é pesquisado, então a complexidade de tempo total é O(|V|2)
travessia em largura
Pesquisa em amplitude (BFS: Pesquisa em amplitude): A pesquisa em amplitude é semelhante ao algoritmo de passagem de ordem de nível de uma árvore
Complexidade de espaço: o BFS precisa usar uma fila e n vértices precisam ser enfileirados uma vez. Portanto, no pior caso, se n vértices estiverem na fila, será necessária uma complexidade de espaço de O(|V|).
complexidade de tempo: 1) Lista de adjacências: Cada vértice é inserido na fila uma vez, e a complexidade de tempo é O(|V|). Para cada vértice, a busca por seus pontos adjacentes requer a visita a todas as arestas deste vértice, então a complexidade de tempo é O. ( |E|). Portanto, a complexidade total do tempo é O(|V| |E|) 2) Matriz de adjacência: Cada vértice é inserido na fila uma vez, e a complexidade de tempo é O(|V|). Para cada vértice, a busca por seus pontos adjacentes requer percorrer uma linha da matriz, então a complexidade de tempo é O(). |V |), então a complexidade de tempo total é O(|V|2)
Aplicação de diagramas
árvore geradora mínima
prlm
① Encontre o primeiro vértice inicial v0 do gráfico como o primeiro vértice da árvore geradora e, em seguida, selecione a aresta com o menor peso de todas as arestas deste vértice para outros vértices. Em seguida, adicione o outro vértice v desta aresta e esta aresta à árvore geradora.
② Para todos os outros vértices restantes, verifique se os pesos desses vértices e do vértice v são menores que os pesos correspondentes desses vértices na matriz de baixo custo. Se menor, atualize a matriz de baixo custo com pesos menores.
③Continue selecionando a aresta com o menor peso e não na árvore geradora da matriz de baixo custo atualizada e, em seguida, adicione-a à árvore geradora.
④ Repita ②③ até que todos os vértices sejam adicionados à árvore geradora.
Em um loop duplo, o número de vezes do loop externo é n-1 e o número de vezes dos dois loops internos em paralelo é n. Portanto, a complexidade de tempo do algoritmo de Prim é O(n2) Além disso, a complexidade do tempo está relacionada apenas a n, portanto é adequada para gráficos densos.
Kruskal
Organize as arestas no gráfico de acordo com seus pesos, de pequeno a grande, em seguida, digitalize a partir da menor aresta e defina um conjunto de arestas para registrar. Se a aresta não formar um loop, a aresta será mesclada na árvore geradora atual. . Até que todas as bordas tenham sido detectadas.
A operação do algoritmo de Kruskal é dividida na parte de classificação de peso das arestas e um único loop for. Eles estão em um relacionamento paralelo. Como a classificação leva mais tempo do que o loop único, o tempo principal do algoritmo de Kruskal é gasto na classificação. A classificação está relacionada ao número de arestas no gráfico, portanto é adequada para gráficos esparsos
caminho mais curto
Dijkstra
O caminho mais curto de um ponto de origem até os vértices restantes
Este algoritmo define um conjunto S para registrar os vértices do caminho mais curto obtido. Ele pode ser implementado por um array s[], inicializado em 0. Quando s[vi]=1, significa que o vértice vi é colocado. em S. Inicialmente, o ponto de origem v0 e coloque-o em S. Além disso, duas matrizes auxiliares são instaladas durante a construção: dist[]: registra o comprimento do caminho mais curto atual do ponto de origem v0 até outros vértices. O valor inicial de dist[i] é arcs[v0][i]. path[]: path[i] representa o nó predecessor do caminho mais curto do ponto de origem ao vértice i. No final do algoritmo, o caminho mais curto do ponto de origem v0 ao vértice vi pode ser rastreado com base em seu valor. Suponha que comece no vértice 0, ou seja, o vértice 0 é o ponto de origem. O conjunto S inicialmente contém apenas o vértice 0. Os arcos da matriz de adjacência representam o grafo direcionado ponderado e os arcos[i][j] representam o peso da aresta direcionada. <i,j> Valor, se não houver aresta direcionada <i, j>, então arcs[i][j] é ∞. As etapas do algoritmo de Dijkstra são as seguintes: 1) Inicialização: O conjunto S é inicialmente {0}, o valor inicial de dist[] é dist[i]=arcs[0][i], i=1, 2,...,n-1. 2) Encontre o valor mínimo dist[j] em dist[] e adicione o vértice j ao conjunto S, ou seja, modifique s[vj]=1. 3) Modifique o comprimento do caminho mais curto de v0 para qualquer vértice vk no conjunto V-S: se dist[j] arcs[j][k]< dist[k], então seja dist[k]=dist[j] arcs [j][k]. Além disso, atualize path[k]=j (ou seja, após o vértice j ser adicionado ao conjunto, se houver um novo caminho que torne o caminho para o vértice k mais curto, o comprimento do caminho para o vértice k será modificado para um mais curto) 4) Repita as operações 2) a 3) um total de n-1 vezes até que todos os vértices estejam incluídos em S.
Freud
O caminho mais curto de todos os vértices para todos os vértices
Ideia algorítmica: A recursão produz uma sequência de matriz quadrada de n ordem A(−1), A(0),…,A(k),…,A(n−1) Entre eles, A(k)[i][j] representa o comprimento do caminho do vértice vi ao vértice vj, e k representa a etapa da operação de contornar o k-ésimo vértice. Inicialmente, para quaisquer dois vértices vi e vj, se houver uma aresta entre eles, o peso nesta aresta é usado como o menor comprimento do caminho entre eles, se não houver uma aresta direcionada entre eles, ∞ é usado como o menor comprimento do caminho; entre eles. No futuro, tentaremos gradualmente adicionar o vértice k (k=0, 1, ..., n-1) como um vértice intermediário no caminho original. Se após adicionar vértices intermediários o comprimento do caminho obtido for menor que o caminho original, substitua o caminho original por este novo caminho.
Gráfico não ponderado
O caminho com o menor número de arestas entre dois pontos
gráfico ponderado
O caminho entre dois pontos que tem a menor soma dos pesos das arestas
classificação topológica
AOV
Se considerarmos cada link como um vértice no grafo, em tal grafo direcionado, usando vértices para representar atividades e arcos para representar as relações de prioridade entre atividades, então tal grafo direcionado é chamado de rede AOV (Activity On Vertex).
A classificação topológica é o processo de construção de uma sequência topológica para um grafo direcionado. A construção terá dois resultados: Se todos os vértices deste gráfico forem gerados, significa que é uma rede AOV sem loops; Se todos os vértices não forem gerados, significa que há um loop neste gráfico e não é uma rede AOV.
Algoritmo de classificação topológica: Selecione um vértice com grau de entrada 0 da rede AOV para saída, exclua esse vértice e exclua o arco com esse vértice como a cauda do arco. Repita esta etapa até que todos os vértices no gráfico de saída sejam gerados ou nenhum vértice com grau 0 seja encontrado.
Caminho crítico
AOE (Activity On Edge): Em um gráfico direcionado ponderado que representa um projeto, vértices são usados para representar eventos, arestas direcionadas são usadas para representar atividades e pesos nas arestas são usados para representar a duração das atividades direcionadas. gráfico A rede que representa a atividade é chamada de rede AOE.
Capítulo 1: Estrutura de Dados conceito básico
definição
Em qualquer problema, os elementos de dados não existem isoladamente, mas existe uma certa relação entre eles. Essa relação entre os elementos de dados é chamada de estrutura. Uma estrutura de dados é uma coleção de elementos de dados que possuem um ou mais relacionamentos específicos entre si. A estrutura de dados inclui três aspectos: estrutura lógica, estrutura de armazenamento e operação de dados. A estrutura lógica e a estrutura de armazenamento de dados são dois aspectos inseparáveis. O design de um algoritmo depende da estrutura lógica selecionada, e a implementação do algoritmo depende da estrutura de armazenamento utilizada.
estrutura lógica
A estrutura lógica refere-se ao relacionamento lógico entre os elementos de dados, ou seja, a descrição dos dados em termos de relacionamentos lógicos. Não tem nada a ver com armazenamento de dados e é independente do computador
A estrutura lógica dos dados é dividida em estrutura linear e estrutura não linear
Não há outra relação entre os elementos de dados na estrutura do conjunto além da relação de “pertencer ao mesmo conjunto”. Semelhante a um conjunto matemático
Estrutura linear Existe apenas um relacionamento um-para-um entre os elementos de dados na estrutura. Como filas
Estrutura em árvore Existe um relacionamento um-para-muitos entre os elementos de dados na estrutura. Como genealogia familiar
Estrutura gráfica ou estrutura de rede Existe um relacionamento muitos para muitos entre os elementos de dados na estrutura. Como mapa
Estrutura física
Estrutura de armazenamento refere-se à representação da estrutura de dados no computador (também chamada de imagem), também chamada de estrutura física. Inclui a representação de elementos de dados e a representação de relacionamentos. A estrutura de armazenamento de dados é a realização da estrutura lógica em linguagem de computador, que depende da linguagem de computador. As estruturas de armazenamento de dados incluem principalmente: armazenamento sequencial, armazenamento em cadeia, armazenamento de índice e armazenamento de hash.
Armazenamento sequencial: Os locais físicos de armazenamento são adjacentes. (p.s. A localização física é a localização das informações no computador.)
Armazenamento vinculado: Os locais físicos de armazenamento podem não ser adjacentes. Os elementos adjacentes são encontrados registrando-se os locais físicos dos elementos adjacentes.
Armazenamento de índice: semelhante a um diretório, você pode entrar em contato com o capítulo do sistema de arquivos do sistema operacional para entendê-lo mais tarde.
Armazenamento de hash: calcule diretamente o endereço físico do elemento por meio de palavras-chave (explicadas em detalhes posteriormente).
Cinco características dos algoritmos
1. Finitude: termina após um número finito de etapas
2. Certeza: não há ambiguidade, ou seja, não há ambiguidade
3. Viabilidade: Por exemplo, limitados pelo poder computacional dos computadores, alguns algoritmos, embora teoricamente viáveis, não podem ser concluídos na prática.
4. Entrada: Vários tipos de dados que podem ser processados pelo computador, como números, áudio, imagens, etc.
5. Saída: um ou mais resultados de saída do programa.
complexidade do algoritmo
complexidade de tempo:
• É utilizado para medir a rapidez com que o tempo de execução do algoritmo aumenta à medida que o tamanho do problema aumenta;
• É uma função do tamanho do problema: T(n) é uma função da escala de tempo. A complexidade do tempo analisa principalmente a ordem de grandeza de T(n).
• T(n)=O(f(n)) f(n) é a frequência das operações básicas no algoritmo. Geralmente, consideramos a complexidade de tempo no pior caso.
Complexidade do espaço:
• É utilizado para medir a velocidade do espaço requerido pelo algoritmo à medida que o tamanho do problema aumenta;
• É uma função do tamanho do problema: S(n)=O(g(n)); a taxa de crescimento do espaço requerido pelo algoritmo é igual à taxa de crescimento de g(n).
Concentre-se no cálculo da complexidade
Relacionamentos de complexidade de tempo comumente usados:
Como calcular a complexidade
Cálculo de complexidade de tempo (corpo de loop único)
Concentre-se diretamente no número de execuções do corpo do loop, definido como k
Cálculo de complexidade de tempo (vários corpos de loop)
Duas regras de operação: regra de multiplicação e regra de adição.
Capítulo 2: Tabela linear
A estrutura lógica de uma tabela linear
Definição: Uma tabela linear é uma sequência finita de n (n≥0) elementos de dados do mesmo tipo de dados. Onde n é o comprimento da tabela. Quando n = 0, a tabela linear é uma tabela vazia
Recursos: O primeiro elemento da lista linear é chamado de elemento de cabeçalho; Exceto o primeiro elemento, cada elemento possui exatamente um antecessor direto. Cada elemento, exceto o último elemento, tem exatamente um sucessor direto.
Estrutura de armazenamento sequencial de tabela linear
O armazenamento sequencial de tabelas lineares também é chamado de tabelas sequenciais. Ele utiliza um conjunto de unidades de armazenamento com endereços consecutivos (como arrays em linguagem C) para armazenar elementos de dados em uma tabela linear em sequência, tornando assim a lógica Dois elementos que são editorialmente adjacentes também são fisicamente adjacentes.
Três atributos para criar uma tabela de sequência: 1. A posição inicial do espaço de armazenamento (dados do nome da matriz) 2. Capacidade máxima de armazenamento da tabela de sequência (MaxSize) 3. O comprimento atual da tabela de sequência (comprimento)
Na verdade, os arrays também podem alocar espaço dinamicamente. O espaço para armazenar arrays é alocado por meio de instruções de alocação dinâmica de armazenamento durante a execução do programa.
Resumir:
1. A principal característica da tabela de sequências é o acesso aleatório (baseado em arrays em linguagem C), ou seja, o elemento especificado pode ser encontrado em tempo O(1) através do primeiro endereço e número de série do elemento.
2. A densidade de armazenamento da tabela de sequência é alta e cada nó armazena apenas elementos de dados. Não há necessidade de gastar espaço nos elementos da tabela para estabelecer relações lógicas entre eles (devido às características de localização física adjacente)
3. Os elementos logicamente adjacentes na tabela de sequência também são fisicamente adjacentes, portanto, as operações de inserção e exclusão exigem a movimentação de um grande número de elementos.
Operações de tabela de sequência
1.Inserir
Ideia de algoritmo:
1. Determine se o valor de i está correto
2. Determine se o comprimento da tabela excede o comprimento da matriz
3. De trás para frente até a i-ésima posição, mova cada um desses elementos uma posição para trás.
4. Insira o elemento na posição i e modifique o comprimento da tabela
código
analisar:
Melhor caso: inserindo no final da tabela (ou seja, i=n 1), a instrução de movimentação do elemento não será executada e a complexidade de tempo é O(1).
Pior caso: inserindo no topo da tabela (ou seja, i=1), a instrução de movimentação do elemento será executada n vezes, a complexidade do tempo é O(n).
Caso médio: suponha que pi (pi=1/(n 1)) seja inserido na i-ésima posição A probabilidade de um nó e, em seguida, insira um nó em uma lista linear de comprimento n O número médio de vezes que um nó precisa ser movido é
2.Excluir
Ideia de algoritmo:
1. Determine se o valor de i está correto
2. Obtenha o elemento excluído
3. Mova todos os elementos após o elemento excluído para frente uma posição em sequência.
4. Modifique o comprimento da tabela
código
analisar
Melhor cenário: exclua o elemento no final da tabela (ou seja, i = n) sem mover o elemento e a complexidade do tempo é O (1).
Pior cenário: a exclusão do elemento do cabeçalho (ou seja, i=1) requer a movimentação de todos os elementos, exceto o primeiro elemento, e a complexidade do tempo é O(n).
Situação média: assumindo que pi (pi = 1/n) é a probabilidade de excluir o nó na i-ésima posição, então o número médio de vezes que o nó precisa ser movido ao excluir um nó em uma lista linear de comprimento n é
Estrutura de armazenamento vinculada de tabela linear
O armazenamento vinculado de tabelas lineares refere-se ao armazenamento de elementos de dados em tabelas lineares por meio de um conjunto de unidades de armazenamento arbitrárias.
Qual é a diferença entre o nó principal e o ponteiro principal?
Independentemente de haver um nó principal ou não, o ponteiro principal sempre aponta para o primeiro nó da lista vinculada, e o nó principal é o primeiro nó na lista vinculada de nós principais. Nenhuma informação geralmente é armazenada no nó.
Por que definir o nó do cabeçalho?
1. É fácil de processar e operar. Por exemplo, as operações de inserção de um nó antes do nó do primeiro elemento e exclusão do primeiro nó são unificadas com as operações de outros nós.
2. Independentemente de a lista vinculada estar vazia ou não, seu ponteiro principal é um ponteiro não nulo apontando para o nó principal, de modo que o processamento de listas vazias e listas não vazias é unificado.
Operações de lista vinculada única
1. Crie uma lista vinculada individualmente usando o método de inserção de cabeçalho:
Crie um novo nó, aloque espaço de memória e insira o novo nó no topo da lista vinculada atual.
código
2. Crie uma lista vinculada individualmente usando o método de inserção final:
Crie um novo nó, aloque espaço de memória e insira o novo nó no final da lista vinculada atual.
código
3. Encontre nós por número de série
Começando no primeiro nó da lista vinculada individualmente, pesquise o próximo campo um por um até que o i-ésimo nó seja encontrado, caso contrário, NULL será retornado no último campo de ponteiro do nó.
código
4. Encontre nós por valor
Começando no primeiro nó da lista vinculada individualmente, compare os valores dos campos de dados de cada nó na lista, do início ao fim. Se o valor do campo de dados de um nó for igual ao valor fornecido e, então. retornar o ponteiro do nó; se toda a lista vinculada única Se não houver tal nó na lista vinculada, NULL será retornado.
código
5. inserir
A operação de inserção consiste em inserir um novo nó com valor x na i-ésima posição da lista vinculada individualmente. Primeiro verifique a legalidade da posição de inserção, depois encontre o nó predecessor da posição a ser inserida, ou seja, o i-1º nó, e depois insira o novo nó depois dele.
Ideia de algoritmo: 1. Obtenha o ponteiro para o nó predecessor da posição de inserção ①p=GetElem(L,i-1); 2. Deixe o campo ponteiro do novo nó *s apontar para o nó sucessor de *p ② s->próximo=p->próximo; 3. Deixe o campo ponteiro do nó *p apontar para o nó *s recém-inserido ③ p->próximo=s;
6． excluir
A operação de exclusão consiste em excluir o i-ésimo nó da lista vinculada individualmente. Primeiro verifique a legalidade da posição excluída, depois procure o i-1º nó na tabela, que é o nó predecessor do nó excluído, e então exclua-o.
Ideia de algoritmo: 1. Obtenha o ponteiro para o nó predecessor da posição excluída p=GetElem(L,i-1); 2. Obtenha o ponteiro para a posição excluída q=p->next; 3. O sucessor do nó apontado por p aponta para o sucessor do nó excluído p->next=q->next 4. Libere e exclua o nó free(q);
Lista duplamente vinculada
definição
1. Inserir: (o método não é único) ① s->próximo=p->próximo; ② p->próximo->anterior=s; ③ s->anterior=p; ④ p->próximo=s;
2. Excluir: ① p->próximo=q->próximo; ② q->próximo->anterior=p; ③ grátis (q);
Lista vinculada circular e lista vinculada estática
Lista circular vinculada individualmente: A diferença entre uma lista circular vinculada individualmente e uma lista vinculada individualmente é que o ponteiro do último nó da lista não é NULO, mas aponta para o nó principal, de modo que toda a lista vinculada forma um anel .
Lista duplamente vinculada cíclica: Análoga à lista cíclica simplesmente vinculada, a lista cíclica duplamente vinculada difere da lista duplamente vinculada porque os nós iniciais e finais formam um anel.
Quando a lista circular duplamente vinculada é uma lista vazia, o campo anterior e o próximo campo de seu nó principal são ambos iguais a Cabeça.
Lista vinculada estática: a lista vinculada estática é uma estrutura de armazenamento vinculada que usa uma matriz para descrever uma lista linear.
O primeiro elemento do array não armazena dados, seu campo ponteiro armazena o índice do array onde o primeiro elemento está localizado. O valor do campo ponteiro do último elemento da lista vinculada é -1.
exemplo
Capítulo 3: Pilhas e Filas
pilha
Pilha: Uma lista linear que permite apenas operações de inserção ou exclusão em uma extremidade.
Topo da pilha (Top): O final da lista linear que permite inserção e exclusão.
Inferior: Fixo, a outra extremidade que não permite inserção e exclusão
Características: 1. A pilha é uma lista linear restrita, então naturalmente tem um relacionamento linear Gravata. 2. Os elementos da pilha que entram depois devem sair primeiro, ou seja, último a entrar, primeiro a sair. LIFO (último a entrar, primeiro a sair)
Os elementos da pilha avançam para trás Quem vai deve sair primeiro Venha, último a entrar, primeiro a entrar Saída LIFO (último a entrar Primeiro a sair)
pilha de sequência
A pilha é um caso especial de tabelas lineares, e o armazenamento sequencial da pilha também é uma simplificação do armazenamento sequencial de tabelas lineares. A estrutura de armazenamento sequencial da pilha também é chamada de pilha sequencial.
Operações de pilha sequenciais
1. Breve julgamento:
2. Empurre para a pilha:
3. Saia da pilha:
4. Leia o elemento superior da pilha:
pilha compartilhada
O tamanho do espaço de armazenamento da pilha sequencial precisa ser alocado antecipadamente. Em muitos casos, a taxa de utilização de abertura separada do espaço de armazenamento para cada pilha não é tão boa quanto o compartilhamento do espaço de armazenamento de cada pilha.
Diagrama esquemático
Estrutura de pilha compartilhada
Operações de pilha compartilhada: (empurrar para a pilha)
pilha de corrente
A pilha é um caso especial de lista linear. A estrutura de armazenamento de uma lista linear também possui uma estrutura de armazenamento vinculada, portanto a pilha também pode ser implementada na forma de uma lista vinculada. A estrutura de armazenamento em cadeia da pilha também é chamada de pilha em cadeia.
Características 1. A pilha da cadeia geralmente não fica cheia. 2. A condição de julgamento para uma pilha vazia geralmente é definida como top==NULL;
estrutura
Operações de pilha de cadeia
1. Empurre para a pilha
2. Saia da pilha
fila
Uma fila é uma lista linear que permite apenas inserções em uma extremidade e exclusões na outra.
Frente: A extremidade que permite a exclusão, também conhecida como frente.
Traseira: A extremidade que permite a inserção.
O elemento que entra primeiro na fila deve sair primeiro da fila, ou seja, First In First Out (FIFO).
fila sequencial
Para implementar uma fila usando um array, você pode colocar o início da fila no índice 0 do array.
fila circular
"Dobre" a matriz para formar um anel. Quando o ponteiro traseiro atinge a posição do subscrito 4, ele pode continuar apontando de volta para a posição do subscrito 0. Dessa forma, a fila armazenada em ordem conectada ponta a ponta é chamada de fila circular.
Enfileirar: traseira=(traseira 1)%MaxSize
Desenfileirar: front=(front 1)%MaxSize
Então, como saber se a fila está vazia ou cheia?
Método 1: Defina o sinalizador flag Quando flag=0 e rear é igual a front, a fila está vazia. Quando flag=1 e rear é igual a front, a fila está cheia.
Método 2: Usamos front=traseiro apenas como condição de julgamento para que a equipe esteja vazia. Quando a fila está cheia, ainda há uma unidade livre no array. Achamos que esta situação ocorre quando a fila está cheia.
Operações de fila circular
1. Junte-se à equipe:
2. Saia da equipe:
fila encadeada
A estrutura de armazenamento vinculada da fila é, na verdade, uma lista vinculada individualmente de uma lista linear, mas precisa ser restrita. Os elementos só podem ser inseridos no final da tabela e excluídos do cabeçalho.
Para facilitar a operação, definimos o ponteiro principal da equipe e o ponteiro final da equipe, respectivamente. O ponteiro principal da equipe aponta para o nó principal e o ponteiro final da equipe aponta para o nó final.
Operações de fila encadeada
1. Entrando na fila: Sabemos que a fila só pode inserir elementos do final da fila e excluir elementos do início da fila. Portanto, ingressar na fila significa inserir o nó no ponteiro final da fila. A operação de inserção da fila em cadeia é igual à operação de inserção da lista vinculada individualmente.
2. Dequeue: Dequeue é retirar da fila o nó sucessor do nó principal e, em seguida, alterar o sucessor do nó principal para o nó atrás dele.
deque
Uma fila dupla refere-se a uma fila que permite que ambas as extremidades executem operações de enfileiramento e desenfileiramento.
aplicação de pilha
1. Correspondência de colchetes: suponha que haja dois tipos de colchetes, um redondo () e um quadrado [].
Ideia de algoritmo: se for um colchete esquerdo, coloque-o na pilha; se for um colchete direito, retire um colchete esquerdo da pilha para determinar se ele corresponde quando o final da string for detectado, verifique se a pilha; está vazia. Enquanto a pilha estiver vazia, toda a string ficará entre colchetes.
código
2. Avaliação de expressão:
Regras: Digitalize cada número e símbolo da expressão da esquerda para a direita. Quando um número é encontrado, ele é colocado na pilha. Quando um símbolo é encontrado, os dois números no topo da pilha são retirados da pilha. então a operação é executada no símbolo. Finalmente, o resultado da operação é colocado na pilha, até que o resultado final seja obtido.
Como converter uma expressão infixa em uma expressão pós-fixada?
1. Adicione colchetes a todos os operadores e seus operandos de acordo com a precedência do operador. (Não há necessidade de adicionar colchetes originais)
2. Mova o operador após os parênteses correspondentes.
3. Remova os parênteses.
exemplo
3. Recursão:
Para entender a recursão, você deve primeiro entender a recursão até poder entendê-la. Se ele próprio for usado na definição de uma função, procedimento ou estrutura de dados, então a função, procedimento ou estrutura de dados será definida recursivamente, ou recursivamente, para abreviar. A coisa mais importante sobre a recursão é a fórmula da recursão e o limite da recursão.
1. Fatorial
Complexidade de tempo: O(NlogN)
2. Sequência de Fibonacci
Complexidade de tempo O (2 ^ n)
Capítulo 4: Árvore
Conceitos básicos de árvores
Uma árvore é uma estrutura definida recursivamente
Nó
Nó raiz: a árvore possui apenas um nó raiz
Grau do nó: o número de subárvores pertencentes ao nó
O grau é 0: nó folha ou nó terminal
O grau não é 0: nó ramificado ou nó não terminal
Os nós de ramificação também são chamados de nós internos, exceto o nó raiz.
Grau da árvore: o grau máximo de todos os nós da árvore
Relacionamento de nó
nó ancestral
Qualquer nó com o caminho exclusivo do nó raiz até este nó
Nó descendentes
nó pai
O nó mais próximo do nó no único caminho do nó raiz para o nó
nó filho
Nó irmão
Nós com o mesmo nó pai
Nível, altura, profundidade, altura da árvore
Nível: A raiz é o primeiro nível, seus filhos são o segundo nível e assim por diante.
Profundidade do nó: começando no nó raiz e acumulando de cima para baixo
A altura do nó: os nós folhas começam a se acumular de baixo para cima.
Altura da árvore (profundidade): o número máximo de níveis de nós na árvore
natureza da árvore
1. O número de nós na árvore é igual ao grau de todos os nós mais 1.
Prova: Não é difícil imaginar que, com exceção do nó raiz, cada nó possui e possui apenas um nó predecessor apontando para ele. Ou seja, cada nó tem uma correspondência biunívoca com o ramo que aponta para ele. Suponha que haja b ramos na árvore, então, além do nó raiz, a árvore inteira contém b nós, então o número de nós na árvore inteira é b nós mais o nó raiz, definido como n, então n = b 1. O número do ramo b também é o grau de todos os nós. A prova está concluída.
2. Existem no máximo m^(i−1) nós no i-ésimo nível de uma árvore com grau m (i≥1).
Prova: (indução matemática) Primeiro considere o caso de i=1: o primeiro nível possui apenas o nó raiz, ou seja, um nó, e i=1 é trazido para a equação para satisfazê-lo. Supondo que a i-1ª camada satisfaça esta propriedade, a i-1ª camada possui no máximo m i-2 nós. …………………. camada i-1 ……… E como o grau da árvore é m, para cada nó no nível i-1, no máximo Existem m nós filhos. Portanto, o número de nós na camada i é no máximo m na camada i-1. vezes, então há no máximo m ^ (i-1) nós na i-ésima camada.
3. Uma árvore m-ária com altura h tem no máximo (m^h-1)/(m-1) nós.
4. A altura mínima de uma árvore m-ária com n nós é logm(n(m-1) 1)
estrutura de armazenamento de árvore
estrutura de armazenamento sequencial
Representação pai: Use um conjunto de espaços de armazenamento contínuo para armazenar os nós da árvore e, ao mesmo tempo, em cada nó, use uma variável para armazenar a posição do nó pai do nó na matriz.
estrutura de armazenamento em cadeia
Representação filho: organize os nós filhos de cada nó e armazene-os em uma lista vinculada individualmente. Portanto, existem n listas vinculadas para n nós; Se for um nó folha, então a lista vinculada individualmente de filhos desse nó estará vazia; Em seguida, os ponteiros principais de n listas vinculadas individualmente são armazenados em uma tabela de sequência (matriz).
Representação do irmão filho: Como o nome indica, é para armazenar o filho e os irmãos do nó filho. Especificamente, é para definir dois ponteiros para apontar para o nó, respectivamente. O primeiro nó filho do ponto e o nó irmão direito deste nó filho.
Árvore binária
definição
Uma árvore binária é um conjunto finito de n (n≥0) nós: ① Ou é uma árvore binária vazia, ou seja, n=0. ② Ou consiste em um nó raiz e duas subárvores esquerdas disjuntas chamadas raízes. e a subárvore certa. A subárvore esquerda e a subárvore direita são, cada uma, uma árvore binária.
1. Cada nó possui no máximo duas subárvores.
2. As subárvores esquerda e direita estão em ordem
Cinco formas básicas de árvores binárias:
1. Árvore vazia
2. Existe apenas um nó raiz
3. O nó raiz possui apenas a subárvore esquerda
4. O nó raiz possui apenas a subárvore correta
5. O nó raiz possui subárvores esquerda e direita
árvore binária especial
1. árvore inclinada
2. Árvore binária completa:
3. Árvore binária completa
Propriedades de árvores binárias
1. O número de nós folha em uma árvore binária não vazia é igual ao número de nós com grau 2 mais 1.
2. Existem no máximo 2 ^ k-1 nós no nível K de uma árvore binária não vazia (K≥1)
3. Uma árvore binária com altura H tem no máximo 2^H-1 nós (H≥1)
4. A altura de uma árvore binária completa com N (N>0) nós é [log2(N 1)] ou [log2N] 1.
Estrutura de armazenamento de árvore binária
armazenamento sequencial
A estrutura de armazenamento sequencial de uma árvore binária consiste em usar um conjunto de unidades de armazenamento com endereços consecutivos para armazenar os elementos do nó na árvore binária completa, de cima para baixo e da esquerda para a direita.
armazenamento em cadeia
Cada nó de uma árvore binária tem no máximo dois filhos, portanto, ao projetar a estrutura do nó de uma árvore binária, considere dois ponteiros apontando para os dois filhos do nó.
Travessia de árvore binária
Passagem de pré-encomenda: 1) Acesse o nó raiz; 2) Percorra a subárvore esquerda em ordem; 3) Percorra a subárvore direita em ordem.
recursão
não recursivo
Percurso em ordem: 1) Percurso em ordem da subárvore esquerda; 2) Acesse o nó raiz; 3) Percorra em ordem a subárvore direita.
recursão
não recursivo
Travessia pós-ordem: 1) Percurso pós-ordem da subárvore esquerda; 2) Percurso pós-ordem da subárvore direita; 3) Visite o nó raiz.
recursão
não recursivo
Passagem de nível: Se a árvore estiver vazia, não faça nada e retorne diretamente. Caso contrário, o acesso começa no primeiro nível da árvore, percorre nível por nível de cima para baixo e, no mesmo nível, acessa os nós um por um, da esquerda para a direita.
pista de árvore binária
Uma lista vinculada binária de N nós. Cada nó possui links apontando para seus filhos esquerdo e direito. Ponteiros de nó, portanto, há 2N ponteiros no total e o binário de N nós A árvore tem um total de N-1 ramos, o que significa que há 2N-(N-1)=N 1 ponteiros nulos. Por exemplo, se houver 6 nós na árvore binária à esquerda, então haverá 7 nós vazios. ponteiro.
Um grande número de ponteiros gratuitos pode ser utilizado?
Os ponteiros que apontam para o antecessor e o sucessor são chamados de pistas. A lista vinculada binária mais as pistas é chamada de lista vinculada de pistas, e a árvore binária correspondente é chamada de árvore binária de pistas.
O processo de percorrer uma árvore binária em uma determinada ordem para transformá-la em uma árvore binária encadeada é chamado de encadeamento.
Árvores de Huffman e codificação de Huffman
O algoritmo é descrito da seguinte forma: 1) Trate esses N nós como N árvores binárias contendo apenas um nó para formar uma floresta F. 2) Construa um novo nó e selecione as duas árvores com os menores pesos do nó raiz de F como as subárvores esquerda e direita do novo nó e altere os pesos do novo nó Definido como a soma dos pesos dos nós raiz nas subárvores esquerda e direita. 3) Exclua as duas árvores recém-selecionadas de F e adicione as árvores recém-obtidas a F. 4) Repita os passos 2) e 3) até que reste apenas uma árvore em F.