Arvore Binaria de Busca (BST)

19/02/2013

1

ESTRUTURAS DE DADOS E

ALGORITMOS

ÁRVORE BINÁRIA Adalberto Cajueiro

Departamento de Sistemas e Computação

Universidade Federal de Campina Grande

1

ÁRVORE (EXEMPLO)

Como seria pesquisar a localização de um arquivo no

windows explorer se não tivéssemos diretórios?

Para entradas realmente grandes, o acesso

linear é proibitivo!

Precisamos de alguma estrutura nao-linear de

acesso mais eficiente. 2

19/02/2013

2

ÁRVORE

Estrutura não-linear com tempo de acesso em

média O(log n).

Coleção de nós em hierarquia

Vazia ou

Raiz (root) e zero ou mais subárvores

Raiz da subárvore é um nó filho do nó raiz

A raiz de uma árvore é unica!

Não possui ciclos

N nós, N-1 arestas

3

ÁRVORE (ILUSTRACAO)

raiz

...

raiz

root

4

19/02/2013

3

ÁRVORE (ILUSTRACAO)

raiz

...

folha (leaf)

5

6

ÁRVORE

raiz

...

Nível 0

Nível 1

Nível k

Nível k + 1

Altura = k+1

19/02/2013

4

ÁRVORE

Uma árvore binária é uma estrutura de

dados caracterizada por:

Ou não tem elemento algum (árvore vazia)

Ou tem um elemento distinto, denominado

raiz, com duas referencias para duas

estruturas diferentes, denominadas sub-árvore

(filho) esquerda e sub-árvore (filho) direita

Cada nó pode ter grau: 0, 1 ou 2

7

ÁRVORE

A ligação entre os nós são vistas como apontadores direcionados do pai para os filhos.

Por questoes de implementação apontadores podem existir também dos filhos para o pai

O numero de filhos por nó diferenciam os vários tipos de arvores existentes.

Cada nó da árvore encontra-se em determinado nível. A raiz encontra-se no nível zero.

Propriedade fundamental: só existe um caminho da raiz para um outro nó da árvore.

Altura de uma árvore: comprimento do caminho mais longo da raiz até as folhas

8

19/02/2013

5

ÁRVORE (APLICABILIDADE)

Representacao de expressoes aritméticas

5*3 + 4/2

+

* /

5 3 4 2

9

EXERCÍCIO

Qual a profundidade

do nó 6?

Qual a altura da

árvore?

Os nós 6 e 9 estão no

mesmo nível? e 7 e

11?

Qual o grau do nó 7?

E de 9? E de 4?

10

19/02/2013

6

ÁRVORES ESTRITAMENTE BINÁRIAS

Cada nó possui grau 0 ou 2

Quantos nós terá uma AEB com n folhas?

7

4

9 1

6

3 2

Desenhe diversas arvores

e tente deduzir.

11

EXERCÍCIO

A árvore a seguir é estritamente binária?

Justifique.

12

19/02/2013

7

ÁRVORE BINÁRIA COMPLETA

Todos os níveis são completos (folhas estão no mesmo nível) Qual a relacao que existe entre a altura de uma

árvore binária completa e o número de elementos em cada nível?

Qual a relacao que existe entre a altura de uma árvore binária completa e o número de elementos no total?

nível 0 – nos:1 – total:1




13

ÁRVORE BINÁRIA COMPLETA

Todos os níveis são completos (folhas estão no mesmo nível) Qual a relacao que existe entre a altura de uma

árvore binária completa e o número de elementos em cada nível?

Qual a relacao que existe entre a altura de uma árvore binária completa e o número de elementos no total?





h 2h 2h+1 - 1

14

19/02/2013

8

ÁRVORES BINÁRIAS (PERCURSOS)

Formas de percurso em árvore binárias:

Pré-ordem (RAIZ, ESQ, DIR) Visita raiz

Percorre sub-árvore esquerda em pré-ordem

Percorre sub-árvore direita em pré-ordem

Em-ordem (simétrica) (ESQ, RAIZ, DIR) Percorre sub-árvore esquerda em ordem simétrica

Visita raiz

Percorre sub-árvore direita em ordem simétrica

Pós-ordem (ESQ, DIR, RAIZ) Percorre sub-árvore esquerda em pós-ordem

Percorre sub-árvore direita em pós-ordem

Visita raiz

Applet: http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html

15

ARVORES BINÁRIAS

Impressão em pré-ordem (R,E,D):

8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

16

http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html

http://www.cosc.canterbury.ac.nz/mukundan/dsal/BTree.html

../material extra/BTree.html

19/02/2013

9

ARVORES BINÁRIAS

Impressão em pré-ordem:

8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8

17

ARVORES BINÁRIAS


8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8,4

18

19/02/2013

10

ARVORES BINÁRIAS


8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8,4,2

19

ARVORES BINÁRIAS


8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8,4,2,1

20

19/02/2013

11

ARVORES BINÁRIAS


8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8,4,2,1,3

21

ARVORES BINÁRIAS


8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8,4,2,1,3,6

22

19/02/2013

12

ARVORES BINÁRIAS


8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8,4,2,1,3,6,5

23

ARVORES BINÁRIAS


8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8,4,2,1,3,6,5,7

24

19/02/2013

13

ARVORES BINÁRIAS


8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8,4,2,1,3,6,5,7,

12

25

ARVORES BINÁRIAS


8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8,4,2,1,3,6,5,7,

12,10

26

19/02/2013

14

ARVORES BINÁRIAS


8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8,4,2,1,3,6,5,7,

12,10,9

27

ARVORES BINÁRIAS


8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8,4,2,1,3,6,5,7,

12,10,9,11

28

19/02/2013

15

ARVORES BINÁRIAS


8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8,4,2,1,3,6,5,7,

12,10,9,11,14

29

ARVORES BINÁRIAS


8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

8,4,2,1,3,6,5,7,

12,10,9,11,14,13

30

19/02/2013

16

EXERCÍCIO

Qual a saída do caminhamento em pré ordem da árvore binária a seguir?

31

32

ARVORES BINÁRIAS

Impressão em ordem simétrica (E,R,D):

8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

1,2,3,4,5,6,7,8,9

10,11,12,13,14,15

19/02/2013

17

EXERCÍCIO

Qual a saída do percurso em ordem da árvore binária a seguir?

33

34

ARVORES BINÁRIAS

Impressão em pós-ordem (E,D,R):

8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

1,3,2,5,7,6,4,9,11,10

13,15,14,12,8

19/02/2013

18

EXERCÍCIO

Qual a saída do caminhamento em pós ordem da árvore binária a seguir?

35

ÁRVORE BINÁRIA (IMPLEMENTAÇÃO)

De que é composta uma árvore binária?

Como implementar uma árvore binária?

36

19/02/2013

19




public class BTNode<T> {

protected T data;

protected BTNode<T> left;

protected BTNode<T> right;

protected BTNode<T> parent;

public boolean isEmpty(){

return this.data == null;

}

//getters, setters, equals, toString

}

37




public interface BT<T> {

public BTNode<T> getRoot();

public boolean isEmpty();

public int height();

public BTNode<T> search(T elem);

public void insert(T value);

public void remove(T key);

public T[] preOrder();

public T[] order();

public T[] postOrder();

public int size();

}

38

19/02/2013

20


Como representar uma árvore vazia?

O construtor default de BTNode já gera uma

árvore vazia?

data = null

null null

null

39


Como representar uma árvore vazia?

O construtor default de BTNode já gera uma

árvore vazia?

data = null

null null

null

= NIL

O nó sentilena de

uma árvore

binária não

contem dados

40

19/02/2013

21


Como representar uma árvore contendo apenas

um nó?

data

NIL NIL

null

data

null

null

null null

null

null null

folha folha

41

ÁRVORE BINÁRIA DE BUSCA

Árvore binária de busca ou árvore binária de

pesquisa é uma árvore binária onde todos os nós

armazenam dados comparáveis

todos nós da sub-árvore à esquerda contêm valores

menores do que o nó raiz

todos os nós da subárvore à direita contêm valores

maiores do que o nó raiz.

A principal utilização de árvores binárias são as

árvores binária de busca

x

< x > x

42

19/02/2013

22

EXEMPLO

2 Subárvores >

> >

<

<

O quanto isso reduz o espaço da busca a cada passo?

43


(IMPLEMENTAÇÃO)

Uma BST é uma BT?

Como implementar isso em Java?

44

19/02/2013

23


(IMPLEMENTAÇÃO)

Uma BST é uma BT?


45

public class BSTNode<T extends Comparable<T>>

extends BTNode<T> {

}


(IMPLEMENTAÇÃO)

Uma BST é uma BT?


46

public interface BST<T extends Comparable<T>>

extends BT<T> {

public BTNode<T> maximum();

public BTNode<T> minimum();

public BTNode<T> successor(BTNode<T> node);

public BTNode<T> predecessor(BTNode<T> node);

}

19/02/2013

24

PESQUISA BINÁRIA

Como saber se um dado/valor/chave está

na árvore?

Se o nó é não-vazio

Verifica se o dado do nó é igual à chave dada

Se nao for

Se a chave dada for menor que o dado do nó,

pesquisa na sub-árvore a esquerda

Senao pesquise na sub-árvore a direita

47

PESQUISA BINÁRIA (IMPLEMENTACAO)

Qual o custo dos algoritmos?

48

19/02/2013

25

ÁRVORE DESBALANCEADA

O que ocorre com a pesquisa binária se a árvore

estiver desbalanceada?

42

88

94

95

x

< x

> x

49

ÁRVORE DESBALANCEADA

O que ocorre com a pesquisa binária se a árvore

estiver desbalanceada?

42

88

94

95

O(n)

Solução: Outras árvores, como AVL, que veremos depois.

x

< x

> x

50

19/02/2013

26

MINIMUM

Como buscar o elemento mínimo de uma

BST?

Descer pela esquerda até que um NIL seja

encontrado

51

MAXIMUM

Como buscar o elemento máximo de uma

BST?

Descer pela direita até que um NIL seja

encontrado

52

19/02/2013

27

SUCESSOR

Como buscar o sucessor de um elemento

em uma BST?

Sucessor é a menor das chaves maiores (menor

descendente a direita)

53

SUCESSOR

Como buscar o sucessor de um elemento

em uma BST?

Sucessor é a menor das chaves maiores

(primeiro ascendente maior)

54

19/02/2013

28

PREDECESSOR

Como buscar o predecessor de um

elemento em uma BST?

Predecessor é a maior das chaves menores

(maior descendente a esquerda). Simétrico ao

sucessor

Tree-Predecessor(x)

if left[x] != NIL

then return Tree-Maximum(left[x])

y = p[x]

while y != NIL and x = left[y]

do x = y

y = p[y]

return y 55

PREDECESSOR

Como buscar o predecessor de um

elemento em uma BST?

Predecessor é a maior das chaves menores

(primeiro ascendente maior). Simétrico ao

sucessor

Tree-Predecessor(x)

if left[x] != NIL

then return Tree-Maximum(left[x])

y = p[x]

while y != NIL and x = left[y]

do x = y

y = p[y]

return y 56

19/02/2013

29

ÁRVORE BINÁRIA (INSERÇÃO)

Acontece pela raiz (admitir elementos diferentes)

Processar apenas chaves diferentes da raiz

Se a chave for menor, insere no filho a esquerda

Se a chave for maior insere no filho a direita

Insercao sempre acontece em uma nova folha

57

EXERCÍCIO 1

Insira as chaves 46, 47, 44, 45

58

19/02/2013

30

EXERCÍCIO 1


59

46

EXERCÍCIO 1


60

46

47

19/02/2013

31

EXERCÍCIO 1


61

46

47 44

EXERCÍCIO 1


62

46

47 44

45

19/02/2013

32

ÁRVORE BINÁRIA (INSERCAO)

O procedimento recebe um nó mas poderia receber V

x guarda o nó onde inserir

e

y guarda o pai

63



Para que serve?

64

19/02/2013

33



Se a arvore é inicialmente

vazia ou entao adiciona z

como filho correto de y

65


O que o método a seguir faz?

XYZ(BSTNode node, T element){

if(node=NIL){

node.data = element

node.left = NIL

node.right = NIL

}else{

if(element< node.data){

XYZ(node.left, element)

}else if (element > node.data){

XYZ(node.right, element)

}

}

} 66

19/02/2013

34

ARVORES BINÁRIAS (REMOCAO)

Remocoes em arvores binarias:

Se o nó y (a ser removido) for uma folha entao remova-o.

Se o nó y tem apenas um filho, então ligamos o pai de y

ao filho de y

Se tem dois filhos então traz o sucessor de y para o lugar

dele e remove o sucessor

12

10 14

9 11 13 15

12

10 15

9 11 13 67

ÁRVORE BINÁRIA (REMOÇÃO)

tem ao maximo 1 filho

68

19/02/2013

35


Tem 2 filhos

69


Guarda o filho a direita

ou a esquerda

70

19/02/2013

36


Conecta o filho ao pai de y

71


Se y é root entao x é novo root

72

19/02/2013

37


Senao seta x sendo o filho

correto do pai de y

73


Se o sucessor de z foi um

nó diferente entao copia

o conteudo dele para z.

74

19/02/2013

38


Outras abordagens trabalham da seguinte forma:

Se for folha remove

Senao sobe o menor descendente a direita (sucessor)

Se nao existir menor descendente a direita então sobe

o maior descendente a esquerda (predecessor)

Remove recursivamente o nó movido.

75


76

remover 20

19/02/2013

39


77


78

remover 30

19/02/2013

40


79

remover 30

40


80

remover 50

40

19/02/2013

41


81

remover 90

40

90


82

40

90

100

19/02/2013

42

ÁRVORE BINÁRIA (REMOCAO)

XYZ(value) {

BSTNode node = search(value)

if(node != NIL){

if(node is leaf){

node = NIL

}else if (node has one child){

if node != root

if(node is left child){

if(node.left != NIL)

node.left is left child of node.parent

else

node.right is left child of node.parent

else //node is right child

if(node.left != NIL)

node.left is right child of parent

else

node.right is right child of parent

else

root = not NIL child of root

}else{

BSTNode sucessor = sucessor(node);

node.value = sucessor.value;

XYZ(sucessor);

}

}

}

O que o metodo faz?

83

ÁRVORE BINÁRIA (PERCURSO)

Algoritmo do percurso em pre-ordem

84

8

4 12

2

1 3

6

5 7

10 14

9 11 13 15

Como seria o algoritmo?

19/02/2013

43


Algoritmo do percurso em pre-ordem

preOrder(BSTNode node){

if(node != NIL){

visit(node);

preOrder(node.left);

preOrder(node.right);

}

}

visit(BSTNode){

print(node.key);

}

Poderia fazer qualquer outro

processamento

85


Algoritmo do percurso em ordem

86

8

4 12

2

1 3

6

5 7

10 14

9 11 13 15


19/02/2013

44


Algoritmo do percurso em ordem

order(BSTNode node){

if(node != NIL){

order(node.left);

visit(node);

order(node.right);

}

}

87


Algoritmo do percurso em pós-ordem

88

8

4 12

2

1 3

6

5 7

10 14

9 11 13 15


19/02/2013

45


Algoritmo do percurso em pós-ordem

postOrder(BSTNode node){

if(node != NIL){

postOrder(node.left);

postOrder(node.right);

visit(node);

}

}

89

ÁRVORE BINÁRIA

Como seria para calcular recursivamente o

tamanho (quantidade de elementos) de uma

árvore binária

90

1

size size

size(root) = 1 + size(left) + size(right)

19/02/2013

46

ÁRVORE BINÁRIA

Como seria para calcular recursivamente o

tamanho (quantidade de elementos) de uma

árvore binária

int size(){

return size(root)

}

int size(BSTNode node){

if(node.isEmpty)

return 0

else

return 1 + size(node.left) + size(node.right)

}

91

POSCOMP 2009

Nao

necessariamente

balanceada!

92

19/02/2013

47

POSCOMP 2009

93

POSCOMP 2009

94

19/02/2013

48

POSCOMP 2009

95

REFERÊNCIAS

Capítulo 13

96

Documents

Arvore Binaria de Busca (BST)