ADT – Arvore Binária de Pesquisa
ATAI
1
Árvore Binária de Pesquisa (Binary Search
Tree)
Á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.
2
Exemplo
lion
(a)
fox
rat
cat
pig
tiger
dog
(b)
cat
pig
fox
dog
tiger
lion
rat
3
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
4
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.
5
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.
lion
root
target
fox
pig
rat
curr
cat
pig
tiger
dog
6
Procura numa BST (sem 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.
lion
root
target
fox
goat
rat
curr
cat
pig
tiger
dog
7
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.
8
Remover elemento numa BST
1. Eliminar o elemento com as árvores esquerda e direita vazias
(implica remoção do nó)
6
6
2
2
8
1
o nó a eliminar
4
8
1
4
5
2. Eliminar o elemento com a árvores esquerda (ou direita) vazia
(implica remoção do nó)
6
6
2
1
2
8
o nó a eliminar
4
1
8
5
5
9
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.
10
Remover elemento numa BST (exemplos)
6
6
A
2
2
8
1
4
8
1
3
5
3
2
8
o nó a eliminar
1
6
B
5
5
3
o nó a eliminar
A
6
2
1
3
2
8
1
4
5
B
5
3
2
8
4
8
1
4
3
5
11
Remover elemento numa BST (exemplos)
o nó a eliminar
A
B
6
5
2
2
7
1
11
3
5
4
9
8
7
1
11
3
4
10
11
2
7
1
3
9
8
9
5
10
8
10
4
12
Exemplo: Inserções Sucessivas

Animação (Inserir ‘lion’, ‘fox’, ‘rat’, ‘cat’,
‘pig’, ‘dog’, ‘tiger’):
Inicio:inserir
Após
inserir ‘dog’:
‘lion’:
‘fox’:
‘rat’:
‘cat’:
‘pig’:
‘tiger’:
lion
fox
cat
rat
pig
tiger
dog
13
Exemplo: Inserções Sucessivas

Animação(Inserir ‘cat’, ‘dog’, ‘fox’, ‘lion’, ‘pig’, ‘rat’):
Inicio:inserir‘fox’:
Após
‘dog’:
‘cat’:
‘lion’:
‘pig’:
‘rat’:
cat
dog
fox
lion
pig
rat
14
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( );
public Comparable findMax( );
//Retorna o menor elemento
//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 INORDER
public void printTreePre(); //Elementos em PREORDER
public void printTreePos(); //Elementos em POSORDER
}
15
Implementação:
versão iterativa
16
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
17
Classe BST
public class BST implements BinarySearchTree {
private BSTNode root;
public BST () {
// cria uma árvore vazia
root = null;
}
…
}
18
Método de procura
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();
}
}
19
Método inserir
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();
}
}
20
Eliminar um nó da árvore
(versão menor dos maiores)
21
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();
}
22
Método privado que elimina o elemento
mais a esquerda da árvore
private 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;
}
}
23
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 filhos
this.element = (this.getRight()).getLeftmost();
this.setRight((this.getRight()).deleteLeftmost());
return this;
}
}
24
Eliminar um nó da árvore
public 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();
}
}
25
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());
}
}
26
Implementação:
versão recursiva
27
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;
}
28
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 );
}
else
t = ( t.getLeft() != null ) ? t.getLeft() : t.getRight();
return t;
}
29
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() );
}
30