Red Black Tree

Introdução

Árvore Preto-Vermelho

Rudolf Bayer: "Symmetric BinaryTrees: Data Structures and
Maintenance Algorithms." Acta
Informat. 1, 290-306, 1972.





Rohit Gheyi [e-mail] O nome atual em 1978 por Leonidas
J. Guibas e Robert Sedgewick

Estrutura de dados que se mantém balanceada  Eficiente na prática


1

2

Características

Invariante

Árvore Binária de Pesquisa
 Cada nó possui uma cor

1.






Um nó é preto ou vermelho
Os nós folha são pretos
Os filhos de um nó vermelho são pretos
Qualquer caminho descendente de um nó até um nó folha possui o mesmo número de nós pretos (nós que possuem chaves)

2.

Preto
Vermelho

3.
4.

Nenhuma altura é maior do que o dobro da outra (razoavelmente balanceada)
 Objetivo







Remover o problema do pior caso onde a altura é
O(n)

5.

Black-height(x)
Começa a contar a partir do filho

A raiz é preta

3

Exemplo

4

Exercício 1


Considere que os nós folhas são NIL
(cor preta e sem chave) Quais destas árvores são preto-vermelho?
42

42

44

40

50

50

42

Não é BST

40

50

Nó folha

Nó 42
5

6

1

Exercício 2


Altura

Qual o black-height do nó 7?




2
O black-height da raiz é o black height da árvore pv



Uma árvore preto-vermelho com n nós internos tem no máximo a altura de:

h ≤ 2.lg(n+1)



Intuição, junte os nós vermelhos no pretos
Prova por indução


Assuma que o número de nós internos é 2bh(x)-1

7

Nodo

8

Exercício


class RBNode {
RBNode left, right, parent; int key;
Object satellite; boolean ehPreto; ...
}

Como é feita a pesquisa em uma árvore preto-vermelho? 9

Pesquisa

10

Algoritmo




A pesquisa realizada em uma árvore pretovermelho é igual a realizada em uma árvore binária de pesquisa

Faça a análise do algoritmo.

Lembrar que é
O(h). Mas h=log n.
Logo é O(log n)

public RBNode TREE-SEARCH(int key) {
RBNode t = this.root; while( t != null ) { if (key < t.element) t = t.left; else if (key > t.element) t = t.right; else return t;
}