Red Black Tree
Árvore Preto-Vermelho
Rudolf Bayer: "Symmetric BinaryTrees: Data Structures and
Maintenance Algorithms." Acta
Informat. 1, 290-306, 1972.
Rohit Gheyi rohit@dsc.ufcg.edu.br 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;
}