Por muito tempo lutei com a árvore vermelho-preto ( doravante - kchd ). Todas as informações que encontrei foram no espírito de "as folhas e a raiz da árvore são sempre pretas PORQUE", "5 principais propriedades de uma árvore vermelho-preta" ou "3 casos ao balancear e 12 casos ao remover um nó". Este arranjo não me convinha.
Eu não queria memorizar as propriedades da árvore, pseudocódigos e opções de balanceamento, queria saber por quê. Como as cores ajudam no equilíbrio? Por que um nó vermelho não pode ter um filho vermelho? Por que a profundidade de uma árvore é medida com a "altura negra"?
Recebi respostas a essas perguntas apenas quando recebi um link para uma palestra sobre duas ou três árvores, com a qual começaremos.
Este artigo está dividido em 3 partes lógicas. Eu recomendo lê-los na ordem mostrada. A primeira parte (esta) terá como objetivo uma introdução ao ccd e como conhecê-lo. Na segunda parte, falaremos sobre balanceamento e inserção no ccd. Na terceira e última parte, analisaremos o processo de exclusão de um nó. Por favor, seja paciente e goste de ler :)
Isenção de responsabilidade
Neste artigo, não haverá informações sobre os prós e contras da árvore, sua aplicação, etc .: há muitas informações sobre a assintótica da árvore e como trabalhar com ela na Internet.
O material é direcionado para aqueles que já estão familiarizados com o ccd e agora querem entendê-los, bem como para aqueles que estão apenas começando a conhecê-los.
O artigo não conterá detalhes da implementação da estrutura.
— . .
-
- , -
, , - - , , , . - - .
- - , . - ( , ). 2-, - 3-. : . :
, .
- , - .
- - , .
, , 5. - 5 .
12. 12 (, ), "" ( , ), .. . 5-12.
. 17. . 5-12-17.
- , . ! "" . . 12, 5, - 17.
, , - . : , "" . 3 :
. , ( ).
. ( ).
. , .
.
, . 3. , . , 3 5. 3 5 . 3-5.
, :)
4 3-5. 3-4-5, , , . ? , .. "" 4 .
. , 4 , - , 4. 5. :
5 ? : - , - . 5 4, 5 , .. . 5 , "", 4-12 (, 5 , "" ).
, . :
, , .
, , , .
, , .
, . , , - . , - (, 4-5-12, , 5 4 12). , . , , ( , 7? 9?).
, , , . , , , . .
, , , . , , ( ). - .
-
, - - . - . ?
, 3-. 3- 2- . - , , , ( ), .
, , .
, - . , , ( , ).
-
, - , , 3- ( ). , , . , ( ).
1.
. , , - 3- 2-3 . , 4-, :)
2.
. , : .
3.
null- (, ) - . , . , , .
Visto que tocamos em nós nulos, deve-se dizer que todos os nós na árvore devem sempre ter dois descendentes, e se a referência ao descendente for zero, então ela leva exatamente ao nó nulo. Na verdade, isso levanta uma questão na implementação, era mais conveniente para mim adicionar um nó nulo (menos problemas com iteradores, balanceamento, etc.).
Propriedade 4.
A altura da árvore é medida apenas por nós pretos e é chamada de "altura preta". Aqui, novamente, tudo em geral se torna óbvio: o nó vermelho é apenas um acréscimo ao nó preto, é uma parte dele, portanto, a altura é considerada baseada nos nós pretos.
Isso conclui a introdução. Na próxima parte, falaremos sobre como inserir nós em uma árvore e equilibrá-la.