Árvore de classificação binária

árvore binária balanceada

Árvore B (árvore B)

Árvore B

Propriedade básica: calcule o endereço da palavra-chave na tabela com base na palavra-chave fornecida

Método de construção

Métodos de tratamento de conflitos

Classificação por bolha: ① Compare elementos adjacentes. Se o primeiro for maior que o segundo, troque os dois ② Faça o mesmo para cada par de elementos adjacentes, começando pelo primeiro par e terminando no último par. Neste ponto, o último elemento deve ser o maior número ③ Repita as etapas acima para todos os elementos, exceto o último. ④ Continue repetindo as etapas acima para cada vez menos elementos até que não haja pares de números para comparar.

Classificação por seleção simples: suponha que o número de registros na sequência classificada seja n. i pega 1, 2,...,n-1, encontra o registro com o menor código de classificação de todos os registros n-i 1 (Ri, Ri 1,..., Rn) e troca-o com o i-ésimo registro. Após executar n-1 vezes, a classificação da sequência de registros é concluída.

Classificação por inserção direta: primeiro, os primeiros dados são classificados primeiro e, em cada passagem, um dado a ser classificado é inserido na posição apropriada de um grupo de registros que foi classificado de acordo com o tamanho de sua chave. todos os dados a serem classificados são inseridos

Classificação de colina: primeiro pegue um número inteiro d1 menor que n como o primeiro incremento e agrupe todos os registros no arquivo. Todos os registros cuja distância é múltiplo de d1 são colocados no mesmo grupo. Primeiro execute a classificação por inserção direta dentro de cada grupo, depois pegue o segundo incremento d2<d1 e repita o agrupamento e classificação acima até o incremento dt=1 (dt<...<d2<d1)

Classificação de heap: construa a sequência a ser classificada em uma árvore binária e, em seguida, execute ajustes de transposição para garantir que todos os nós filhos sejam menores que seus nós pais. Neste momento, o valor do nó raiz deve ser o valor máximo. e construa uma árvore binária novamente, repita as operações acima.

Classificação de mesclagem bidirecional: ① Forme vários grupos binários e ajuste-os na ordem dentro do grupo ② Mescle os grupos binários ordenados em um grupo e ajuste-os na ordem dentro do grupo ③ Mescle todos os dados em um grupo para completar a classificação

Classificação radical: Configure dez espaços, denominados 0 espaço, 1 espaço,..., 9 espaço Primeiro, corresponda os registros na sequência a cada espaço principal, um por um, de acordo com o valor de um único dígito e coloque-os em cada espaço. Conclua a classificação em cada espaço, retire cada registro do espaço 0 para formar uma nova sequência e repita o trabalho em bits mais altos até que a classificação de bits mais alta seja concluída.

Classificação por mesclagem: divida a sequência inicial em m segmentos de registro menores, classifique esses segmentos de registro e compare continuamente os valores mínimos das extremidades menores de cada segmento de registro até que a classificação seja concluída.

Árvore perdedora: quando a classificação por mesclagem detecta o valor mínimo, se você não usar a árvore perdedora, será necessário comparar os k valores lidos k-1 vezes. Depois de usá-la, você só precisará executar log2k vezes. de selecionar o melhor valor é O (log2k), a complexidade do tempo de construção da árvore é O (klog2k) e a altura da árvore perdedora é [log2k] 1

Classificação por seleção de substituição: De acordo com o tamanho do buffer, um registro é lido da memória externa. Quando o registro preenche o buffer, o menor é selecionado e gravado de volta na memória externa. registro de leitura e o registro de saída se torna o registro inicial atual Parte do segmento mesclado. Se o novo registro inserido for menor que o registro retirado do segmento de mesclagem, ele será gerado como uma alternativa a outros segmentos de mesclagem iniciais. Repita as operações acima

Árvore de mesclagem ideal: segmentos de mesclagem de comprimentos diferentes são obtidos por meio de classificação por seleção de substituição. Cada segmento é colocado em uma árvore de Huffman de acordo com seu comprimento (consulte o capítulo sobre árvores para obter o método). . O dobro da soma do número de arestas passadas pelo nó é o número de E/Ss correspondente à árvore de mesclagem ideal (número mínimo de E/Ss).