Árvore vermelha e preta
Árvores vermelhas e negras são árvores que são frequentemente mencionadas em estruturas e algoritmos de dados, mas que não podem ser explicados em detalhes. Eles também são árvores que costumam ser solicitadas em entrevistas técnicas. No entanto, sejam os materiais em livros ou on -line, eles geralmente são mais rígidos e difíceis de entender. Você pode entender as árvores vermelhas e negras de uma maneira mais intuitiva? Este artigo explicará as operações de inserção e exclusão de árvores vermelhas e negras de maneira gráfica.
Aprender a estrutura da árvore é um processo progressivo. As árvores com as quais costumamos entrar em contato são árvores binárias. Em termos simples, cada nó não folhas tem e apenas dois filhos, chamado de criança esquerda e criança certa. Há um tipo especial de árvore em uma árvore binária chamada árvore de busca binária. Uma árvore de busca binária é uma árvore ordenada. Para cada nó não folhas, o valor de sua subárvore esquerda é menor que ele, e o valor de sua subárvore direita é maior que ele. Outra etapa do que uma árvore de busca binária é uma árvore de equilíbrio binário. Além de garantir a ordem, a árvore de equilíbrio binária também pode manter a diferença de altura entre as subárvores esquerda e direita de cada nó e não mais que 1. Árvores comuns e balanceadas são árvores AVL, Treps, Red e Black, árvores esticadas e assim por diante.
Uma árvore vermelha e preta é uma árvore de pesquisa binária, mas adiciona um bit de armazenamento a cada nó para representar a cor do nó, que pode ser vermelha ou preta. Ao limitar como cada nó está sombreando em qualquer caminho de raiz para folha, a árvore vermelha-preta garante que nenhum caminho seja duas vezes mais que os outros caminhos, aproximando-se do equilíbrio.
A árvore vermelha e preta satisfaz 5 propriedades:
Observe que em uma árvore preta, aponte o filho do nó foliar da árvore binária tradicional para nulo e chame de nulo de nó da folha na árvore preta vermelha. O nó nulo contém um ponteiro para o nó pai, o que pode ser a razão pela qual o NULL é necessário para ser alterado para nulo.
1. Inserir operação
Primeiro, insira o novo nó na maneira de inserir a árvore de busca binária (os novos nós inseridos estão todos nos nós da folha) e desenhe -o em vermelho. Em seguida, redesenhe sua cor ou gire -a para manter as propriedades da árvore vermelha e preta. O ajuste é dividido nas três situações a seguir:
1 novo nó n não tem nó pai (ou seja, está localizado na raiz)
Pinte o novo nó n como preto.
2 O nó pai P do novo nó n é preto
Não há necessidade de ajustar.
3 O nó pai P do novo nó n é vermelho
Como a árvore vermelha e preta não permite dois nós vermelhos consecutivos (propriedade 4), ela precisa ser ajustada. De acordo com a cor do nó do tio de n, ele é dividido em duas situações: (tomamos o nó dos pais de N como o filho esquerdo como exemplo, e P como criança certa como uma situação semelhante, para que não o explique em detalhes)
3.1 O tio nó U do novo nó n é vermelho. O nó pai P e o tio U do novo nó n são pintados como pretos, e o nó do avô G é pintado como vermelho, de modo a garantir que o número de nós pretos contidos no caminho de G para cada nó nulo seja consistente com o original. Mas como transformamos G em vermelho, se o pai de G também estiver vermelho, isso pode levar a dois nós vermelhos consecutivos (violando a natureza 4), por isso é necessário verificar novamente se G viola a natureza da árvore vermelha e preta.
3.2 O nó do tio U do novo nó n é preto. Se o novo nó n for o filho esquerdo de seu nó pai P: desenhe seu nó pai P como preto, desenhe seu nó do avô G como vermelho e depois gire G para a direita uma vez.
Se o novo nó n for o filho certo de seu nó pai: executar uma rotação esquerda em seu nó pai, o problema será transformado na situação do filho esquerdo.
2. Excluir operação
The method in "Introduction to Algorithms" and Wikipedia is to delete a black node D, "push down" the black of D to its child node C, that is, C has an extra layer of black in addition to its own color, and then continue to move the extra layer of black along the tree until it encounters a red node, and turns it into black to ensure that the number of black nodes on the path remains unchanged, or move to the root of the tree, para que o número de nós pretos em todos os caminhos seja reduzido por um e permaneça igual. Durante o movimento ascendente, algumas cores do nó podem precisar ser giradas e modificadas para garantir que o número de nós pretos no caminho permaneça inalterado.
Essa abordagem pode ser benéfica para a implementação do código (que pode ser usada de maneiras iterativas), mas não é conveniente entender (acreditar pessoalmente). Para fins de compreensão da prioridade, fiz a seguinte classificação com base se o filho do nó excluído D é nulo:
1 Ambas as crianças cujo nó D foi excluído são nil
1.1 Se o nó excluído D estiver vermelho, basta substituir D por Nil.
1.2 O nó excluído D é preto (vamos tomar d como exemplo)
1.2.1 Ambos os filhos do nó B, cujo irmão D, foram excluídos, são nulos
O nó do irmão B de D é pintado como vermelho e o nó pai P é pintado como preto.
Meio vermelho e meio preto na figura significa que o nó pode ser vermelho ou preto. Se P acabou sendo vermelho, o número de nós pretos no caminho após a modificação é o mesmo de antes da exclusão d; Se P acabou sendo preto, a exclusão de D resultará em um número a menos de nós pretos no caminho do que antes da exclusão; portanto, você precisa continuar a verificar se a alteração no número de nós pretos no caminho que passa através de P afeta as propriedades da árvore vermelha e preta.
1.2.2 O Nó Brother B do Nó D tem um filho não nil
A criança deve estar vermelha, caso contrário, o número de nós pretos no caminho do nó pai de D para cada nó da folha variará (violação 5).
Se essa criança for a criança certa, desenhe o filho certo de B como preto, desenhe B como a cor original de seu nó pai, desenhe P como preto e depois gire P com uma esquerda.
Se essa criança for a criança esquerda, desenhe o filho esquerdo de B como preto, B como vermelho e depois gire B bem uma vez, o problema será transformado na situação da criança certa.
1.2.3 Ambos os filhos do nó B, que foram excluídos, não são nulos
Se B é vermelho, os dois filhos de B devem ser negros. Desenhe B como Black, o filho de esquerda de B como vermelho e depois realizar uma rotação esquerda de P.
Se B é preto, os dois filhos de B devem ser vermelhos. Desenhe o nó dos pais de B como preto, o filho direito de B como preto, a cor original de B como seu nó pai e depois gire P com um esquerdo.
2 Ambas as crianças cujo nó D foi excluído não são nil
De acordo com a árvore de busca binária para excluir nós, encontre os nó sucessores de D, troca o conteúdo de D e S (a cor permanece inalterada) e o nó excluído se torna S. Se s tiver um nó que não for nulo, continue a substituir S pelo nó sucessor de S até que ambos os filhos do nó excluído sejam nil. O problema se transforma na situação em que os dois filhos do nó excluído D são nulos.
3 nó excluído D tem um filho não nulo
Essa criança C deve ser um nó vermelho, caso contrário, o número de nós pretos no caminho de D para cada nó nulo será diferente (violação 5).
O conteúdo de D e C são trocados (a cor permanece a mesma), o nó excluído se torna C e o problema se transforma na situação em que ambos os filhos do nó excluído d são nulos.
Travessia de árvores binárias
Existem três tipos de travessias em árvores binárias: travessia de pré -encomenda, travessia média e travessia postorder. Existem dois tipos de implementações de travessia: recursão e iteração. Neste artigo, discutiremos como usar o código mais elegante para implementar a travessia de árvores binárias.
Primeiro, vou definir um nó de uma árvore binária:
classe pública Treenode {int val; Treenode para a esquerda; Treenode à direita; public treenode (int x) {val = x; }}
1. Travessal de pré -encomenda
Simplificando, a Traversal de pré-encomenda deve primeiro acessar o nó pai, depois acessar o filho esquerdo e, finalmente, acessar a criança certa, ou seja, para atravessar na ordem dos pais, à esquerda e à direita.
A implementação recursiva é muito simples, o código é o seguinte:
classe pública Solução {List <Teger> resultado = new ArrayList <Teger> (); Lista pública <Integer> pré -encomendTraversal (Treenode Root) {dfs (root); resultado de retorno; } private void dfs (root Treenode) {if (root == null) {return; } resultado.add (root.val); dfs (root.left); dfs (root.right); }} A implementação iterativa requer uma pilha para armazenar o nó certo que não é acessado. O código é o seguinte:
classe pública Solução {Lista pública <TEGER> PreMerTraversal (Treenode Root) {List <Teger> resultado = new ArrayList <Teger> (); if (root == null) {return resultado; } Pilha <Treenode> pilha = new Stack <Treenode> (); Stack.push (raiz); while (! Stack.isEmpty ()) {Treenode curr = Stack.pop (); resultado.add (curr.val); if (curr.right! = null) {staack.push (curr.right); } if (curr.left! = null) {Stack.push (curr.left); }} Retornar resultado; }}
2. Traversal inorder
Simplificando, a Traversal da Ordem Média é acessar primeiro o filho esquerdo, depois acessar o nó pai e, finalmente, acessar a criança certa, ou seja, travessia na ordem da esquerda, pai e direita.
O código recursivo também é mais fácil, como mostrado abaixo:
classe pública Solução {Lista pública <Teger> inOrderTraversal (Treenode Root) {List <Teger> resultado = new ArrayList <Teger> (); recorrente (raiz, resultado); resultado de retorno; } private void Recurse (ROOT TREENODE, LIST <Integer> resultado) {if (root == null) retornar; recorrente (root.left, resultado); resultado.add (root.val); recorrente (root.right, resultado); }} O método de escrita acima é diferente do código recursivo de travessia de pré -encomenda. Utilizamos variáveis de membro para armazenar os resultados da Traversal na travessia de pré -encomenda, e aqui usamos parâmetros de método para salvar os resultados da Traversal. Ambos os métodos de escrita estão OK, use o que você quiser.
A implementação iterativa da travessia de ordem média não é tão simples quanto a travessia de pré-encomenda. Embora também exija uma pilha, as condições para a terminação iterativa são diferentes. Imagine que, para uma árvore binária, o nó que acessamos primeiro é o nó mais à esquerda. É claro que podemos alcançar o nó mais à esquerda por um loop de tempo, mas quando recuamos, como sabemos se o filho esquerdo de um nó foi acessado? Usamos uma variável curr para registrar o nó atualmente acessado. Quando acessamos o nó direito de uma subárvore, devemos voltar ao nó pai da subárvore. No momento, o curr é nulo, para que possamos usar isso para distinguir se a subárvore esquerda de um nó foi acessada. O código é o seguinte:
classe pública Solução {Lista pública <Teger> inOrderTraversal (Treenode Root) {List <Teger> resultado = new ArrayList <Teger> (); Stack <reenode> pilha = new Stack <Treenode> (); Treenode curr = root; while (curr! = null ||! Stack.isEmpty ()) {while (curr! = null) {Stack.push (curr); curr = curr.left; } curr = Stack.pop (); resultado.add (curr.val); curr = curr.right; } resultado de retorno; }}
3. Travessal da Postome
Simplificando, a travessal de pós-ordem é acessar primeiro o filho esquerdo, acessar a criança certa e, finalmente, acessar o nó pai, ou seja, travessia na ordem da esquerda, direita e pai.
Ao imitar a travessia da ordem do meio, você pode escrever facilmente uma implementação recursiva da travessia de pós-ordem:
classe pública Solução {Lista pública <Teger> PostOrderTraversal (Treenode Root) {List <Teger> resultado = new ArrayList <Teger> (); recorrente (raiz, resultado); resultado de retorno; } private void Recurse (ROOT TREENODE, LIST <Integer> resultado) {if (root == null) retornar; recorrente (root.left, resultado); recorrente (root.right, resultado); resultado.add (root.val); }} A iteração da travessia de pós-ordem também requer uma identificação para distinguir se os filhos esquerdo e direito de um nó foram acessados. Caso contrário, as crianças esquerda e direita serão acessadas por sua vez. Se tiver sido acessado, o nó será acessado. Para esse fim, usamos uma pré -variável para representar o nó que visitamos. Se o nó que visitamos for o filho esquerdo ou direito do nó atual, significa que os filhos esquerdo e direito do nó atual foram acessados e, em seguida, podemos acessar o nó. Caso contrário, precisamos entrar nas crianças esquerda e direita para acessá -lo por sua vez. O código é o seguinte:
classe pública Solução {Lista pública <Teger> PostOrderTraversal (Treenode Root) {List <Teger> resultado = new LinkedList <Teger> (); Stack <reenode> pilha = new Stack <Treenode> (); if (root! = null) pilha.push (root); Treenode pre = root; while (! Stack.isEmpty ()) {Treenode curr = Stack.peek (); if (curr.left == pre || curr.right == pre || (curr.left == null && curr.right == null)) {result.add (curr.val); Stack.pop (); pre = curr; } else {if (curr.right! = null) Stack.push (curr.right); if (curr.left! = null) pilha.push (curr.left); }} Retornar resultado; }} Há outra implementação relativamente simples da iteração da travessia de pós-ordem. Sabemos que a ordem da travessia de pré-encomenda é pai, esquerda e direita, enquanto a ordem da travessia de pós-ordem é deixada, à direita e pai. Portanto, se modificarmos ligeiramente a travessia de pré-encomenda e a alterarmos para a ordem dos pais, à direita e à esquerda, é exatamente o oposto da ordem da travessia de pós-ordem. Depois de acessá -lo nesta ordem, podemos inverter o resultado do acesso no final. A implementação iterativa da travessia de pré-encomenda é relativamente fácil. De acordo com o método de escrita acima, podemos implementá -lo da seguinte maneira:
classe pública Solução {Lista pública <Teger> PostOrderTraversal (Treenode Root) {List <Teger> resultado = new LinkedList <Teger> (); Stack <reenode> pilha = new Stack <Treenode> (); if (root! = null) pilha.push (root); while (! Stack.isEmpty ()) {Treenode curr = Stack.pop (); resultado.add (curr.val); if (curr.left! = null) pilha.push (curr.left); if (curr.right! = null) pilha.push (curr.right); } Coleções.Reverse (resultado); resultado de retorno; }}
4. Resumo
A implementação recursiva dos três travessia é fácil. É melhor escrever a implementação da iteração da travessia de pré -encomenda, e apenas uma pilha é necessária; A travessia de ordem média é a mais difícil. Além de determinar se a pilha está vazia, a condição do loop também precisa determinar se o nó atual está vazio para indicar se a subárvore esquerda foi atravessada; Se a iteração da travessia subsequente for convertida em iteração de travessia de pré -encomenda, é muito mais fácil. Caso contrário, também é necessário registrar o nó de acesso anterior para indicar se as subáridas esquerda e direita do nó atual foram acessadas.