Início » Aulas » [ED] Aula 106 – Árvore Rubro Negra Caída para a Esquerda (LLRB)

[ED] Aula 106 – Árvore Rubro Negra Caída para a Esquerda (LLRB)

Olá caros alunos,

Hoje iremos ver como funciona uma árvore rubro-negra caída para a esquerda (do inglês, left-leaning red–black tree), uma variante da árvore rubro-negra desenvolvida por Robert Sedgewick em 2008. Como a árvore rubro-negra original, ela garante a mesma complexidade de operações, mas possui um implementação mais simples na inserção e remoção de nós.

Além de satisfazer todas as propriedades da árvore rubro-negra convencional, a árvore rubro-negra caída para a esquerda possui uma propriedade extra que deve ser respeitada: se um nó é vermelho, então ele é o filho esquerdo do seu pai. É essa propriedade extra da árvore que confere o seu aspecto de caída para a esquerda: os nós vermelhos sempre são filhos à esquerda.

Vamos para a aula e até semana que vem!


Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: