Wondershare EdrawMind
MindMap Gallery Estrutura de conhecimento de estrutura de dados
- 21
Estrutura de conhecimento de estrutura de dados
Estruturas de dados, incluindo árvores B, hashes, classificação, gráficos, primeira introdução a estruturas de dados, complexidade de algoritmos, recursão, pilhas, filas, matrizes, primeira introdução a árvores, árvores binárias de árvores, árvores binárias encadeadas, heaps, árvores Huffman , Árvores de pesquisa binária, árvores AVL e árvores rubro-negras podem ser usadas para revisão final e estudo de vestibular de pós-graduação.
Edited at 2023-05-18 23:31:04
Estrutura de conhecimento de estrutura de dados
- Recommended to you
- Outline
Guia de sobrevivência do gerenteComo gerenciar uma empresa de 1 a 300 pessoas, um manual de desenvolvimento de liderança
- 14
Estrutura de conhecimento de estrutura de dados
Árvore B
Multi-árvore balanceada
natureza
O nó raiz tem pelo menos dois filhos
Cada nó não raiz tem pelo menos M/2 (arredondado) filhos e no máximo M filhos.
Cada nó não raiz tem pelo menos palavras-chave M/2-1 (arredondadas para cima) e elas são organizadas em ordem crescente
O valor do nó filho entre key[i] e key[i 1] está entre key[i] e key[i 1]
Todos os nós folha estão na mesma camada
Árvore B
natureza
Sua definição é basicamente a mesma da árvore B
O ponteiro da subárvore de um nó não folha é igual ao número de palavras-chave
O ponteiro da subárvore P[i] do nó não folha aponta para a subárvore cujo valor-chave pertence a [k[i],k[i 1])
Adicione um ponteiro de link a todos os nós folha
Todas as palavras-chave aparecem em nós folha
procurar
Basicamente o mesmo que árvore B
característica
Todas as palavras-chave aparecem na lista vinculada de nós folha (índice denso), e as palavras-chave na lista vinculada são ordenadas
Impossível acertar no nó folha
Os nós não folha são equivalentes ao índice de nós folha (índice esparso) e os nós folha são equivalentes à camada de dados que armazena dados (palavra-chave).
Mais adequado para sistemas de indexação de arquivos
Árvore B*
Adicione ponteiros para irmãos entre os nós não-raiz e não-folha da árvore B
Subtópico 2
Cerquilha
Pesquisa (recuperação)
O processo de descobrir se existe um elemento de dados com uma chave igual a uma determinada chave em uma coleção de elementos de dados.
resultado
sucesso
falhar
estrutura de pesquisa
Coleta de dados para pesquisa
Contexto de pesquisa
ambiente estático
A estrutura de pesquisa não será alterada antes e depois da execução de operações como inserção e exclusão.
ambiente dinâmico
Para manter a alta eficiência da pesquisa, a estrutura da pesquisa será ajustada automaticamente antes e depois de operações como inserção e exclusão, e a estrutura pode mudar.
Encontrar
pesquisa estática
Tabela de sequência
Atravessando da frente para trás O(n)
lista de sequência ordenada
Pesquisa binária O(log(n))
tabela de sequência de índice
pesquisa dinâmica
estrutura de árvore binária
Árvore de classificação binária
árvore binária balanceada
estrutura de árvore
Árvore B
Árvore B
Pesquisa de hash
A chave de cada elemento corresponde a um local único de armazenamento de nós na estrutura
Método de hash
Insira e pesquise dados. Use a função hash para encontrar o local de armazenamento e, em seguida, armazene ou pesquise.
Colisão de hash
Para dois dados Ki e Kj (i!=j), Ki!=Kj, mas há Hash(Ki)==Hash(Kj)
Função hash
O domínio da função hash deve incluir todas as chaves que precisam ser armazenadas e, se a tabela hash permitir m endereços, seu intervalo de valores deve estar entre 0-m-1
Os endereços calculados pela função hash podem ser distribuídos uniformemente por todo o espaço
A função hash deve ser relativamente simples
Funções hash comuns
método de endereçamento direto
Tome uma função linear da palavra-chave como endereço hash
Vantagens: simples e uniforme
Desvantagens: Necessidade de saber antecipadamente a distribuição das palavras-chave
Cenário de uso: Adequado para encontrar situações relativamente pequenas e contínuas
método de divisão deixando resto
Deixe o número de endereços permitidos no hash ser m, pegue um número primo p que não seja maior que m, mas seja mais próximo ou igual a m como divisor, e divida a chave de acordo com a função hash: Hash(chave) =key%p,p<=m código convertido em endereço hash;
Método Quadrado-Médio
Suponha que a palavra-chave seja 1234, o quadrado seja 1522756 e, em seguida, extraia o número de três dígitos 227 no meio como o endereço hash
método de dobramento
Divida a palavra-chave em várias partes com dígitos iguais da esquerda para a direita, depois sobreponha e some essas partes e tome os últimos dígitos como o endereço hash de acordo com o comprimento da tabela hash.
método de número aleatório
Escolha uma função aleatória e considere o valor da função aleatória da palavra-chave como seu endereço hash
analise matemática
Assumindo n dígitos, cada dígito pode ter r símbolos diferentes. A frequência desses r símbolos diferentes que aparecem em cada dígito não é necessariamente a mesma. o endereço hash de acordo com o método hash.
Método de tratamento de conflitos de hash
hash fechado
Quando ocorrer um conflito, procure o próximo endereço da tabela hash vazia. Contanto que a tabela hash seja grande o suficiente, o endereço hash vazio sempre poderá ser conhecido.
exploração linear
Ao inserir, verifica-se que os dados nesta posição são iguais aos dados a serem inseridos e nenhuma inserção é realizada.
Se ocorrer um conflito, verifique o próximo intervalo e insira os dados se houver uma posição vazia.
Segunda exploração
Usando o método de exploração quadrática, a fórmula para encontrar a próxima posição vazia na tabela é H(i)=(H0 i^2)%m,H(i)=(H0-i^2)%m
Quando o comprimento da tabela for um número primo e o fator de reprodução não exceder 0,5, novas entradas na tabela poderão ser inseridas
hash duplo
Duas funções hash são necessárias e, quando uma delas colide, a próxima função hash é usada para calcular o deslocamento.
fator de carga
a=número de elementos preenchidos na tabela/comprimento da tabela hash
Controle-o abaixo de 0,7-0,8. Se exceder 0,8, o índice de cache da CPU aumentará ao consultar a tabela.
hash aberto
Primeiro, uma função hash é usada para calcular o endereço hash do conjunto de chaves com o mesmo endereço pertencente ao mesmo subconjunto. Cada subconjunto é chamado de bucket. lista vinculada O cabeçalho de cada lista vinculada Os pontos formam um vetor com o mesmo número de elementos que o número de baldes possíveis.
filtro de flor
Quando um elemento é adicionado ao conjunto, k funções hash são usadas para mapear o elemento em k pontos em uma matriz de bits e defini-los como 1. Ao recuperar, basta verificar se todos são 1. Tudo bem, desde que. como existe um Se for zero, não é, se for tudo 1, provavelmente é
organizar
conceito
É organizar um conjunto de dados confusos de acordo com uma determinada regra (ordem crescente ou decrescente)
Ficha de dados
Um conjunto finito de elementos de dados a serem classificados
Código de classificação
Normalmente, os elementos de dados possuem vários campos de atributos, um dos quais pode ser usado para distinguir elementos e servir como base para a classificação. Este campo é o código de classificação.
Se os códigos de classificação de cada elemento na tabela de dados forem diferentes entre si, esse código de classificação é chamado de código de classificação principal.
A estabilidade dos algoritmos de classificação
Dois elementos R[i]R[j], seu código de classificação K[i]==K[j], e antes da classificação, o elemento R[i] está antes de R[j], e o elemento está entre R[i ] e a ordem de R[j] permanece inalterada
Algoritmos de classificação comuns
ordenação por inserção
classificação por inserção direta
Insira na sequência classificada, primeiro encontre a posição e, em seguida, mova o elemento após a posição de volta
Estabilizar
Tipo de colina
Reduzir a classificação incremental
ordenação por seleção
ordenação por seleção
Coloque o menor elemento na frente de cada vez
Classificação do torneio
Continue comparando dois por dois para encontrar o vencedor, não compare mais este, continue comparando os outros dois por dois, obtenha o vencedor e continue repetindo
instável
Classificação de pilha
Crie um heap grande em ordem crescente, caso contrário, crie um heap pequeno
instável
classificação de troca
Tipo de bolha
Estabilizar
Compare dois elementos adjacentes em sequência e troque se as condições não forem atendidas.
Ordenação rápida
Pegue um valor base e coloque os menores à esquerda e os maiores à direita. As partes esquerda e direita pegam recursivamente o valor base e continuam dividindo.
classificação por mesclagem
classificação por mesclagem
Divida a sequência a ser classificada em duas subsequências de igual comprimento e depois mescle-as em uma sequência
classificação não comparativa
classificação de contagem
Classificação de raiz
foto
Uma estrutura de dados que consiste em uma coleção de vértices e relacionamentos entre vértices
vértices e arestas
vértice
Os nós no gráfico são chamados de nós
lado
Existe uma aresta entre os vértices
Classificação de gráficos
gráfico direcionado
Em um gráfico direcionado, o par de vértices <x, y> é ordenado <x, y> <y, x> são duas arestas diferentes
Gráfico não direcionado
(x,y)(y,x) é um lado
gráfico completo
Em um gráfico não direcionado com n vértices, se houver n*(n-1)/2 arestas, ou seja, existe e existe apenas uma aresta entre quaisquer dois vértices.
Em um gráfico direcionado com n vértices, se houver n*(n-1) arestas, ou seja, existem e existem apenas arestas em direções opostas entre quaisquer dois vértices.
nó adjacente
No grafo não direcionado G, se (u, v) é uma aresta em E (G), então u e v são considerados vértices adjacentes um ao outro, e (u, v) é considerado anexado aos vértices u e v.
No gráfico direcionado G, se <u,v> é uma aresta em E(G), então o vértice u é considerado adjacente a v, e o vértice v é adjacente ao vértice u, e a aresta <u, v> é considerado a soma do vértice u e v está associado a
grau de vértice
o número de arestas associadas a ele
Em um gráfico direcionado, o grau de um vértice é igual à soma do grau de entrada e do grau de saída do vértice, onde o grau de entrada do vértice v é o número de arestas direcionadas que terminam em v, denotado como indev( v) o grau externo do vértice v. O grau é o número de arestas direcionadas com v como ponto inicial, denotado como outdev(v)
O grau de um gráfico não direcionado é igual ao grau de entrada e ao grau de saída dev(v) = indev(v) = outdev(v)
caminho
No gráfico G=(V,E), se houver um conjunto de arestas começando no vértice vi que pode atingir o vértice vj, então a sequência de vértices do vértice vi a vj é chamada de caminho do vértice vi ao vértice vj.
certo
Informações de dados anexadas à borda
comprimento do percurso
Para gráficos não ponderados, o comprimento do caminho de uma aresta refere-se ao número de arestas no caminho.
Para gráficos ponderados, o comprimento de um caminho refere-se à soma dos pesos de cada aresta do caminho.
Caminhos e loops simples
Se os vértices no caminho não são repetidos, então tal caminho é chamado de caminho simples. Se o primeiro vértice v1 e o último vértice vm no caminho coincidem, então tal caminho é chamado de loop ou anel.
subtrama
Suponha que o gráfico G={V,E} e o gráfico G1={V1.E1} se V1 pertence a V e E1 pertence a E, então G1 é considerado um subgrafo de G.
gráfico conectado
Em um grafo não direcionado, se houver um caminho entre dois vértices, ele será conectado. Se qualquer par de vértices estiver conectado, o grafo é chamado de grafo conectado.
Gráfico fortemente conectado
Em um grafo direcionado, entre qualquer par de vértices vi e vj, existe um caminho de vi para vj, e também existe um caminho de vj para vi.
árvore geradora
O subgrafo mínimo conectado de um grafo conectado é chamado de árvore geradora do grafo. A árvore geradora de um grafo conectado com n vértices tem n vértices e n-1 arestas.
Estrutura de armazenamento de gráfico
matriz de adjacência
lista de adjacências
Gráfico não direcionado
gráfico direcionado
Percurso gráfico
profundidade primeiro
largura primeiro
componentes conectados
Quando o grafo não direcionado é um grafo não conectado, começando em um determinado vértice do grafo, o algoritmo de busca em profundidade ou busca em largura não pode percorrer todos os vértices do grafo, mas só pode acessar todos os vértices do maior subgrafo conectado onde o nó está localizado, esses vértices formam um componente conectado.
árvore geradora mínima
critério
Uma árvore geradora mínima só pode ser construída usando arestas no gráfico
Apenas n vértices no gráfico podem ser conectados usando exatamente n-1 arestas
As n-1 arestas selecionadas não podem formar um loop.
algoritmo ganancioso
Ao resolver problemas, faça sempre a escolha que lhe parecer melhor no momento, ou seja, a solução ótima local.
Algoritmo de Kruskal
Encontre uma aresta com o peso mais curto e não mais no mesmo componente conectado todas as vezes para adicionar à árvore geradora.
algoritmo principal
Encontre um ao lado do outro
caminho mais curto da unidade
Partindo de um vértice em um gráfico ponderado, encontre o caminho mais curto para outro vértice. O caminho mais curto é a soma mínima dos pesos ao longo do caminho.
Primeira introdução às estruturas de dados
conceito
dados
Símbolos que descrevem coisas objetivas são objetos que podem ser manipulados no computador. Eles são uma coleção de símbolos que podem ser reconhecidos pelo computador e inseridos no computador para processamento.
elemento de dados
É uma unidade básica que compõe os dados e tem um determinado significado. Nos computadores, geralmente é processado como um todo.
Item de dados
Um elemento de dados pode consistir em vários itens de dados. Um item de dados é a menor unidade inseparável de dados
formulário de estrutura de dados
estrutura de dados
é uma coleção de elementos de dados que possuem um ou mais relacionamentos específicos entre si
Classificação
estrutura lógica
Definir estrutura
estrutura linear
estrutura de árvore
Estrutura gráfica
Estrutura física
estrutura de armazenamento sequencial
estrutura de armazenamento em cadeia
conceito específico
estrutura lógica
Inter-relacionamentos entre elementos de dados em um objeto de dados
Definir estrutura
Os elementos de dados no conjunto não têm outro relacionamento entre eles, exceto que pertencem ao mesmo conjunto.
estrutura linear
Existe um relacionamento um-para-um entre os elementos de dados
estrutura de árvore
Um relacionamento hierárquico um-para-muitos entre elementos de dados
Estrutura gráfica
Os elementos de dados são relacionamentos muitos para muitos
Estrutura física
A forma de armazenamento da estrutura lógica dos dados no computador
estrutura de armazenamento sequencial
Os elementos de dados são armazenados em unidades de armazenamento com endereços consecutivos e os relacionamentos lógicos e físicos entre os dados são consistentes.
estrutura de armazenamento em cadeia
Os elementos de dados são armazenados em qualquer unidade de armazenamento. A unidade de armazenamento pode ser contínua ou descontínua.
A estrutura lógica é orientada para o problema e a estrutura física é orientada para o computador. Seu objetivo básico é armazenar dados e seus relacionamentos lógicos na memória do computador.
programa
algoritmo
estrutura de dados
algoritmo
Uma descrição dos passos para resolver um problema específico, representado num computador como uma sequência finita de instruções, com cada instrução representando uma ou mais operações.
Características do algoritmo
digitar
O algoritmo tem zero ou mais entradas
saída
Há pelo menos uma ou mais saídas
Finitude
O algoritmo termina automaticamente após a execução de um número limitado de etapas sem loops infinitos, e uma etapa é concluída dentro de um tempo aceitável
certeza
Cada etapa do algoritmo tem um significado definido e não haverá ambigüidade.
viabilidade
Cada etapa do algoritmo deve ser viável, ou seja, cada etapa pode ser concluída executando um número finito de vezes.
Requisitos de algoritmo de design
correção
legibilidade
Robustez
Alta eficiência de tempo
e baixo uso de espaço
simplicidade
complexidade do algoritmo
complexidade de tempo
complexidade do espaço
Classificação de Análise Algorítmica
situação média
Número esperado de execuções para qualquer tamanho de entrada
pior cenário
Número máximo de execuções para qualquer tamanho de entrada
Melhor cenário possível
Número mínimo de execuções para qualquer tamanho de entrada, geralmente o melhor caso não ocorre
Complexidade de tempo - notação assintótica O
Algoritmo geral O(n) método de cálculo
Substitua todas as constantes aditivas em tempo de execução pela constante 1
Na função de número de execuções modificada, apenas os termos de ordem mais alta são retidos
Se o coeficiente do termo de ordem mais alta existir e não for 1, remova a constante multiplicada por este termo
Cálculo de complexidade de tempo do algoritmo de divisão e conquista
A complexidade de tempo do algoritmo de busca binária é lgN
A complexidade de tempo do algoritmo de busca de pontos M é logM^N
Cálculo de complexidade de tempo do algoritmo recursivo
Número total de recursões * número de recursões por tempo
Algoritmo Recursivo Algoritmo de Complexidade Espacial
N*tamanho do espaço para cada recursão
recursão
definição recursiva
Dizemos que um objeto é recursivo se ele se contém parcialmente ou se define por si mesmo.
processo recursivo
Um procedimento chama a si mesmo direta ou indiretamente
pensamento recursivo
Divida o problema em problemas menores que tenham a mesma solução do problema original
condição recursiva
Reduza o tamanho do problema para que o novo problema tenha a mesma solução que o problema original
Definir saída recursiva
classificação recursiva
recursão de estrutura de dados
recursão de resolução de problemas
pilha de chamadas recursiva
recursão de cauda
O resultado retornado por uma chamada recursiva é sempre retornado diretamente
A natureza da recursão da cauda
Armazene em cache o resultado de um único cálculo e passe-o para a próxima chamada, o que equivale à acumulação automática
complexidade de tempo
Número total de recursões * número de recursões por tempo
Retrocesso
Ideia básica
algoritmo de labirinto
Vantagens e desvantagens da recursão
vantagem
A recursão simplifica a maneira como pensamos ao resolver determinados problemas, e o código é mais conciso e fácil de ler.
deficiência
A essência da recursão é chamar a si mesmo, e o custo de chamar uma função é muito alto. O sistema deve alocar espaço de armazenamento para cada chamada de função, colocar as informações do ponto de chamada na pilha e, após o término da chamada de função, o espaço deve. ser liberado, estourar a pilha e restaurar o ponto de interrupção, se a complexidade da solução recursiva.
pilha
Conceito de pilha
Um tipo especial de tabela linear que permite apenas a inserção e exclusão de dados de uma extremidade
Características: Último a entrar, primeiro a sair
pilha de sequência
Os membros de dados da pilha sequencial e da tabela de sequência do livro são os mesmos. A diferença é que as operações push e pop da pilha sequencial só podem ser executadas no topo da pilha atual.
pilha compartilhada
Um array implementa duas pilhas
princípio
Como duas pilhas compartilham um espaço e se aproximam do meio, as duas extremidades da matriz representam a parte inferior das duas pilhas, e o topo da pilha continua se movendo em direção ao meio.
Cenários de aplicação
Os dois requisitos de espaço de pilha têm uma relação oposta, ou seja, um aumenta e o outro diminui.
pilha de corrente
Plugue de cabeça excluído
aplicação de pilha
correspondência de colchetes
Expressão polonesa reversa
algoritmo de labirinto
fila
Uma tabela linear especial que só permite que dados sejam inseridos em uma extremidade e excluídos na outra extremidade
fila sequencial
Método de implementação um
Quando o chefe da fila não sai da fila, todos os elementos avançam.
Método de implementação dois
Ao retirar da fila, o início da fila retrocede uma posição
falso estouro
O estouro ocorre após diversas operações de enfileiramento e desenfileiramento. Ainda há espaço de armazenamento, mas a operação de enfileiramento não pode ser executada.
Verdadeiro fenômeno de estouro
O espaço máximo de armazenamento está cheio, continue a operação da fila.
fila circular
Uma fila de armazenamento sequencial conectada de ponta a ponta é uma fila circular.
Determinando se a fila está cheia ou vazia
Use um espaço de armazenamento a menos
O ponteiro final da fila mais um é igual ao ponteiro inicial da fila, que é a condição para determinar se a fila está cheia.
A condição para julgamento nulo é que a cauda e a cabeça sejam iguais
Projete uma bandeira de marca
O sinalizador inicial é definido como 0, a fila é enfileirada com êxito com sinalizador = 1 e a fila é retirada da fila com êxito com o sinalizador definido como 0.
Equipe vazia condição traseira==frente&&flag==0,
Condição completa traseira==frente&&flag=1
Definir um contador
Inicialmente, contagem=0, a fila foi enfileirada com êxito, contagem 1, e a fila foi retirada da fila com êxito, contagem-1.
Contagem de condições de fila vazia==0
As condições para a fila ficar cheia são count>0&&rear==front ou count == MaxSize
fila encadeada
A estrutura de armazenamento vinculada da fila é, na verdade, uma lista vinculada individualmente de uma lista linear, exceto que só pode ter o final para dentro e o início para fora.
Fila de prioridade
Fila de prioridade
Aqueles com maior prioridade serão retirados primeiro da fila e aqueles com a mesma prioridade seguirão a regra do primeiro a entrar, primeiro a sair.
Enfileirar aplicativos
modelo produtor-consumidor
fila de mensagens
fenômeno da fila
Transmissão de dados em rede
matriz
matriz especial
Uma matriz que possui muitos elementos com o mesmo valor ou muitos elementos zero, e a distribuição de elementos com o mesmo valor ou zero elementos tem um determinado padrão
Matriz simétrica
Uma matriz N*N, qualquer Aij = Aji
Armazenamento de compressão de matriz simétrica
Como os triângulos superior e inferior da matriz simétrica são iguais, apenas metade deles precisa ser armazenada.
A relação entre matrizes simétricas e armazenamento compactado simétrico
triângulo inferior
i>jSymmetricMatrix[i][j] == Matriz[i*(i 1)/2 j]
matriz esparsa
Matriz M*N, o número de valores válidos na matriz é muito menor que o número de valores inválidos e a distribuição é irregular.
Armazenamento de compactação de matriz esparsa
Armazene apenas um pequeno número de valores válidos
Use triplos {row,col,value} para armazená-los de uma vez em ordem de prioridade de linha de acordo com a posição na matriz.
Inversão de matriz
Trocando linhas e colunas
Retrocesso rápido
árvore do primeiro conhecido
Conceitos básicos de árvores
Um conjunto composto por N nós (N>=0)
Existe um nó especial chamado nó raiz. O nó raiz não possui nós predecessores.
Com exceção do nó raiz, os nós restantes são divididos em M (M>0) conjuntos disjuntos T1, T2...Tn, cada um dos quais é uma subárvore semelhante a uma estrutura de árvore.
As árvores são definidas recursivamente
Glossário
Nó
Um nó inclui um elemento de dados e vários ramos (ponteiros (índices)) apontando para outras subárvores.
grau de nó
O número de subárvores pertencentes ao nó
nó com grau 0
Também chamado de nó terminal
nó de ramificação
Nós com grau diferente de zero
nó não terminal
nó ancestral
Todos os nós nas ramificações do nó raiz até este nó
Nó descendentes
Todos os nós na subárvore com um nó como nó raiz
nó pai
Se um nó na árvore tiver um nó filho, o nó será chamado de nó pai de seu nó filho.
nó filho
O nó raiz de uma subárvore de um nó na árvore é chamado de nó filho desse nó.
Nó irmão
Nós com o mesmo nó pai
grau de árvore
O grau máximo de todos os nós da árvore
Nível do nó
O número de ramificações ao longo do caminho do nó raiz até um nó na árvore
profundidade da árvore
O valor máximo dos níveis de todos os nós da árvore
árvore ordenada
Cada subárvore T0, T1... do nó na árvore é ordenada
árvore não ordenada
A ordem entre as subárvores dos nós da árvore não é importante e eles podem trocar posições entre si.
floresta
árvore m coleção de árvores
representação de árvore
Estrutura de diretório
Diagrama de Venn de coleção
estrutura de armazenamento de árvore
representação dos pais
Use ponteiros para indicar os nós pais de cada nó
vantagem
É muito conveniente encontrar a operação do nó pai de um nó.
deficiência
É inconveniente encontrar os nós filhos de um nó.
representação infantil
Use ponteiros para apontar para os nós filhos de cada nó
vantagem
É mais conveniente encontrar os nós filhos de um nó
deficiência
É muito inconveniente encontrar o nó pai de um nó.
Representação pai-filho
Use ponteiros para representar os nós pais de cada nó e os nós filhos de cada nó.
representação do irmão menor
Representa o primeiro nó filho do primeiro nó e também indica o próximo nó irmão de cada nó.
Aplicações de árvores
diretório de computador
árvore binária
conceito
Uma árvore binária é um conjunto finito de nós. O conjunto é vazio ou consiste em um nó raiz mais duas árvores binárias chamadas subárvore esquerda e subárvore direita.
Características
Cada nó possui no máximo duas subárvores
As subárvores de uma árvore binária podem ser divididas em subárvores esquerda e direita e sua ordem não pode ser invertida.
árvore binária completa
Todos os nós ramificados têm subárvores esquerda e subárvores direita, e todos os nós folha estão no mesmo nível.
árvore binária completa
Se a estrutura de uma árvore binária com N nós for igual à estrutura dos primeiros N nós de uma árvore binária completa, ela é chamada de árvore binária completa.
Propriedades de árvores binárias,
Se o nível do nó raiz for especificado como 1, então haverá no máximo 2^(i-1) (i>=1) nós no i-ésimo nível de uma árvore binária não vazia.
Se a profundidade de uma árvore binária com apenas o nó raiz for especificada como 1, então o número máximo de nós de uma árvore binária com profundidade K é 2^k-1 (k>=0)
Para qualquer árvore binária, se o número de nós folha for n0 e o número de nós não folha com grau 2 for n2, então n0 = n2 1
Para uma árvore binária completa com n nós, se todos os nós forem numerados começando em 0 em ordem de cima para baixo, da esquerda para a direita, então para o nó com número de série i:
Se i>0, então o número de série do nó pai do nó com número de série i é (i-1)/2. Se i==0, então o nó com número de série i é o nó raiz e não há. nó pai.
Se 2i 1<n, então o número filho esquerdo do nó pai com número de série i é (i-1)/2. Se (2i 1)>=n, então o nó com número de série i não tem nó filho direito.
Se 2i 2<n, então o nó filho certo do nó com o número de série é 2i 2. Se 2i 2>=n, então o nó com o número de série i não tem nenhum nó filho certo.
Estrutura de armazenamento de árvore binária
armazenamento sequencial
vantagem,
Armazene árvores binárias completas, simples e com economia de espaço
deficiência
Para árvores binárias gerais, especialmente árvores de ramo único, a utilização do espaço de armazenamento não é ideal.
armazenamento em cadeia
Subtópico 1
Ponteiro de simulação (lista vinculada estática)
Operações básicas de árvores binárias
Criação de árvore binária
Travessia de árvore binária
prólogo
ordem intermediária
Posfácio
seqüência
Inicializar uma fila
Coloque o ponteiro do nó raiz na fila
Loops quando a fila não está vazia
Remover da fila um nó
Se a subárvore esquerda do nó não estiver vazia, coloque o ponteiro da subárvore esquerda do nó na fila.
Se a subárvore direita do nó não estiver vazia, coloque a subárvore direita do nó na fila.
Terminar
árvore binária encadeada
conceito de sugestão
Converta a árvore binária em uma sequência linear de acordo com o percurso da árvore binária
Possíveis problemas com árvores binárias comuns
A travessia recursiva pode causar estouro de pilha
A versão não recursiva pode tornar o programa menos eficiente
É difícil encontrar o antecessor ou sucessor de um nó em uma determinada forma de travessia.
Há um grande número de campos de ponteiro nulo na árvore causando desperdício,
processo de pistas
Quando o ponteiro esquerdo de um nó estiver vazio, deixe o ponteiro apontar para o nó predecessor do nó obtido ao percorrer a árvore binária de uma determinada maneira.
Quando o ponteiro direito de um nó é nulo, deixe o ponteiro apontar para o nó sucessor do nó obtido percorrendo a árvore binária de acordo com um determinado método de travessia.
bandeira de pista
A função é distinguir se é um nó filho, um precursor ou um sucessor.
leftThread
0
esquerdaCriança
1
leftThread
thread à direita
0
criança direita
1
thread à direita
dica
Ponteiro para o nó predecessor ou sucessor no nó
pista de árvore binária
Árvore binária com nós de árvore binária mais pistas
O processo de percorrer uma árvore binária de uma determinada maneira (pré-ordem, ordem, pós-ordem) é chamado de árvore binária com pistas. É chamado de método de encadeamento da árvore binária.
amontoar
Conceito de pilha
Armazene todos os elementos em uma matriz unidimensional na forma de uma árvore binária completa e satisfaça Ki<=K2*i 1 e Ki<=K2*i 2 (Ki>=K2*i 1 e Ki>=K2*i 2 ) , esse heap é chamado de heap mínimo (heap máximo)
Classificação de pilhas
pilha pequena
O código-chave de qualquer nó é menor que o código-chave de seus filhos esquerdo e direito. O código-chave do nó no topo do heap é o menor.
pilha grande
O código-chave de qualquer nó é maior que os códigos-chave de seus filhos esquerdo e direito. O código-chave do nó no topo do heap é o maior.
Propriedades da pilha
Se i=0, o nó i é o nó raiz e não tem nenhum nó pai, caso contrário, o nó pai do nó i é (i-1)/2
Se 2*i 1>n-1, então o nó i não tem filho esquerdo, caso contrário, o filho esquerdo do nó i é o nó 2*i 1
Se 2*i 1>n-1, então o nó i não tem filho esquerdo, caso contrário, o filho esquerdo do nó i é o nó 2*i 2
Criação de pilha
Ajuste de cima para baixo
Inserção de heap
Exclusão de heap
Aplicativos de pilha
Fila de prioridade
Árvore de Huffman
conceito
caminho
comprimento do percurso
A árvore com o menor comprimento de caminho ponderado é chamada de árvore de Huffman.
Construir árvore huffman
Construa uma floresta de n árvores binárias com apenas nós raiz. Cada árvore binária possui apenas um nó raiz com peso.
Repita as etapas a seguir até que reste apenas uma árvore em F
Selecione os dois menores na floresta de árvores binárias e construa uma nova árvore binária como as subárvores esquerda e direita. O peso do nó raiz da nova árvore binária é a soma dos pesos dos nós raiz das subárvores esquerda e direita. .
Exclua essas duas árvores binárias na floresta de árvores binárias original
Adicionar nova árvore binária à floresta de árvores binárias
codificação huffman
codificação
Na comunicação de dados, o texto transmitido é frequentemente convertido em uma sequência binária composta pelos caracteres binários 0 e 1. Isso é chamado de codificação.
Codificação de comprimento igual
Codificação de comprimento desigual
Compactação de arquivo
árvore de pesquisa binária
natureza
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 do nó raiz
Sua subárvore direita não está vazia, então os valores de todos os nós da subárvore direita são maiores que o valor do nó raiz
Suas subárvores esquerda e direita também são árvores de busca binária, respectivamente.
operar
procurar
Se o nó raiz não estiver vazio
Chave do nó raiz == chave a ser encontrada, retorna verdadeiro
Chave do nó raiz> Chave de pesquisa, pesquise em sua subárvore esquerda
Chave do nó raiz<chave de pesquisa, pesquise em sua subárvore direita
Caso contrário, retorne falso
inserir
Primeiro verifique se o nó já existe. Se existir, não o insira.
Caso contrário, insira o elemento na posição encontrada
excluir
Primeiro determine se está na árvore, sem retornar diretamente
Existem situações
O nó a ser excluído não possui nós filhos
Exclua o nó diretamente
O nó a ser excluído possui apenas o filho esquerdo
Exclua o nó e faça com que o nó pai do nó excluído aponte para o nó filho esquerdo do nó excluído.
O nó a ser excluído possui apenas o filho certo
Exclua o nó e faça com que o nó pai do nó excluído aponte para o nó filho direito do nó excluído.
O nó a ser excluído possui nós filhos esquerdo e direito
Encontre o primeiro nó na ordem intermediária (com o menor código de chave) em sua subárvore direita, preencha-o com seu valor no nó excluído e, em seguida, lide com o problema de exclusão do nó.
Análise de desempenho da árvore de pesquisa binária
No pior caso, o comprimento médio da pesquisa é O(n). Em geral, o comprimento médio da pesquisa é O(lgn).
Árvore AVL
Propriedades da árvore AVL
Suas subárvores esquerda e direita são árvores AVL
O valor absoluto da diferença entre as alturas da subárvore esquerda e da subárvore direita (referido como fator de equilíbrio) não excede 1 (-1, 0, 1)
Se uma árvore for altamente balanceada, é uma árvore AVL. Se tiver n nós, sua altura pode ser mantida em 0(lgn), e a complexidade média da pesquisa é O(lgn)
rotação equilibrada
unirotação esquerda
unirotação direita
rotação dupla esquerda e direita
Rotação dupla direita e esquerda
Inserção de árvore AVL
Se for uma árvore vazia, será o nó raiz após a inserção e retornará verdadeiro diretamente após a inserção.
Se a árvore não estiver vazia, procure a posição de inserção. Se a chave for encontrada durante o processo de pesquisa, a inserção falhará e retornará falso diretamente.
Inserir nó
Atualize o fator de equilíbrio e ajuste a árvore
Exclusão da árvore AVL
O nó excluído tem apenas o filho esquerdo
O fator de equilíbrio do pai é 1 ou -1, e a altura do pai permanece inalterada, então a altura de todos os nós do pai à raiz permanece inalterada e nenhum ajuste é necessário.
O nó excluído tem apenas o filho certo
O fator de equilíbrio do pai torna-se 0. Embora a subárvore enraizada no pai seja balanceada, sua altura é reduzida em 1, mas o equilíbrio do nó pai precisa ser verificado.
O nó excluído tem filhos esquerdo e direito.
Altere para excluir o primeiro nó q na passagem em ordem
Se o fator de equilíbrio do nó pai for 2 ou -2, o número de anões será reduzido, o pai ficará desequilibrado e será necessária uma rotação de equilíbrio.
A raiz da subárvore superior do pai é q
Se o fator de equilíbrio de q for 0, execute um único loop para restaurar o pai
Se o fator de equilíbrio de q tiver o mesmo sinal que o fator de equilíbrio (positivo ou negativo) do pai, execute um único loop para restaurar o pai.
Se o fator de equilíbrio de q tiver sinal oposto (positivo ou negativo) ao fator de equilíbrio (positivo ou negativo) do pai, execute uma rotação dupla para restaurar o pai.
árvore vermelha preta
conceito
A árvore vermelha e preta é uma árvore de busca binária. Ela adiciona um bit de armazenamento a cada nó para representar a cor do nó, garantindo que o caminho mais longo não exceda o dobro do caminho mais curto, que é aproximadamente balanceado.
natureza
Cada nó é vermelho ou preto
O nó raiz da árvore é preto
Se um nó for vermelho, então seus dois nós filhos serão pretos (não há dois nós vermelhos consecutivos)
Para cada nó, os caminhos simples desse nó para todos os seus nós folhas descendentes contêm o mesmo número de nós pretos (o número de nós pretos é igual em cada caminho)
Cada nó folha é preto (os nós folha aqui se referem a nós vazios)
inserir implementação
Se a árvore estiver vazia, o novo nó precisará ser alterado para preto após a inserção.
O nó pai do nó inserido é preto e não viola nenhuma propriedade. Ele pode ser inserido diretamente.
Situação três
Situação quatro
Situação cinco
excluir
usar
Biblioteca C STL - mapear/configurar multimap multiset
Biblioteca Java
núcleo do Linux
algumas outras bibliotecas
Comparação de árvores rubro-negras e árvores AVL