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

natureza

procurar

característica

Adicione ponteiros para irmãos entre os nós não-raiz e não-folha da árvore B

Subtópico 2

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

estrutura de pesquisa

Contexto de pesquisa

pesquisa estática

pesquisa dinâmica

Pesquisa de hash

Colisão de hash

Função hash

Funções hash comuns

hash fechado

hash aberto

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 um conjunto de dados confusos de acordo com uma determinada regra (ordem crescente ou decrescente)

Ficha de dados

Código 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

ordenação por inserção

ordenação por seleção

classificação de troca

classificação por mesclagem

classificação não comparativa

vértice

lado

gráfico direcionado

Gráfico não direcionado

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.

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

o número de arestas associadas a ele

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.

Informações de dados anexadas à borda

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.

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.

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.

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.

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.

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.

matriz de adjacência

lista de adjacências

profundidade primeiro

largura primeiro

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.

critério

Ao resolver problemas, faça sempre a escolha que lhe parecer melhor no momento, ou seja, a solução ótima local.

Encontre uma aresta com o peso mais curto e não mais no mesmo componente conectado todas as vezes para adicionar à árvore geradora.

Encontre um ao lado do outro

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.

dados

elemento de dados

Item de dados

estrutura de dados

conceito específico

algoritmo

estrutura de dados

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

Requisitos de algoritmo de design

situação média

pior cenário

Melhor cenário possível

Algoritmo geral O(n) método de cálculo

Cálculo de complexidade de tempo do algoritmo de divisão e conquista

Cálculo de complexidade de tempo do algoritmo recursivo

Algoritmo Recursivo Algoritmo de Complexidade Espacial

Dizemos que um objeto é recursivo se ele se contém parcialmente ou se define por si mesmo.

Um procedimento chama a si mesmo direta ou indiretamente

Divida o problema em problemas menores que tenham a mesma solução do problema original

Reduza o tamanho do problema para que o novo problema tenha a mesma solução que o problema original

Definir saída recursiva

recursão de estrutura de dados

recursão de resolução de problemas

pilha de chamadas recursiva

recursão de cauda

complexidade de tempo

Retrocesso

vantagem

deficiência

Um tipo especial de tabela linear que permite apenas a inserção e exclusão de dados de uma extremidade

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.

Um array implementa duas pilhas

princípio

Cenários de aplicação

Plugue de cabeça excluído

correspondência de colchetes

Expressão polonesa reversa

algoritmo de labirinto

Método de implementação um

Método de implementação dois

falso estouro

Verdadeiro fenômeno de estouro

Uma fila de armazenamento sequencial conectada de ponta a ponta é uma fila circular.

Determinando se a fila está cheia ou vazia

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

modelo produtor-consumidor

fila de mensagens

fenômeno da fila

Transmissão de dados em rede

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

Uma matriz N*N, qualquer Aij = Aji

Armazenamento de compressão de matriz simétrica

A relação entre matrizes simétricas e armazenamento compactado simétrico

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

Trocando linhas e colunas

Retrocesso rápido

Um conjunto composto por N nós (N>=0)

Nó

grau de nó

nó com grau 0

nó de ramificação

nó ancestral

Nó descendentes

nó pai

nó filho

Nó irmão

grau de árvore

Nível do nó

profundidade da árvore

árvore ordenada

árvore não ordenada

floresta

Estrutura de diretório

Diagrama de Venn de coleção

representação dos pais

representação infantil

Representação pai-filho

representação do irmão menor

diretório de computador

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.

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.

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.

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.

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:

armazenamento sequencial

armazenamento em cadeia

Ponteiro de simulação (lista vinculada estática)

Criação de árvore binária

Travessia de árvore binária

Converta a árvore binária em uma sequência linear de acordo com o percurso da árvore binária

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,

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.

A função é distinguir se é um nó filho, um precursor ou um sucessor.

leftThread

thread à direita

Ponteiro para o nó predecessor ou sucessor no nó

Árvore binária com nós de árvore binária mais pistas

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)

pilha pequena

pilha grande

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

Ajuste de cima para baixo

Fila de prioridade

caminho

comprimento do percurso

A árvore com o menor comprimento de caminho ponderado é chamada de árvore de 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

codificação

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.

procurar

inserir

excluir

Análise de desempenho da árvore de pesquisa binária

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)

unirotação esquerda

unirotação direita

rotação dupla esquerda e direita

Rotação dupla direita e esquerda

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

O nó excluído tem apenas o filho esquerdo

O nó excluído tem apenas o filho certo

O nó excluído tem filhos esquerdo e direito.

A raiz da subárvore superior do pai é q

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.

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)

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

Biblioteca C STL - mapear/configurar multimap multiset

Biblioteca Java

núcleo do Linux

algumas outras bibliotecas