Galeria de mapas mentais Mapa mental da árvore de estrutura de dados
Resume os pontos de conhecimento das árvores de estrutura de dados. O conteúdo principal inclui definições e termos básicos, propriedades de árvores, definições e termos básicos de árvores binárias, propriedades de árvores binárias e estruturas de armazenamento de árvores binárias.
Editado em 2023-01-06 10:54:13Microbiologia 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!
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.
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.
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!
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.
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.
Árvore
primeira parte
Definições e termos básicos
Nó raiz, nó folha, aresta, nó ramificado, árvore vazia: um número com 0 nós, subárvore, caminho entre nós: de cima para baixo. Comprimento do caminho: o número de arestas passadas.
Características: Existe um e apenas um nó chamado raiz. Cada nó, exceto o nó raiz, tem apenas um predecessor.
Uma árvore ordenada é desordenada. Da esquerda para a direita, ela é ordenada ou não?
árvores e floresta
Nó, descrição do atributo da árvore
Grau da árvore: o número de filhos que uma árvore possui o maior número de nós filhos
Altura do nó: contando de baixo para cima
Nível do nó, profundidade: contando de cima para baixo
Grau do nó: Quantos filhos um nó tem?
natureza da árvore
Número de nós = grau total 1
Árvores de grau m e árvores m-árias
Uma árvore com grau m: o grau de cada nó é <=m, e pelo menos um nó tem grau m. Deve ser uma árvore não vazia com pelo menos m 1 nós.
árvore m-ária: o grau de qualquer nó <= m, o grau de todos os nós é permitido <m, pode ser uma árvore vazia
O i-ésimo nível de uma árvore de grau m tem no máximo m ^ i-1 nós, e a árvore m-ária é a mesma
Uma árvore m-ária com altura h tem no máximo m^h-1/m-1 nós.
Uma árvore m-ária com altura h tem pelo menos h nós, e uma árvore com altura h e grau m tem pelo menos h m-1 nós.
A altura mínima de uma árvore m-ária com n nós é (log)[m](n(m-1) 1 arredondado para cima
a segunda parte
Definição de árvore binária e terminologia básica
conceito básico
Características: Cada nó possui no máximo duas subárvores, e as subárvores esquerda e direita não podem ser invertidas.
Várias árvores binárias especiais
árvore binária completa
A altura é h e o número de nós é 2 ^ h-1
A numeração começa em 1 em ordem hierárquica e o nó pai do nó i é arredondado para i/2
árvore binária completa
Ele tem uma correspondência um-para-um com a árvore binária completa e só pode ser excluído de trás para frente. A fila é semelhante.
i<=n/2 é arredondado para o próximo nó de ramificação e, se for maior ou igual a n/2, é arredondado para o nó folha.
Árvore de classificação binária
As chaves de todos os nós na subárvore direita são maiores que as chaves do nó raiz, e as chaves de todos os nós na subárvore esquerda são menores que
Usado para classificar e pesquisar elementos
árvore binária balanceada
A diferença de profundidade entre a subárvore esquerda e a subárvore direita de qualquer nó da árvore não excede 1
Mais gordo, com o mínimo de camadas possível
Maior eficiência de pesquisa
Propriedades de árvores binárias
Propriedades de árvores binárias
n0=n2 1
O resto é igual ao anterior
Propriedades de árvores binárias completas
A altura de uma árvore binária completa com n nós é log2(n 1) arredondado para cima e (log2n) 1 arredondado para baixo.
De acordo com o número de nós sendo n, podemos deduzir o número de nós com graus 0, 1 e 2.
Estrutura de armazenamento de árvore binária
armazenamento sequencial
Crie uma matriz estática para armazenar a árvore em ordem de cima para baixo, da esquerda para a direita. A estrutura da árvore contém duas variáveis, uma é o valor dos dados e a outra é o valor bool para determinar se o nó está vazio. Durante a inicialização, um loop é necessário para definir cada nó como vazio (o valor bool é verdadeiro)
operar
O filho esquerdo do nó i 2i
O filho certo do nó i 2i 1
O nó pai de i é arredondado para i/2
Arredondar log2(n 1)
árvore binária completa
Determine se eu tenho um filho esquerdo 2i<=n
Determine se eu tenho um filho certo 2i 1<=n
Determine se o nó i é uma folha ou ramo i> arredonde para n/2
No armazenamento sequencial de árvores binárias, os números dos nós da árvore binária devem ser combinados com a árvore binária completa, para que as relações lógicas entre os nós possam ser refletidas pelos números armazenados sequencialmente. Só faz sentido que árvores binárias completas sejam armazenadas sequencialmente.
Na pior das hipóteses, uma única árvore com apenas o filho certo requer pelo menos 2 ^ h-1 unidades de armazenamento sequenciais
armazenamento em cadeia
A estrutura possui três variáveis, uma é o valor e as outras duas são as variáveis de ponteiro filho esquerdo e direito.
Uma lista vinculada de árvore binária com n nós possui um total de n 1 campos de link vazios.
A vantagem é que é muito conveniente encontrar os filhos esquerdo e direito de um nó, mas a desvantagem é que encontrar o nó pai requer percorrer desde o início. O método consiste em definir mais um ponteiro de nó pai na estrutura.
a terceira parte
Travessia de primeira/média/pós-ordem da árvore binária
passagem de pré-encomenda
Ao redor da raiz
expressão de prefixo
etapa
Se estiver vazio, não faça nada
acessar o nó raiz
Travessia de pré-ordem da subárvore esquerda
A pré-encomenda atravessa a subárvore certa
travessia em ordem
esquerda raiz direita
Expressão inorder, requer delimitador inicial
Ruokong não faz nada
Percurso em ordem da subárvore esquerda
acessar o nó raiz
Percurso em ordem da subárvore direita
Travessia pós-ordem
raízes esquerda e direita
expressão pós-fixada
Se estiver vazio, não faça nada
Travessia pós-ordem da subárvore esquerda
Travessia pós-ordem da subárvore direita
acessar o nó raiz
Cada nó será passado três vezes em cada travessia, e as três travessias visitam o nó durante a primeira, segunda e terceira passagens em sequência.
Travessia de ordem de nível da árvore binária
Pensamento algorítmico
Inicializar uma fila auxiliar
Deixe o nó raiz entrar na fila
Se a fila não estiver vazia, deixe o nó raiz sair da fila e deixe os filhos esquerdo e direito do nó raiz entrarem na fila (os filhos esquerdo e direito existem)
Repita a etapa 3 até que a fila esteja vazia
Construa uma árvore binária a partir de uma sequência de travessia
Se apenas uma das sequências de travessia de ordem frontal, intermediária e posterior for fornecida, uma árvore binária não pode ser determinada exclusivamente.
Dois devem ser combinados e um deles deve ser uma sequência intermediária.
O princípio é que o nó raiz pode ser determinado com base nos níveis frontal e traseiro e, em seguida, as subárvores esquerda e direita são divididas de acordo com a ordem intermediária.
Conceito de árvore binária de dicas
sugestão
Idéia: Existem n 1 domínios de link vazios para n nós. Usamos o domínio de link vazio deste nó para armazenar o predecessor e o sucessor deste nó em cada travessia de sequência. Definir rtag, ltag indica se aponta para filho rag = 1 ou pista rag = 0.
Pista precursora: servida pelo ponteiro do filho esquerdo
Pista do sucessor: servida pelo ponteiro do filho certo
Predecessor em ordem: aponta para o antecessor do nó na travessia em ordem
A razão é que se não usarmos métodos encadeados, precisaremos percorrer os nós novamente, o que é ineficiente. O método simples é usar dois ponteiros para percorrer em sequência e registrar e, em seguida, usar os dois ponteiros para encontrar o nó para julgamento de equivalência. Dois tipos de julgamentos antes e depois correspondem ao antecessor e ao sucessor.
Threading de árvores binárias
Três tipos de implementações de código de passagem
Modificação dos três algoritmos de travessia Ao visitar um nó, a informação da pista que conecta o nó e o nó predecessor é.
Use um ponteiro pré para registrar o nó predecessor do nó atualmente acessado.
Fácil de cometer erros
Processamento de rchild e rtag do último nó
Encomende pistas para prestar atenção ao problema do círculo mágico do amor. Quando ltag=0, a subárvore esquerda pode ser informada em pré-ordem.
Encontre o antecessor e o sucessor na árvore binária de dicas
Encontre o predecessor e o sucessor do nó p na árvore binária de dicas em ordem
Procurando um sucessor
Determine o valor de rtag
se 0
Loop para encontrar o nó esquerdo da subárvore direita até que seja um nó folha, então este nó é o sucessor
se 1
Então o filho certo de p é o sucessor
Encontre um pioneiro
Determine o valor de ltag
se 0
Faça um loop para encontrar o filho direito da subárvore esquerda até que seja um nó folha, então este nó é o predecessor.
se 1
Então o filho esquerdo de p é o antecessor
precedência
Encontre um pioneiro
Determinar ltag = 1
é o ponteiro esquerdo
tag = 0
Na travessia de pré-ordem, os filhos esquerdo e direito só podem ser sucessores e não predecessores.
O método alternativo é percorrer do zero
Use uma lista vinculada de três frentes e adicione um ponteiro para o nó pai
Se houver um nó pai e p for o filho esquerdo
Então o nó pai de p é o antecessor
Se houver um nó pai e p for o filho certo
Irmão Zuo não está vazio
O predecessor de p é o último nó da subárvore irmã esquerda na travessia de pré-ordem.
O irmão esquerdo está vazio
O nó pai é o predecessor
Se p é o nó raiz
nenhum precursor
Procurando um sucessor
Determinar ltag = 1
é o ponteiro esquerdo
tag = 0
Suponha que haja um filho esquerdo
Então o filho da esquerda é o sucessor
não há filho esquerdo
é o filho certo
Posfácio
Encontre um pioneiro
Determinar ltag = 1
é o ponteiro esquerdo
tag = 0
Deve haver uma criança esquerda
Suponha que não haja filho certo
Então o filho da esquerda é o precursor
Tenha um filho certo
Então a criança certa é a precursora
Procurando um sucessor
Determinar rtag = 1
é o ponteiro certo
tag = 0
p deve ter um filho certo
No percurso pós-ordem, as subárvores esquerda e direita só podem ser o predecessor da raiz, não o sucessor.
Percorra do zero usando métodos locais
Use uma lista vinculada de três frentes para adicionar um ponteiro pai
Pode encontrar o nó pai
p é o filho certo
O nó pai de p é o sucessor
p é o filho esquerdo
O irmão certo está vazio
O nó pai de p é o sucessor
Certo irmão não está vazio
O sucessor de p é o primeiro nó na subárvore irmã direita que é percorrido em pós-ordem
P é o nó raiz
p não tem sucessor
quarta parte
estrutura de armazenamento de árvore
Notação parental (armazenamento sequencial)
Como definir
Defina duas estruturas, uma para cada nó e outra para a estrutura em árvore
Armazene árvores em uma matriz de cima para baixo, da esquerda para a direita
O ponteiro do nó pai do nó raiz é -1 e o valor do ponteiro do nó pai de outros nós é o subscrito da matriz do nó pai.
operar
Novos elementos não precisam ser armazenados fisicamente para
Excluir elemento
A opção 1 altera o valor do ponteiro do nó pai do elemento excluído para -1
Opção 2: Cubra o último nó com o nó a ser excluído
Se for um nó folha, é muito conveniente excluí-lo. E se não for um nó folha?
É necessário percorrer desde o início e deletar todas as suas subárvores.
Vantagens e desvantagens: A vantagem é que é fácil encontrar o nó pai, mas encontrar o nó filho requer percorrê-lo desde o início.
Representação filho (armazenamento em cadeia sequencial)
Como definir
Defina três estruturas
estrutura de lista vinculada
uma estrutura de árvore
A estrutura de um nó
Armazene cada nó sequencialmente e armazene o ponteiro principal da lista filho em cada nó.
Representação do irmão filho (armazenamento acorrentado)
Existem dois ponteiros na estrutura, um apontando para o filho esquerdo e outro apontando para o irmão direito do filho esquerdo.
Vantagens: você pode usar operações de árvore binária para processar árvores diretamente
Apresente a estrutura de uma árvore binária em lógica física
Implementar conversão de árvore e árvore binária
Realize a conversão de árvores e florestas binárias
Os nós raiz de cada árvore são considerados irmãos.
Travessia de árvores e florestas
travessia de árvore
passagem pela raiz da árvore
Se a árvore não estiver vazia, visite primeiro o nó raiz e, em seguida, execute o percurso raiz primeiro em cada subárvore.
primeira travessia em profundidade
A sequência de passagem pré-raiz da árvore é igual à sequência de pré-ordem da árvore binária correspondente desta árvore.
Travessia da raiz traseira da árvore
Se a árvore não estiver vazia, primeiro execute uma travessia pós-raiz em cada subárvore e, finalmente, visite o nó raiz.
primeira travessia em profundidade
A travessia subsequente da árvore é igual à sequência ordenada da árvore binária correspondente a esta árvore.
Percurso em nível de árvore
Implementado usando filas
Se a árvore não estiver vazia, o nó raiz será adicionado à fila.
Se a fila não estiver vazia, o elemento principal será retirado da fila e acessado, e os filhos do elemento serão adicionados à fila.
Repita a etapa anterior até que a fila esteja vazia
travessia em largura
Viajando pela floresta
Pré-encomenda de travessia da floresta
O efeito é equivalente ao percurso pela primeira raiz de cada árvore em sequência.
Equivalente à travessia pré-encomendada de uma árvore binária em sequência
travessia em ordem
Equivalente a realizar um percurso pós-raiz em cada árvore por vez
Equivalente ao percurso em ordem de uma árvore binária
Primeiro primeiro primeiro, Shusen Er. Após o meio, Shusen dois.
a quinta parte
Árvore de Huffman
Caminho e comprimento corretos
O peso do nó: um valor com algum significado prático (como a importância do nó)
O comprimento total do caminho de um nó: o produto do comprimento do caminho (número de arestas passadas) da raiz da árvore até o nó e o peso do nó
O comprimento total do caminho da árvore
A soma dos comprimentos ponderados dos caminhos de todos os nós foliares das espécies de árvores
Definição de árvore de Huffman
Em uma árvore binária contendo n nós folha ponderados, a árvore binária com o menor comprimento total de caminho é chamada de árvore de Huffman, também conhecida como árvore binária ótima.
A estrutura da árvore de Huffman
Cada vez que os dois nós com os menores pesos são combinados em uma árvore, o peso do novo nó gerado é a soma dos dois nós. Continue as etapas acima em sequência até que todos os nós sejam combinados.
natureza
Cada nó inicial eventualmente se torna um nó folha, e o nó com o menor peso tem o maior comprimento de caminho até o nó raiz.
O número total de nós da árvore de Huffman é 2n-1
Não há nó com grau 1 na árvore de Huffman
A árvore de Huffman não é única, mas o wpl deve ser o mesmo e ideal
Codificação de Huffman
Codificação de comprimento fixo: cada caractere é representado por comprimento igual de bits binários
Codificação de comprimento variável: permite que diferentes caracteres sejam representados por comprimentos desiguais de bits binários
Codificação de prefixo: se nenhuma codificação for o prefixo de outra codificação, essa codificação será chamada de codificação de prefixo.
A codificação e decodificação de prefixo são inequívocas
A codificação de Huffman é obtida usando uma árvore de Huffman. Cada caractere do conjunto de caracteres é usado como um nó folha, e a frequência de cada caractere é usada como o peso do nó para construir uma árvore de Huffman.
natureza
As árvores de Huffman não são únicas e os códigos de Huffman não são únicos.
Aplicação: Telégrafo e dados compactados
E pesquise a coleção
O conjunto de pesquisa de união é uma estrutura lógica, uma implementação específica de um conjunto. Ele executa apenas duas operações: união e pesquisa. Uma floresta é usada para representar um conjunto, e cada árvore é um subconjunto disjunto.
operar
Pesquisa: comece no elemento especificado, vá até o norte e encontre o nó raiz.
Determine se dois elementos estão no mesmo conjunto. Encontre as raízes de dois elementos separadamente e determine se os nós raiz são iguais
E: Basta fazer de outra árvore de lição uma subárvore de outra árvore
Estrutura de armazenamento: Representação parental de uma árvore.
Código
Inicialização: deixe o ponteiro pai de cada nó apontar para -1
Encontrar
e
Otimização da fusão: Use o valor absoluto do nó raiz para representar o número total de nós na árvore, para que árvores pequenas possam ser mescladas em árvores grandes.
A pior complexidade de tempo das operações de otimização e pesquisa muda de on para olog2n
A altura da árvore construída por este método não excede (arredondado para baixo log2n) 1
Otimização adicional da pesquisa de união
Otimização da operação de localização: compactar o caminho, primeiro encontrar o nó raiz e, em seguida, suspender todos os nós no caminho de pesquisa sob o nó raiz