Uma árvore vermelha e preta é uma árvore de pesquisa equilibrada binária. Cada nó tem um bit de armazenamento para representar a cor do nó, que pode ser vermelha ou preta.
Árvores vermelhas e negras têm as seguintes propriedades:
(1) Cada nó é vermelho ou preto
(2) O nó raiz é preto
(3) Se um nó é vermelho, seus dois filhos são pretos
(4) Para cada nó, todos os caminhos desse nó para seus descendentes contêm o mesmo número de nós pretos.
Através das propriedades da árvore vermelha-preta, é garantido que todas as implementações baseadas em árvores vermelhas-pretas possam garantir que o tempo de execução da operação seja logarítmico (exceto a pesquisa de intervalo. O tempo extra necessário é proporcional ao número de chaves retornadas).
O Treemap de Java é implementado através de árvores vermelhas e negras.
Se você não desenhar um desenho, é fácil ficar confuso. A seguir, é apresentado um diagrama para ilustrar a operação de inserção da árvore vermelha e preta.
Depois de inserir um nó vermelho na árvore vermelha e preta, haverá 6 situações: n representa o nó inserido, p representa o nó pai, u representa o nó do tio, g representa o nó do avô e x representa o nó de operação atual
O código é o seguinte:
classe pública Redblackbst <Key estende comparável <Key>, value> {private node root; private estático final booleano vermelho = true; Private estático final booleano preto = falso; Nó da classe privada {chave privada -chave; // Chave de valor privado val; // Valor nó privado esquerdo, direito, pai; // Árvores infantis esquerdo e esquerdo e nó dos pais Private Boolean Color; // a cor do link apontada por seu nó de pai pai (chave de chave, value val, nó pai, cor booleano) {this.key = key; this.val = val; this.color = cor; }} valor público get (chave da chave) {nó x = root; while (x! = null) {int cmp = key.compareto (x.key); if (cmp <0) x = x.left; else if (cmp> 0) x = x.right; caso contrário, retorne x.val; } retornar nulo; } public void put (chave da chave, value val) {if (root == null) {// Se for um nó raiz, crie o nó como root preto = novo nó (chave, val, nulo, preto); retornar; } // Encontre um nó de inserção adequado pai pai = null; Nó cur = root; while (cur! = null) {parent = curs; if (key.compareto (cur.key)> 0) cur = cur.right; else cur = cur.left; } Nó n = novo nó (chave, val, pai, vermelho); // Ord Norm Node Node Normal está vermelho // Insira o novo nó em Pai se (key.compareto (parent.key)> 0) parent.right = n; else parent.left = n; // Depois de inserir um novo nó, você deve ajustar as cores e propriedades de alguns nós na árvore para garantir que as características da árvore vermelha e preta não sejam destruídas. FixAfterInserção (n); } nó privado parentef (nó x) {return (x == null? null: x.parent); } colorof booleano privado (nó x) {return (x == null? null: x.right); } nó privado esquerdo (nó x) {return (x == null? null: x.right); } nó privado direito (nó x) {return (x == null? null: x.right); } private void setColor (nó x, cor booleano) {if (x! = null) x.color = color; } private void fixAfterInsertion (nó x) {while (x! Nó pai = paif (x); if (parent == leftOf (vovPa)) {// case 1 || case2 || case3 nó tio = rightOf (vovô); if (colorof (tio) == vermelho) {// case1, tio é vermelho setColor (pai, preto); // O nó pai é preto setColor (tio, preto); // O nó do tio é Black SetColor (vovô, vermelho); // O nó do avô é vermelho x = vovô; // porque o nó do avô é vermelho de preto para vermelho, os atributos vermelhos e pretos do nó pai e seus ancestrais precisam ser reajustados} else {// case2 || case3, tio é preto if (x == rightOf (pai)) {// case2 x = pai; rotateleft (x); } // case3 setColor (pai, preto); setColor (vovô, vermelho); Rotateright (vovô); }} else {// case4 || Caso 5 || case6 tio do nó = esquerda (vovô); if (colorof (tio) == vermelho) {// case4 || case5 || case6 setColor (pai, preto); setColor (tio, preto); setColor (vovô, vermelho); x = vovô; } else {// case5 || case6, tio é preto if (x == leftOf (pai)) {// case5 x = pai; Rotateright (x); } // case6 setColor (pai, preto); setColor (vovô, vermelho); Rotateleft (vovô); }}}} private void rotateleft (nó x) {if (x == null) return; Nó y = x.right; x.right = y.left; if (y.left! = null) y.left.parent = x; y.left = x; y.parent = x.parent; if (x.parent == null) {root = y; } else if (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; } private void roTateright (nó x) {if (x == null) return; Nó y = x.left; x.left = y.right; if (y.right! = null) y.right.parent = x; y.right = x; y.parent = x.parent; if (x.parent == null) {root = y; } else if (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; }}É necessário desenhar um diagrama para o Rotateleft e Rotateright acima:
O artigo acima é baseado no princípio da operação de inserção de árvores vermelha e preta e método de implementação de Java (compartilhamento), que é todo o conteúdo que compartilho com você. Espero que você possa lhe dar uma referência e espero que você possa apoiar mais o wulin.com.