Rubro-negra

Árvore Rubro-Negra
Siang Wun Song - Universidade de São Paulo - IME/USP

MAC 5710 - Estruturas de Dados - 2008

Siang Wun Song - Universidade de São Paulo - IME/USP

Árvore Rubro-Negra

Referência bibliográfica

Os slides sobre este assunto são parcialmente baseados no capítulo 13 do livro
T. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein.
Introduction to Algorithms, second edition, The MIT Press,
2005.

Siang Wun Song - Universidade de São Paulo - IME/USP

Árvore Rubro-Negra

Árvores binárias de busca balanceadas
Numa árvore binária de busca com n chaves e de altura h, as operações de busca, inserção e remoção têm complexidade de tempo O(h).
No pior caso, a altura de uma árvore binária de busca pode ser O(n). No caso médio, vimos que a altura é O(log n).
Árvores AVL, árvores 2-3 e árvores rubro-negras são alguns tipos de árvores binárias de busca ditas balanceadas com altura O(log n).
Todas essas árvores são projetadas para busca de dados armazenados na memória principal (RAM).
As árvores 2-3 são generalizadas para as chamadas
B-árvores, que veremos mais tarde, para busca eficiente de dados armazenados em memória secundária (disco rígido). Veremos a árvore rubro-negra cuja altura é no máximo igual a 2 log(n + 1).
Siang Wun Song - Universidade de São Paulo - IME/USP

Árvore Rubro-Negra

Árvore rubro-negra

Uma árvore rubro-negra é uma árvore binária de busca em que cada nó é constituído dos seguintes campos: cor (1 bit): pode ser vermelho ou preto. key (e.g. inteiro): indica o valor de uma chave. left, right: ponteiros que apontam para a subárvore esquerda e direita, resp. pai: ponteiro que aponta para o nó pai. O campo pai do nó raiz aponta para nil.
O ponteiro pai facilita a operação da árvore rubro-negra, conforme será visto a seguir.

Siang Wun Song - Universidade de São Paulo - IME/USP

Árvore Rubro-Negra

Uma árvore rubro-negra

26

$

$$
$$$

$$ˆˆˆ

ˆˆˆ

ˆˆ

17

41

d d