Ao converter a uma árvore rubro-negro, há alguma razão para escolher uma forma em detrimento de outro?

Question

Eu tenho uma biblioteca de lista ligada / métodos árvore binária para uso quando contentores normais não cabem - por exemplo, quando existem diferentes tipos de nós, ou quando eu preciso converter de árvore binária a lista e vice-versa. Ele inclui a manipulação de árvore vermelho-preto.

Um dos métodos convertidos de uma lista duplamente ligada a uma árvore binária simples perfeitamente equilibrado no tempo O(n) (dado que o número de itens é conhecido com antecedência). O algoritmo é conhecido como "dobrar" - é a segunda metade de um algoritmo de reequilíbrio árvore binária que uma vez foi publicado no Dr. Dobbs'. Os passos são basicamente ...

• Dado o tamanho da árvore, decidir sobre os tamanhos das subárvores esquerda e direita

• Recurse para a sub

  esquerdo

• Pop um nó da lista para usar como a raiz

• Recurse para a subárvore direita

• ligar as sub-árvores para a raiz

Eu também tenho um método semelhante que cria uma árvore rubro-negro. O princípio é o mesmo, mas a recursão mantém o controle de altura nó - altura zero de nós são criados vermelho, todos os outros são pretos. O cálculo altura inicial é baseado no maior conjunto de bits no tamanho da árvore, e é brincava de modo que uma árvore de porte (2^n)-1 perfeitamente equilibrado tem apenas nós negros (a recursão só vai até a altura um).

O ponto aqui é que eu só tenho nós vermelhos no nível folha, e um máximo de precisamente metade dos nós são vermelhos.

A coisa é, enquanto esta é uma maneira simples de gerar uma árvore rubro-negro válida, não é a única opção. Evitando ter todas as folhas vermelhas em uma árvore perfeitamente equilibrado foi uma escolha arbitrária. Eu poderia ter camadas alternadas de nós vermelhos e pretos. Ou eu poderia reduzir o número de nós vermelhos dramaticamente em alguns casos, através da identificação de sub-árvores que são perfeitamente equilibrado e (se ele precisa de nós vermelhos) fazendo a raiz sub vermelho em vez de todas as suas folhas.

A questão é -? Não há qualquer razão prática para escolher uma forma de árvore vermelho-preto válida sobre outra

Isso é pura curiosidade - Eu sei que eu não tenho nenhuma razão prática - mas alguém sabe de uma aplicação especializada onde esta escolha é significativa

Answer 1

Na análise padrão do custo amortizado de modificar árvores vermelhas e pretas usando o método do pysicist, nós pretos com zero ou dois filhos vermelhos são atribuídos a um potencial positivo de um, o que significa que eles representam lugares problemáticos na árvore onde adicional trabalho talvez precise ser feito. nós vermelhos e nós pretos com exatamente uma criança vermelho é atribuído um potencial de zero.

Assim, para reduzir o custo das modificações, dar a cada nó preto uma criança vermelho.

---

O razão É por isso que nós pretos com uma criança vermelho são abençoados explicou melhor por analogia com redundantes números binários. Primeiro vou explicar como se relacionar árvores vermelho-pretas para números binários e depois vou explicar por que nós one-vermelho-filho são úteis.

Como você deve saber, árvores vermelho-pretas são uma forma de representar 2-4 árvores, em que cada caminho simples da raiz para uma folha tem o mesmo comprimento, mas nós têm 2, 3 ou 4 filhos. O algoritmo mais simples para adicionar ou remover um nó em uma árvore 2-4 é o mesmo algoritmo como adicionar ou subtrair um de um número binário redundante .

A redundante binário número é um número em que o dígito om representa 2 ⁱ , assim como em um número binário padrão, mas o dígito om pode ser 0, 1, ou 2 . Eles são chamados redundante porque existem várias maneiras de escrever um determinado número. 4 _dezembro pode ser escrita 100 ou 20 ou 12.

Para adicionar um para um número binário redundante, você incrementar o dígito menos significativo; se for 3, configurá-lo para um e incrementar o próximo menos significativo dígitos, e assim por diante. As paradas algoritmo quando encontrar um 0 ou 1.

Para adicionar uma folha de uma árvore 2-4, adicionar um filho a seu pai pretendido. Se o pai como tem cinco filhos, dividi-lo em dois nós e torná-los filhos de seu pai. Continue até chegar a um nó que não precisa de divisão. Assim, o caminho para as paradas de raiz quando encontra um nó com dois ou três filhos.

Para obrigado o custo amortizado de incrementar um número binário redundante, use o método físicos e atribuir um potencial de 1 a cada 2 dígitos. Um XALL ao incremento que dígitos toques k lançamentos k-1 potencial, dando-lhe um custo amortizado de O (1).

Essa análise é semelhante ao custo amortizado de incrementar um número binário padrão, mas um número binário padrão não pode suportar tanto incremento e decremento em O (1) amortizado tempo: considerar 2 ^k - 1. é k 1 dígitos. Incremento custos T (k). Se isso é seguido por um decréscimo, o par custa T (k) e traz o número de volta ao seu antigo estado.

binário redundante é especial em que 1 dígitos interromper as operações em cascata de aumentar e diminuir. 2-4 árvores são especiais em que o 3-nós de parar as operações em cascata de ambos inserção e exclusão.

Em árvores vermelhas e pretas, um nó com um filho vermelho é apenas uma representação de um 3-nó em uma árvore 2-4. Estes nós são especiais e robusta contra inserções ou exclusões em suas sub-árvores, então você deve favorecê-los na construção de árvores vermelhas e pretas que vão ver um monte de atualizações.

Se você sabe que vai ver apenas inserções, favorecem nós com duas crianças negras. Se você sabe que vai ver apenas exclusões, nós favor com duas crianças vermelhas.

Answer 2

A resposta curta é: isso depende

.

Basicamente, qualquer árvore válido será suficiente. No entanto, em termos de amortizado análise - que poderia muito possivelmente ser que você vai querer escolher o mais árvore correta que, a longo prazo, irá dar-lhe o comportamento mais otimizado.

por exemplo. se você sempre escolher uma árvore válida, mas um que é propenso a muitas operações de equilíbrio, você vai ter mau desempenho amortizado. Um exemplo óbvio é uma árvore totalmente preto, o que é perfeitamente válido, ainda executa mal quando modificado.

Depende, porque isso geralmente será específico do aplicativo.