Árvore Binária de Pesquisa

Prévia do material em texto

Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Árvore Binária de Pesquisa
Aleffer Rocha
Universidade Tecnológica Federal do Paraná, Câmpus Ponta Grossa
1 de dezembro de 2017
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Introdução
O que é uma Árvore Binária de Pesquisa?
Uma Árvore Binária de Pesquisa trata-se de uma estrutura de dados, onde cada nó da
árvore pode ser representado por um objeto composto de por:
* Elemento chave;
* Ponteiro para o nó pai;
* Ponteiro para o nó esquerdo;
* Ponteiro para o nó direito.
Onde todo nó da subárvore à esquerda de um nó x possui valor chave menor que o valor
chave de x e todo nó da subárvore à direita de um nó x possui valor chave maior ou igual
que o valor chave de x.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Introdução
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Introdução
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Introdução
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Introdução
A Árvore Binária de Pesquisa comporta um conjunto de operações dinâmicas como:
* Busca;
* Menor Valor;
* Maior Valor;
* Antecessor;
* Sucessor;
* Inserção;
* Remoção.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Introdução
As operações básicas de uma Árvore Binária de Pesquisa podem ser executadas em tempo
proporcional a altura h da árvore.
Figura: Árvore Binária de Pesquisa com altura h = 4.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Introdução
Para uma árvore binária completa com n nós, cada operação executa em tempo Θ(lgn) no
pior caso.
Figura: Árvore binária completa com 15 nós.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Introdução
Para uma árvore binária com n nós que possui um comportamento linear, cada operação
executa em tempo Θ(n) no pior caso.
Figura: Árvore binária com comportamento linear com 4 nós.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
ImprimeEmOrdem(x)
1: if x , NULL then
2: ImprimeEmOrdem(x.esquerda)
3: print x.chave
4: ImprimeEmOrdem(x.direita)
5: end if
Sequência de nós:
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
ImprimeEmOrdem(x)
1: if x , NULL then
2: ImprimeEmOrdem(x.esquerda)
3: print x.chave
4: ImprimeEmOrdem(x.direita)
5: end if
Sequência de nós:
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
ImprimeEmOrdem(x)
1: if x , NULL then
2: ImprimeEmOrdem(x.esquerda)
3: print x.chave
4: ImprimeEmOrdem(x.direita)
5: end if
Sequência de nós:
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
ImprimeEmOrdem(x)
1: if x , NULL then
2: ImprimeEmOrdem(x.esquerda)
3: print x.chave
4: ImprimeEmOrdem(x.direita)
5: end if
Sequência de nós: 11.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
ImprimeEmOrdem(x)
1: if x , NULL then
2: ImprimeEmOrdem(x.esquerda)
3: print x.chave
4: ImprimeEmOrdem(x.direita)
5: end if
Sequência de nós: 11.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
ImprimeEmOrdem(x)
1: if x , NULL then
2: ImprimeEmOrdem(x.esquerda)
3: print x.chave
4: ImprimeEmOrdem(x.direita)
5: end if
Sequência de nós: 11, 18.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
ImprimeEmOrdem(x)
1: if x , NULL then
2: ImprimeEmOrdem(x.esquerda)
3: print x.chave
4: ImprimeEmOrdem(x.direita)
5: end if
Sequência de nós: 11, 18, 22.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
ImprimeEmOrdem(x)
1: if x , NULL then
2: ImprimeEmOrdem(x.esquerda)
3: print x.chave
4: ImprimeEmOrdem(x.direita)
5: end if
Sequência de nós: 11, 18, 22.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
ImprimeEmOrdem(x)
1: if x , NULL then
2: ImprimeEmOrdem(x.esquerda)
3: print x.chave
4: ImprimeEmOrdem(x.direita)
5: end if
Sequência de nós: 11, 18, 22, 28.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
ImprimeEmOrdem(x)
1: if x , NULL then
2: ImprimeEmOrdem(x.esquerda)
3: print x.chave
4: ImprimeEmOrdem(x.direita)
5: end if
Sequência de nós: 11, 18, 22, 28.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
ImprimeEmOrdem(x)
1: if x , NULL then
2: ImprimeEmOrdem(x.esquerda)
3: print x.chave
4: ImprimeEmOrdem(x.direita)
5: end if
Sequência de nós: 11, 18, 22, 28, 52.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
Teorema
Se x é a raiz de uma subárvore com n nós, então o algoritmo ImprimeEmOrdem(x) tem
complexidade Θ(n).
Seja T(n) a complexidade do algoritmo quando ele é chamado na raiz de uma subárvore
com n nós. O algoritmo demora um tempo constante c em uma subárvore vazia, então
T(n) = c, n = 0.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
Teorema
Se x é a raiz de uma subárvore com n nós, então o algoritmo ImprimeEmOrdem(x) tem
complexidade Θ(n).
Para n > 0, suponha que o algoritmo seja
chamado em um nó x cuja subárvore
esquerda têm k nós e cuja subárvore direita
tem n − k − 1 nós.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
Teorema
Se x é a raiz de uma subárvore com n nós, então o algoritmo ImprimeEmOrdem(x) tem
complexidade Θ(n).
O tempo para execução do algoritmo é
T(n) = T(k) + T(n − k − 1) + d para alguma
constante positiva d que reflete o tempo para
executar o algoritmo, executando-se o tempo
gasto em chamadas recursivas.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Em Ordem
Teorema
Se x é a raiz de uma subárvore com n nós, então o algoritmo ImprimeEmOrdem(x) tem
complexidade de tempo de execução Θ(n).
Para n = 0, temos (c + d) ∗ 0 + c = c = T(0). Para n > 0 temos:
T(n) = T(k) + T(n − k − 1) + d
= ((c + d) ∗ k + c) + ((c + d)(n − k − 1) + c) + d
= (c + d) ∗ n + c − (c + d) + c + d
= (c + d) ∗ n + c
Portanto, o algoritmo ImprimeEmOrdem(x) tem complexidade de execução Θ(n). �
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Busca
Busca pelo valor 18, onde k = 18 e x é o endereço do nó raiz.
BuscaRecursiva(x, k)
1: if x == NULL or k == x.chave then
2: return x
3: end if
4: if k < x.chave then
5: return BuscaRecursiva(x.esquerda, k)
6: else
7: return BuscaRecursiva(x.direita, k)
8: end if
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Busca
Busca pelo valor 18, onde k = 18 e x é o endereço do nó raiz.
BuscaRecursiva(x, k)
1: if x == NULL or k == x.chave then
2: return x
3: end if
4: if k < x.chave then
5: return BuscaRecursiva(x.esquerda, k)
6: else
7: return BuscaRecursiva(x.direita, k)
8: end if
Introdução Em Ordem Busca Menor Valor MaiorValor Sucessor Antecessor Inserção Remoção Referência
Busca
Busca pelo valor 18, onde k = 18 e x é o endereço do nó raiz.
BuscaRecursiva(x, k)
1: if x == NULL or k == x.chave then
2: return x
3: end if
4: if k < x.chave then
5: return BuscaRecursiva(x.esquerda, k)
6: else
7: return BuscaRecursiva(x.direita, k)
8: end if
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Busca
Busca pelo valor 18, onde k = 18 e x é o endereço do nó raiz.
BuscaRecursiva(x, k)
1: if x == NULL or k == x.chave then
2: return x
3: end if
4: if k < x.chave then
5: return BuscaRecursiva(x.esquerda, k)
6: else
7: return BuscaRecursiva(x.direita, k)
8: end if
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Busca
Busca pelo valor 18, onde k = 18 e x é o endereço do nó raiz.
BuscaRecursiva(x, k)
1: if x == NULL or k == x.chave then
2: return x
3: end if
4: if k < x.chave then
5: return BuscaRecursiva(x.esquerda, k)
6: else
7: return BuscaRecursiva(x.direita, k)
8: end if
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Busca
Busca pelo valor 18, onde k = 18 e x é o endereço do nó raiz.
BuscaIterativa(x, k)
1: while x , NULL and k , x.chave do
2: if k < x.chave then
3: x = x.esquerda
4: else
5: x = x.direita
6: end if
7: end while
8: return x
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Busca
Busca pelo valor 18, onde k = 18 e x é o endereço do nó raiz.
BuscaIterativa(x, k)
1: while x , NULL and k , x.chave do
2: if k < x.chave then
3: x = x.esquerda
4: else
5: x = x.direita
6: end if
7: end while
8: return x
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Busca
Busca pelo valor 18, onde k = 18 e x é o endereço do nó raiz.
BuscaIterativa(x, k)
1: while x , NULL and k , x.chave do
2: if k < x.chave then
3: x = x.esquerda
4: else
5: x = x.direita
6: end if
7: end while
8: return x
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Busca
Busca pelo valor 18, onde k = 18 e x é o endereço do nó raiz.
BuscaIterativa(x, k)
1: while x , NULL and k , x.chave do
2: if k < x.chave then
3: x = x.esquerda
4: else
5: x = x.direita
6: end if
7: end while
8: return x
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Busca
Busca pelo valor 18, onde k = 18 e x é o endereço do nó raiz.
BuscaIterativa(x, k)
1: while x , NULL and k , x.chave do
2: if k < x.chave then
3: x = x.esquerda
4: else
5: x = x.direita
6: end if
7: end while
8: return x
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Menor Valor
Busca pelo Menor Valor chave na árvore onde x é o endereço do nó raiz.
MenorValor(x)
1: while x.esquerda , NULL do
2: x = x.esquerda
3: end while
4: return x
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Menor Valor
Busca pelo Menor Valor chave na árvore onde x é o endereço do nó raiz.
MenorValor(x)
1: while x.esquerda , NULL do
2: x = x.esquerda
3: end while
4: return x
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Menor Valor
Busca pelo Menor Valor chave na árvore onde x é o endereço do nó raiz.
MenorValor(x)
1: while x.esquerda , NULL do
2: x = x.esquerda
3: end while
4: return x
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Maior Valor
Busca pelo Maior Valor chave na árvore onde x é o endereço do nó raiz.
MaiorValor(x)
1: while x.direta , NULL do
2: x = x.direita
3: end while
4: return x
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Maior Valor
Busca pelo Maior Valor chave na árvore onde x é o endereço do nó raiz.
MaiorValor(x)
1: while x.direta , NULL do
2: x = x.direita
3: end while
4: return x
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Maior Valor
Busca pelo Maior Valor chave na árvore onde x é o endereço do nó raiz.
MaiorValor(x)
1: while x.direta , NULL do
2: x = x.direita
3: end while
4: return x
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Maior Valor
Busca pelo Maior Valor chave na árvore onde x é o endereço do nó raiz.
MaiorValor(x)
1: while x.direta , NULL do
2: x = x.direita
3: end while
4: return x
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Maior Valor
Busca pelo Maior Valor chave na árvore onde x é o endereço do nó raiz.
MaiorValor(x)
1: while x.direta , NULL do
2: x = x.direita
3: end while
4: return x
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Sucessor
Sucessor(x)
1: if x.direita , NULL then
2: returnMenorValor(x.direita)
3: end if
4: y = x.pai
5: while y , NULL and x == y.direita do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
x.chave = 28
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Sucessor
Sucessor(x)
1: if x.direita , NULL then
2: returnMenorValor(x.direita)
3: end if
4: y = x.pai
5: while y , NULL and x == y.direita do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
x.chave = 28
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Sucessor
Sucessor(x)
1: if x.direita , NULL then
2: returnMenorValor(x.direita)
3: end if
4: y = x.pai
5: while y , NULL and x == y.direita do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
x.chave = 28
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Sucessor
Sucessor(x)
1: if x.direita , NULL then
2: returnMenorValor(x.direita)
3: end if
4: y = x.pai
5: while y , NULL and x == y.direita do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
x.chave = 28
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Sucessor
Sucessor(x)
1: if x.direita , NULL then
2: returnMenorValor(x.direita)
3: end if
4: y = x.pai
5: while y , NULL and x == y.direita do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
x.chave = 28
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Sucessor
Sucessor(x)
1: if x.direita , NULL then
2: returnMenorValor(x.direita)
3: end if
4: y = x.pai
5: while y , NULL and x == y.direita do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
x.chave = 28
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Sucessor
Sucessor(x)
1: if x.direita , NULL then
2: returnMenorValor(x.direita)
3: end if
4: y = x.pai
5: while y , NULL and x == y.direita do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
x.chave = 48
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Sucessor
Sucessor(x)
1: if x.direita , NULL then
2: returnMenorValor(x.direita)
3: end if
4: y = x.pai
5: while y , NULL and x == y.direitado
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
x.chave = 48
y.chave = 50
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Sucessor
Sucessor(x)
1: if x.direita , NULL then
2: returnMenorValor(x.direita)
3: end if
4: y = x.pai
5: while y , NULL and x == y.direita do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
x.chave = 48
y.chave = 50
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Antecessor
Antecessor(x)
1: if x.esquerda , NULL then
2: returnMaiorValor(x.esquerda)
3: end if
4: y = x.pai
5: while y , NULL and x == y.esquerda do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Antecessor
Antecessor(x)
1: if x.esquerda , NULL then
2: returnMaiorValor(x.esquerda)
3: end if
4: y = x.pai
5: while y , NULL and x == y.esquerda do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Antecessor
Antecessor(x)
1: if x.esquerda , NULL then
2: returnMaiorValor(x.esquerda)
3: end if
4: y = x.pai
5: while y , NULL and x == y.esquerda do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Antecessor
Antecessor(x)
1: if x.esquerda , NULL then
2: returnMaiorValor(x.esquerda)
3: end if
4: y = x.pai
5: while y , NULL and x == y.esquerda do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Antecessor
Antecessor(x)
1: if x.esquerda , NULL then
2: returnMaiorValor(x.esquerda)
3: end if
4: y = x.pai
5: while y , NULL and x == y.esquerda do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Antecessor
Antecessor(x)
1: if x.esquerda , NULL then
2: returnMaiorValor(x.esquerda)
3: end if
4: y = x.pai
5: while y , NULL and x == y.esquerda do
6: x = y
7: y = y.pai
8: end while
9: return y
Para este exemplo, x é o nó cujo
x.chave = 28.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Antecessor
Teorema
Os procedimentos BuscaIterativa, BuscaRecursiva, MenorValor, MaiorValor, Sucessor e
Antecessor possuem tempo de execução como complexidade O(h) em uma Árvore Binária
de Pesquisa com altura h.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Inserção
Insercao(T, z)
1: y = NULL
2: x = T.root
3: while x , NULL do
4: y = x
5: if z.chave < x.chave then
6: x = x.esquerda
7: else
8: x = x.direita
9: end if
10: end while
11: z.p = y
12: if y == NULL then
13: T.root = z
14: else if z.chave < y.chave then
15: y.esquerda = z
16: else
17: y.direita = z
18: end if
Inserção de z, onde z.chave = 7 e T é a
árvore.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Inserção
Insercao(T, z)
1: y = NULL
2: x = T.root
3: while x , NULL do
4: y = x
5: if z.chave < x.chave then
6: x = x.esquerda
7: else
8: x = x.direita
9: end if
10: end while
11: z.p = y
12: if y == NULL then
13: T.root = z
14: else if z.chave < y.chave then
15: y.esquerda = z
16: else
17: y.direita = z
18: end if
Inserção de z, onde z.chave = 7 e T é a
árvore.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Inserção
Insercao(T, z)
1: y = NULL
2: x = T.root
3: while x , NULL do
4: y = x
5: if z.chave < x.chave then
6: x = x.esquerda
7: else
8: x = x.direita
9: end if
10: end while
11: z.p = y
12: if y == NULL then
13: T.root = z
14: else if z.chave < y.chave then
15: y.esquerda = z
16: else
17: y.direita = z
18: end if
Inserção de z, onde z.chave = 7 e T é a
árvore.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Inserção
Insercao(T, z)
1: y = NULL
2: x = T.root
3: while x , NULL do
4: y = x
5: if z.chave < x.chave then
6: x = x.esquerda
7: else
8: x = x.direita
9: end if
10: end while
11: z.p = y
12: if y == NULL then
13: T.root = z
14: else if z.chave < y.chave then
15: y.esquerda = z
16: else
17: y.direita = z
18: end if
Inserção de z, onde z.chave = 7 e T é a
árvore.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Inserção
Insercao(T, z)
1: y = NULL
2: x = T.root
3: while x , NULL do
4: y = x
5: if z.chave < x.chave then
6: x = x.esquerda
7: else
8: x = x.direita
9: end if
10: end while
11: z.p = y
12: if y == NULL then
13: T.root = z
14: else if z.chave < y.chave then
15: y.esquerda = z
16: else
17: y.direita = z
18: end if
Inserção de z, onde z.chave = 7 e T é a
árvore.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Inserção
Insercao(T, z)
1: y = NULL
2: x = T.root
3: while x , NULL do
4: y = x
5: if z.chave < x.chave then
6: x = x.esquerda
7: else
8: x = x.direita
9: end if
10: end while
11: z.p = y
12: if y == NULL then
13: T.root = z
14: else if z.chave < y.chave then
15: y.esquerda = z
16: else
17: y.direita = z
18: end if
Inserção de z, onde z.chave = 7 e T é a
árvore.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Remoção
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Remoção
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Remoção
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Remoção
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Remoção
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Remoção
Remover(T, z)
1: if z.esquerda == NULL then
2: Transplantar(T, z, z.direita)
3: else if z.direita == NULL then
4: Transplantar(T, z, z.esquerda)
5: else
6: y = MenorValor(z.direita)
7: if y.p , z then
8: Transplantar(T, y, y.direita)
9: y.direita = z.direita
10: y.direita.pai = y
11: end if
12: Transplantar(T, z, t)
13: y.esquerda = z.direita
14: y.esquerda.pai = y
15: end if
Removendo o nó z, onde z.chave = 42.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Remoção
Remover(T, z)
1: if z.esquerda == NULL then
2: Transplantar(T, z, z.direita)
3: else if z.direita == NULL then
4: Transplantar(T, z, z.esquerda)
5: else
6: y = MenorValor(z.direita)
7: if y.p , z then
8: Transplantar(T, y, y.direita)
9: y.direita = z.direita
10: y.direita.pai = y
11: end if
12: Transplantar(T, z, t)
13: y.esquerda = z.direita
14: y.esquerda.pai = y
15: end if
Removendo o nó z, onde z.chave = 42.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Remoção
Remover(T, z)
1: if z.esquerda == NULL then
2: Transplantar(T, z, z.direita)
3: else if z.direita == NULL then
4: Transplantar(T, z, z.esquerda)
5: else
6: y = MenorValor(z.direita)
7: ify.p , z then
8: Transplantar(T, y, y.direita)
9: y.direita = z.direita
10: y.direita.pai = y
11: end if
12: Transplantar(T, z, t)
13: y.esquerda = z.direita
14: y.esquerda.pai = y
15: end if
Removendo o nó z, onde z.chave = 42.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Remoção
Transplantar(T, u, v)
1: if u.pai == NULL then
2: T.root = v
3: else if u == u.pai.esquerda then
4: u.pai.esquerda = v
5: else
6: u.pai.direita = v
7: end if
8: if v , NULL then
9: v.pai = u.pai
10: end if
Removendo o nó z, onde z.chave = 42.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Remoção
Transplantar(T, u, v)
1: if u.pai == NULL then
2: T.root = v
3: else if u == u.pai.esquerda then
4: u.pai.esquerda = v
5: else
6: u.pai.direita = v
7: end if
8: if v , NULL then
9: v.pai = u.pai
10: end if
Removendo o nó z, onde z.chave = 42.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Remoção
Remover(T, z)
1: if z.esquerda == NULL then
2: Transplantar(T, z, z.direita)
3: else if z.direita == NULL then
4: Transplantar(T, z, z.esquerda)
5: else
6: y = MenorValor(z.direita)
7: if y.p , z then
8: Transplantar(T, y, y.direita)
9: y.direita = z.direita
10: y.direita.pai = y
11: end if
12: Transplantar(T, z, t)
13: y.esquerda = z.direita
14: y.esquerda.pai = y
15: end if
Removendo o nó z, onde z.chave = 42.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Remoção
Teorema
As operações de Insercao e Remover possuem implementações que podem ser executadas
com complexidade de tempo O(h) em uma Árvore Binária de Pesquisa com altura h.
Introdução Em Ordem Busca Menor Valor Maior Valor Sucessor Antecessor Inserção Remoção Referência
Referência
* Livro: Introduction to Algorithms, 3ª edição.
* Autores: Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest e Clifford Stein;
* Páginas: 286 a 298.
	Introdução
	
	Em Ordem
	
	Busca
	
	Menor Valor
	
	Maior Valor
	
	Sucessor
	
	Antecessor
	
	Inserção
	
	Remoção
	
	Referência