Árvore rubro negra
4598 palavras
19 páginas
´ ´ ´ Arvores Binarias Balanceadas (Arvores Rubro-Negras)Breno Piva Ribeiro – IC/UNICAMP
11 de setembro de 2007
Breno Piva Ribeiro – IC/UNICAMP
´ ´ ´ Arvores Binarias Balanceadas (Arvores Rubro-Negras)
´ Sumario
Breno Piva Ribeiro – IC/UNICAMP
´ ´ ´ Arvores Binarias Balanceadas (Arvores Rubro-Negras)
´ ´ Arvores Binarias de Busca
´ ´ Arvores Binarias que possuem a seguinte propriedade: ´ ´ ´ ˜ Se y e um no da subarvore esquerda de x, entao Chave[y] ≤ Chave[x]. ´ ´ ´ ˜ Se y e um no da subarvore direita de x, entao Chave[x] ≤ Chave[y].
Breno Piva Ribeiro – IC/UNICAMP
´ ´ ´ Arvores Binarias Balanceadas (Arvores Rubro-Negras)
´ ´ Arvores Binarias de Busca
5
3
7
2
5
8
Breno Piva Ribeiro – IC/UNICAMP
´ ´ ´ Arvores Binarias Balanceadas (Arvores Rubro-Negras)
´ ´ Arvores Binarias de Busca
2
3
7
5
8
5
Breno Piva Ribeiro – IC/UNICAMP
´ ´ ´ Arvores Binarias Balanceadas (Arvores Rubro-Negras)
´ ´ Arvores Binarias de Busca
´ ´ Operacoes sobre Arvores Binarias de Busca: ¸˜ ´ Busca, M´nimo, Maximo, Predecessor, Sucessor, Inserir, ı Remover
Breno Piva Ribeiro – IC/UNICAMP
´ ´ ´ Arvores Binarias Balanceadas (Arvores Rubro-Negras)
Inserir
6 5
3
7
2
5
8
Breno Piva Ribeiro – IC/UNICAMP
´ ´ ´ Arvores Binarias Balanceadas (Arvores Rubro-Negras)
Inserir
6 5
3
7
2
5
8
Breno Piva Ribeiro – IC/UNICAMP
´ ´ ´ Arvores Binarias Balanceadas (Arvores Rubro-Negras)
Inserir
6 5
3
7
2
5
8
Breno Piva Ribeiro – IC/UNICAMP
´ ´ ´ Arvores Binarias Balanceadas (Arvores Rubro-Negras)
Inserir
5
3
7
2
5
6
8
Breno Piva Ribeiro – IC/UNICAMP
´ ´ ´ Arvores Binarias Balanceadas (Arvores Rubro-Negras)
Remover
´ Remover um elemento e ligeiramente mais complicado, ˆ pois existem tres casos a considerar:
Breno Piva Ribeiro – IC/UNICAMP
´ ´ ´ Arvores Binarias Balanceadas (Arvores Rubro-Negras)