ADT – Arvore Binária de Pesquisa

1

ADT – Arvore Binária de Pesquisa

ATAI

2

Árvore binária de pesquisa (BST) é uma árvore binária especial (ordenada). A localização do nó é determinada pela chave (identificador único) do elemento.

Uma árvore binária de pesquisa é uma árvore binária com as seguintes propriedades:

a chave de qualquer nó é maior que todas as chaves da subárvore esquerda;

a chave de qualquer nó é menor (ou igual) que todas as chaves da subárvore direita.

Se a chave é uma cadeia de caracteres, então a cadeia de caracteres da esquerda deve ser lexicalmente menor que a cadeia de caracteres da direita.

Árvore Binária de Pesquisa (Binary Search Tree)

3

Exemplo

(a)

dog

cat

fox

lion

pig

rat

tiger

(b)

pig

cat

dog

fox

lion rat

tiger

4

Definição Recursiva

Uma BST é:

vazia, ou Não vazia, neste caso possui:

Uma raiz que possui um elemento elem

Um ligação à sub-árvores esquerda na qual (se não for vazia) todos os elementos são menores do que elem

Um ligação à sub-árvores direita na qual (se não for vazia) todos os elementos são maiores do que elem

5

Procura numa BST

1. Por curr para a raiz da BST.2. Repetir:

2.1. se curr é null:2.1.1. Terminar com resposta não.

2.2. senão, se target é igual ao elemento na posição curr:

2.2.1. Terminar com resposta curr.2.3. se não, se target é menor do que elemento curr:

2.3.1. curr passa a ser o seu filho esquerdo.2.4. se não , se target é maior do que elemento curr:

2.4.1. curr passa a ser o seu filho direito.

6

Procura numa BST (com sucesso)

To find which if any node of a BST contains an element equal to target:1. Set curr to the BST’s root.2. Repeat:

2.1. If curr is null, terminate with answer none.2.2. Otherwise, if target is equal to curr’s element, terminate with answer curr.2.3. Otherwise, if target is less than curr’s element, set curr to curr’s left child.2.4. Otherwise, if target is greater than curr’s element, set curr to curr’s right

child.

root

dog

cat

fox

lion

pig

rat

tiger

pigtarget

To find which if any node of a BST contains an element equal to target:1. Set curr to the BST’s root.2. Repeat:

2.1. If curr is null, terminate with answer none.2.2. Otherwise, if target is equal to curr’s element, terminate with answer curr.2.3. Otherwise, if target is less than curr’s element, set curr to curr’s left child.2.4. Otherwise, if target is greater than curr’s element, set curr to curr’s right

child.

root

dog

cat

fox

lion

pig

rat

tigercurr

pigtarget

To find which if any node of a BST contains an element equal to target:1. Set curr to the BST’s root.2. Repeat:

2.1. If curr is null, terminate with answer none.2.2. Otherwise, if target is equal to curr’s element, terminate with answer curr.2.3. Otherwise, if target is less than curr’s element, set curr to curr’s left child.2.4. Otherwise, if target is greater than curr’s element, set curr to curr’s right

child.

root

dog

cat

fox

lion

pig

rat

tigercurr

pigtarget

To find which if any node of a BST contains an element equal to target:1. Set curr to the BST’s root.2. Repeat:

2.1. If curr is null, terminate with answer none.2.2. Otherwise, if target is equal to curr’s element, terminate with answer curr.2.3. Otherwise, if target is less than curr’s element, set curr to curr’s left child.2.4. Otherwise, if target is greater than curr’s element, set curr to curr’s right

child.

root

dog

cat

fox

lion

pig

rat

tigercurr

pigtarget

To find which if any node of a BST contains an element equal to target:1. Set curr to the BST’s root.2. Repeat:

2.1. If curr is null, terminate with answer none.2.2. Otherwise, if target is equal to curr’s element, terminate with answer curr.2.3. Otherwise, if target is less than curr’s element, set curr to curr’s left child.2.4. Otherwise, if target is greater than curr’s element, set curr to curr’s right

child.

root

dog

cat

fox

lion

pig

rat

tigercurr

pigtarget

7

To find which if any node of a BST contains an element equal to target:1. Set curr to the BST’s root.2. Repeat:

2.1. If curr is null, terminate with answer none.2.2. Otherwise, if target is equal to curr’s element, terminate with answer curr.2.3. Otherwise, if target is less than curr’s element, set curr to curr’s left child.2.4. Otherwise, if target is greater than curr’s element, set curr to curr’s right

child.

root

dog

cat

fox

lion

pig

rat

tiger

goattarget

To find which if any node of a BST contains an element equal to target:1. Set curr to the BST’s root.2. Repeat:

2.1. If curr is null, terminate with answer none.2.2. Otherwise, if target is equal to curr’s element, terminate with answer curr.2.3. Otherwise, if target is less than curr’s element, set curr to curr’s left child.2.4. Otherwise, if target is greater than curr’s element, set curr to curr’s right

child.

root

dog

cat

fox

lion

pig

rat

tigercurr

goattarget

To find which if any node of a BST contains an element equal to target:1. Set curr to the BST’s root.2. Repeat:

2.1. If curr is null, terminate with answer none.2.2. Otherwise, if target is equal to curr’s element, terminate with answer curr.2.3. Otherwise, if target is less than curr’s element, set curr to curr’s left child.2.4. Otherwise, if target is greater than curr’s element, set curr to curr’s right

child.

root

dog

cat

fox

lion

pig

rat

tigercurr

goattarget

To find which if any node of a BST contains an element equal to target:1. Set curr to the BST’s root.2. Repeat:

2.1. If curr is null, terminate with answer none.2.2. Otherwise, if target is equal to curr’s element, terminate with answer curr.2.3. Otherwise, if target is less than curr’s element, set curr to curr’s left child.2.4. Otherwise, if target is greater than curr’s element, set curr to curr’s right

child.

root

dog

cat

fox

lion

pig

rat

tigercurr

goattarget

To find which if any node of a BST contains an element equal to target:1. Set curr to the BST’s root.2. Repeat:

2.1. If curr is null, terminate with answer none.2.2. Otherwise, if target is equal to curr’s element, terminate with answer curr.2.3. Otherwise, if target is less than curr’s element, set curr to curr’s left child.2.4. Otherwise, if target is greater than curr’s element, set curr to curr’s right

child.

root

dog

cat

fox

lion

pig

rat

tigercurr

goattarget

Procura numa BST (sem sucesso)

8

Inserir elemento numa BST

Ideia: Para iserir um novo elemento numa BST,

processa como no método de procura. Se o elemento não estiver já presente, o método de procura vai terminar numa ligação nula. Substitua esta ligação nula por uma ligação para um nó (do tipo folha) que possui o elemento.

9

Remover elemento numa BST

1. Eliminar o elemento com as árvores esquerda e direita vazias (implica remoção do nó)

5

4

8

6

2

1 4

8

6

2

1o nó a eliminar

2. Eliminar o elemento com a árvores esquerda (ou direita) vazia (implica remoção do nó)

5

4

8

6

2

1 5

8

6

2

1o nó a eliminar

10

Remover elemento numa BST (cont.)

3. Eliminar o elemento com as árvores esquerda e direita não vazias

Soluções:

Substituir o valor do nó a eliminar com o valor do nó mais a direita na árvore esquerda do nó a eliminar (i.e. maior valor da árvore esquerda)Apagar o nó mais a direita.

Substituir o valor do nó a eliminar com o valor do nó mais a esquerda na árvore direita do nó a eliminar (i.e. menor valor da árvore direita)Apagar o nó mais a esquerda.

11

Remover elemento numa BST (exemplos)

3 5

4

8

6

2

1o nó a eliminar

3

8

6

2

1

5

A

5

8

6

2

1

3

B

3 5

4

8

6

2

1

o nó a eliminar

4

3

8

2

1

5

A

4

8

5

2

1

3

B

12

Remover elemento numa BST (exemplos)

A B

4

5

3

7

6

2

1

o nó a eliminar

11

9

8 10

4

3

7

5

2

1 11

9

8 10 4

5

3

7

2

1

11

9

8 10

13

Inicio:

Exemplo: Inserções Sucessivas

Animação (Inserir ‘lion’, ‘fox’, ‘rat’, ‘cat’, ‘pig’, ‘dog’, ‘tiger’):

Após inserir ‘lion’:

lion

Após inserir ‘fox’:

fox

lion

Após inserir ‘rat’:

fox

lion

rat

Após inserir ‘cat’:

cat

fox

lion

rat

Após inserir ‘pig’:

cat

fox

lion

pig

rat

Após inserir ‘dog’:

dog

cat

fox

lion

pig

rat

Após inserir ‘tiger’:

dog

cat

fox

lion

pig

rat

tiger

14

Exemplo: Inserções Sucessivas

Animação(Inserir ‘cat’, ‘dog’, ‘fox’, ‘lion’, ‘pig’, ‘rat’):

Inicio:Após inserir ‘cat’:

cat

Após inserir‘dog’:

dog

cat

Após inserir‘fox’:

dog

cat

fox

Após inserir ‘lion’:

dog

cat

fox

lion

Após inserir ‘pig’:

dog

cat

fox

lion

pig

Após inserir ‘rat’:

dog

cat

fox

lion

pig

rat

15

Interface da àrvore Binária de Pesquisa (BinarySearchTree - BST)public interface BinarySearchTree {public void insert(Comparable x ); //Insere o Elemento x

public void remove(Comparable x ); //Remove o Elemento x

public Comparable findMin( ); //Retorna o menor elementopublic Comparable findMax( ); //Retorna o maior elemento

public Position findKey(Comparable key ); //Retorna a posição do //elemento com a chave key

public boolean isEmpty( ); //Retorna TRUE se está vazia

public void printTreeIn(); //Imprime os Elementos em INORDERpublic void printTreePre(); //Elementos em PREORDERpublic void printTreePos(); //Elementos em POSORDER}

16

Implementação:versão iterativa

17

Classe nó do BST

public class BSTNode implements Position{

protected Comparable element;protected BSTNode left, right;protected BSTNode (Comparable elem) {

element = elem;left = null; right = null;

}public Comparable element() {return element;}public void setElement (Comparable elem){element = elem;}

….}

BSTNode metodos gets e sets

18

public class BST implements BinarySearchTree {

private BSTNode root;

public BST () {// cria uma árvore vazia

root = null;}

…

}

Classe BST

19

public Position findKey (Comparable target) {int direction = 0;BSTNode curr = root;for (;;) {

if (curr == null) return null;direction =

target.compareTo(curr.element());if (direction == 0) return curr;else if (direction < 0) curr =

curr.getLeft();else curr = curr.getRight();

}}

Método de procura

20

public void insert (Comparable elem) {int direction = 0;BSTNode parent = null, curr = root;for (;;) {

if (curr == null) {BSTNode ins = new BSTNode(elem);if (root == null) root = ins;else if (direction < 0)

parent.setLeft(ins);else parent.setRight(ins);return;

} direction = elem.compareTo(curr.element());

if (direction == 0) return;parent = curr;if (direction < 0) curr = curr.getLeft();else curr = curr.getRight();

}}

Método inserir

21

Eliminar um nó da árvore(versão menor dos maiores)

22

Método privado que retorna o elemento mais a esquerda da árvore

private Comparable getLeftmost () {BSTNode curr = this;while (curr.getLeft() != null)

curr = curr.getLeft();return curr.element();

}

23

Método privado que elimina o elemento mais a esquerda da árvoreprivate BSTNode deleteLeftmost () {

if (this.left == null)return this.right;

else {BSTNode parent = this,

curr = this.getLeft();while (curr.getLeft() != null) {

parent = curr; curr = curr.getLeft();

}parent.setLeft(curr.getRight());return this;

}}

24

Eliminar um nó do topo da árvore

public BSTNode deleteTopmost () {if (this.left == null)

return this.getRight();//não tem sub-árvore esquerda

else if (this.right == null)return this.getLeft ();//não tem sub-árvore

direita

else { // nó tem dois filhosthis.element = (this.getRight()).getLeftmost();

this.setRight((this.getRight()).deleteLeftmost());return this;

}}

25

Eliminar um nó da árvorepublic void remove (Comparable elem) {

int direction = 0;BSTNode parent = null, curr = root;for (;;) {

if (curr == null) return;direction = elem.compareTo(curr.element());if (direction == 0) {

BSTNode del = curr.deleteTopmost();//eliminar o curr

if (curr == root) root = del;else if (curr == parent.getLeft())

parent.setLeft(del);else parent.setRight(del);return;

}parent = curr;if (direction < 0)

curr = parent.getLeft();else // direction > 0

curr = parent.getRight();}

}

26

Imprimir os elementos da árvore (in-order)

public static void printInOrder (BSTNode top) {// imprima em forma crescente

// todos os elementos da árvore top

if (top != null) {printInOrder(top.getLeft());System.out.println(top.element());printInOrder(top.getRight());

}}

27

Implementação:versão recursiva

28

Operação insert // Inserir elemento x na Árvore;// Se o elemento existir não se insere public void insert( Comparable x ) { root = insert( x, root ); } /*

* Retorna o novo Nó */ private BinaryNode insert( Comparable x, BinaryNode t ) { if( t == null ) t = new BSTNode( x, null, null ); else if( x.compareTo( t.element() ) < 0 ) t.setLeft (insert( x, t.getLeft() )); else if( x.compareTo( t.element() ) > 0 ) t.setRight (insert( x, t.getRight() )); else ;// Se houver duplicação não inserir o elemento return t; }

29

Operação remove private BSTNode remove( Comparable x, BSTNode t ){ if( t == null ) return t; if( x.compareTo( t.element ) < 0 ) t.setLeft( remove( x, t.getLeft() ); else if( x.compareTo( t.element ) > 0 ) t.setRight( remove( x, t.getRight() ); else if( t.getLeft() != null &&

t.getRight() != null ) { t.setElement(findMin( t.getRight ()).element); t.setRight (remove( t.element, t.right ); } elset = ( t.getLeft() != null ) ? t.getLeft() : t.getRight(); return t;}

30

Operação que retorna o menor elemento da árvore public Comparable findMin( ) { return element( findMin( root ) ); }

private BSTNode findMin (BSTNode t ) { if( t == null ) return null; else if( t.getLeft() == null ) return t; return findMin( t.getLeft() ); }