Árvores B
Implementação pelos FrameWork
Bruno Preiss
Árvores B
FrameWork Java de Bruno Preiss
Framework de Árvores e Busca
3
Interface Comparable
//pgm05_01.txt
public interface Comparable
{
boolean isLT (Comparable object);
boolean isLE (Comparable object);
boolean isGT (Comparable object);
boolean isGE (Comparable object);
boolean isEQ (Comparable object);
boolean isNE (Comparable object);
int compare (Comparable object);
}
4
Declaração da classe AbstractObject
//
pgm05_02.txt
public abstract class AbstractObject
implements Comparable
{
public final boolean isLT (Comparable object)
{ return compare (object) < 0; }
public final boolean isLE (Comparable object)
{ return compare (object) <= 0; }
public final boolean isGT (Comparable object)
{ return compare (object) > 0; }
public final boolean isGE (Comparable object)
{ return compare (object) >= 0; }
public final boolean isEQ (Comparable object)
{ return compare (object) == 0; }
public final boolean isNE (Comparable object)
{ return compare (object) != 0; }
public final boolean equals (Object object)
{
if (object instanceof Comparable)
return isEQ ((Comparable) object);
else
return false;
}
5
Métodos compareTo e compare
da classe AbstractObject
//pgm05_03.txt
//
public abstract class AbstractObject
implements Comparable
{
protected abstract int compareTo (Comparable arg);
public final int compare (Comparable arg)
{
if (getClass () == arg.getClass ())
return compareTo (arg);
else
return getClass ().getName ().compareTo (
arg.getClass ().getName ());
}
// ...
}
6
Interface Container
public interface Container
extends Comparable
{
int getCount ();
boolean isEmpty ();
boolean isFull ();
void purge ();
void accept (Visitor visitor);
Enumeration getEnumeration ();
}
7
Interface SearchableContainer
public interface SearchableContainer
extends Container
{
boolean isMember (Comparable object);
void insert (Comparable object);
void withdraw (Comparable obj);
Comparable find (Comparable object);
}
8
Interface Tree
//pgm09_01.txt
public interface Tree
extends Container
{
Object getKey ();
Tree getSubtree (int i);
boolean isEmpty ();
boolean isLeaf ();
int getDegree ();
int getHeight ();
void depthFirstTraversal (PrePostVisitor visitor);
void breadthFirstTraversal (Visitor visitor);
}
9
Interface SearchTree
//pgm10_01.txt
public interface SearchTree
extends Tree,
SearchableContainer
{
Comparable findMin ();
Comparable findMax ();
}
10
Classe Abstrata AbstractContainer
public abstract class AbstractContainer
extends AbstractObject
implements Container
{
protected int count;
public int getCount ()
{ return count; }
public boolean isEmpty ()
{ return getCount () == 0; }
public boolean isFull ()
{ return false; }
// ...
}
11
Classe Abstrata AbstractTree
//
pgm09_02.txt
public abstract class AbstractTree
extends AbstractContainer
implements Tree
{
public void depthFirstTraversal (PrePostVisitor
visitor)
{
if (visitor.isDone ())
return;
if (!isEmpty ())
{
visitor.preVisit (getKey ());
for (int i = 0; i < getDegree (); ++i)
getSubtree (i).depthFirstTraversal (visitor);
visitor.postVisit (getKey ());
}
}
// ...
}
12
Árvores MWay
13
Classe MwayTree: Métodos construtor e getM
//pgm10_14.txt
public class MWayTree
extends AbstractTree
implements SearchTree
{
protected Comparable key[];
protected MWayTree subtree[];
public MWayTree (int m)
{
if (m < 2)
throw new IllegalArgumentException("invalid degree");
key = new Comparable [m];
subtree = new MWayTree [m];
}
int getM ()
{ return subtree.length; }
// ...
}
14
Método find
Recebe um objeto e localiza o item na
árvore de busca que coincide com o objeto
buscado
Caso o objeto buscado não exista retorna
null
15
Método find da Classe MWayTree
//pgm10_16.txt
public class MWayTree
extends AbstractTree
implements SearchTree
{
protected Comparable key[];
protected MWayTree subtree[];
public Comparable find (Comparable object)
{
if (isEmpty ())
return null;
int i;
for (i = count; i > 0; --i)
{
int diff = object.compare (key [i]);
if (diff == 0)
return key [i];
if (diff > 0)
break;
}
return subtree [i].find (object);
}
}
16
Método findIndex
Recebe um objeto x e retorna i que é o
maior valor tal que x ≥ ki, sendo ki a chave
de ordem i no nó
17
Método findIndex da Classe MWayTree
//pgm10_17.txt
public class MWayTree
extends AbstractTree
implements SearchTree
{
protected Comparable key[];
protected MWayTree subtree[];
protected int findIndex (Comparable object)
{
if (isEmpty () || object.isLT (key [1]))
return 0;
int left = 1;
int right = count;
while (left < right)
{
int middle = (left + right + 1) / 2;
if (object.isLT (key [middle]))
right = middle - 1;
else
left = middle;
}
return left;
}
18
Classe BTree
//
pgm10_20.txt
public class BTree
extends MWayTree
{
protected BTree parent;
public BTree (int m)
{ super (m); }
public void attachSubtree (int i, MWayTree arg)
{
BTree btree = (BTree) arg;
subtree [i] = btree;
btree.parent = this;
}
// ...
}
19
Método insert da Classe BTree
Insere uma chave em uma página de árvore B
Se a página está vazia então:


Se a página não tem ancestral a chave será key[1] e a
página passará a ter duas filhas vazias
Caso contrário inserir no ancestral o par (chave, árvore B
vazia) pelo método insertPair
Se a página não estiver vazia:



Faz-se a busca do local apropriado calculando index pelo
método findIndex
Se o objeto for encontrado é lançada a exceção de chave
duplicada
O método chama a si mesmo recursivamente da forma
subtree [index].insert (object)
20
Método insert da Classe BTree
//
pgm10_21.txt
public void insert (Comparable object)
{
if (isEmpty ())
{
if (parent == null)
{
attachSubtree (0, new BTree (getM ()));
key [1] = object;
attachSubtree (1, new BTree (getM ()));
count = 1;
}
else
parent.insertPair (object, new BTree (getM ()));
}
else
{
int index = findIndex (object);
if (index != 0 && object.isEQ (key [index]))
throw new IllegalArgumentException (
"duplicate key");
subtree [index].insert (object);
}
}
21
Método insertPair da Clase BTree (1)
Inclui em um nó de árvore B um par (object, child)
Inicia buscando a posição correta na página com findIndex
Caso a página não esteja cheia:


O método insertKey é chamado para inserir a chave (object) na posição
correta do array de chaves
O método insertSubtree é chamado para inserir a árvore (child) na
correta posição do array de sub árvores
Caso a página esteja cheia:


O método insertKey retorna a chave que transborda do array de chaves
(maior valor) e que é atribuída a extraKey
O método insertSubtree retorna a sub árvore que sobra à direita do
array de sub árvores e que é atribuída a extraTree
22
Método insertPair da Clase BTree (2)
A página transbordou e é preciso balancear a árvore
Se o nó for a raiz:







Criam-se dois nós left e right
Left recebe as primeiras
chaves e primeiras
sub árvores pelo método attachLeftHalfOf
Right recebe as últimas
chaves a as últimas
sub árvores pelo método attachRightHalfOf
O par (extraKey,extraTree) é incluído no nó right
Left será a sub árvore 0 ligada à raiz por AttachSubtree
Right será a sub árvore 1 ligada à raiz por AttachSubtree
A chave que sobrou,
, é inserida na raiz modificada que terá
por folhas as página left e right
23
Método insertPair da Clase BTree (3)
Se o nó não for a raiz:






Cria-se um novo nó e right
Right recebe as últimas
chaves a as últimas
sub árvores pelo método attachRightHalfOf
O par (extraKey,extraTree) é incluído no nó right
As primeiras chaves e primeiras sub árvores permanecem no
nó corrente
A chave que sobrou é
O método chama a si mesmo, recursivamente, para inserir no
ancestral o par (chave que sobrou, right)
24
Método insertPair da Clase Btree (1)
protected void insertPair (Comparable object, BTree child)
{
int index = findIndex (object);
if (!isFull ())
{
insertKey (index + 1, object);
insertSubtree (index + 1, child);
++count;
}
else
{
Comparable extraKey = insertKey (index + 1, object);
BTree extraTree = insertSubtree (index + 1, child);
if (parent == null)
{
BTree left = new BTree (getM ());
BTree right = new BTree (getM ());
left.attachLeftHalfOf (this);
right.attachRightHalfOf (this);
right.insertPair (extraKey, extraTree);
attachSubtree (0, left);
key [1] = key [(getM () + 1)/2];
attachSubtree (1, right);
count = 1;
25
Método insertPair da Clase Btree (2)
else
{
count = (getM () + 1)/2 - 1;
BTree right = new BTree (getM ());
right.attachRightHalfOf (this);
right.insertPair (extraKey, extraTree);
parent.insertPair (key [(getM () + 1)/2], right);
}
}
}
26
Método attachSubtree
Recebe um inteiro i e uma árvore B
A árvore B recebida torna-se a sub árvore
de ordem i do nó corrente
27
Método attachSubtree
public void attachSubtree
(int i, MWayTree arg)
{
BTree btree = (BTree) arg;
subtree [i] = btree;
btree.parent = this;
}
28
Metodo attachLeftHalfOf
protected void attachLeftHalfOf (BTree tree) throws
IllegalArgumentException
{
attachSubtree (0, tree.subtree [0]);
count = 0;
for (int ind = 1;
ind < Math.ceil (((float) tree.getM ()) / 2);
++ind)
{
this.insertPair (tree.key [ind],
(BTree) tree.subtree [ind]);
}
}
29
Metodo attachRightHalfOf
protected void attachRightHalfOf (BTree tree) throws
IllegalArgumentException
{
attachSubtree (0, tree.subtree [(getM () + 1) / 2]);
count = 0;
for (int ind = getM () - 1;
ind > Math.ceil ((tree.getM () + 1) / 2);
--ind)
{
this.insertPair (tree.key [ind],
(BTree) tree.subtree [ind]);
}
}
30
Método insertSubtree
Recebe um inteiro índice e uma sub árvore e deve
inserir na correta posição do array de sub árvores
Caso a página não esteja cheia:
 A inserção é feita usando AttachSubtree e o
método retorna null
 As sub árvores “acima” do índice são
rearrumadas
Caso a página esteja cheia:

O método insertSubtree retorna a sub árvore que sobra
à direita do array de sub árvores e que é atribuída a
extraTree
31
Método insertSubtree (1)
private BTree insertSubtree (int index, BTree child)
{
BTree extraTree = null;
if (isFull ())
{
if (index == getM ())
extraTree = child;
else
{
extraTree = (BTree) subtree [count];
for (int i = count - 1; i >= index; --i)
{
subtree [i + 1] = subtree [i];
}
attachSubtree (index, child);
}
}
32
Método insertSubtree (2)
else
{
child.parent = this;
for (int i = count; i >= index; --i)
{
subtree [i + 1] = subtree [i];
}
subtree [index] = child;
}
return extraTree;
}
33
Método insertKey
Recebe um inteiro índice e um objeto e deve
inserir na correta posição do array de chaves
Caso a página não esteja cheia:


A inserção é feita e o método retorna null
As chaves “acima” do índice são rearrumadas
Caso a página esteja cheia:

O método insertKey retorna a chave que transborda do
array (maior valor) e que é atribuída a extraKey
34
Método insertKey (1)
private Comparable insertKey (int index, Comparable
object)
{
Comparable extraKey = null;
if (isFull ())
{
if (index == getM ())
extraKey = object;
else
{
extraKey = key [count];
for (int i = count - 1; i >= index; --i)
{
key [i + 1] = key [i];
}
key [index] = object;
}
}
35
Método insertKey (2)
else
{
for (int i = count; i >= index; --i)
{
key [i + 1] = key [i];
} // for (int i = count; i > index; --i) {
key [index] = object;
}
return extraKey;
}
36
Método withdraw (1)
Remove um objeto da árvore
Se a árvore estiver vazia lança uma exceção
Determina a posição do objeto no nó pelo método
findIndex
Caso tenha encontrado o objeto a excluir em uma
página não folha procura seu antecessor ou
sucessor para gravar sobre o objeto a ser excluído
e trata de excluir o antecessor ou sucessor
37
Método withdraw (2)
Caso tenha encontrado o objeto a excluir em
folha:
Decrementa o contador de população
 Leva para a esquerda do array de objetos todos os
superiores ao index do objeto a excluir
 Leva para a esquerda do array de sub árvores todas
as sub árvores correspondentes
 Anula o objeto e a sub árvore a excluir

38
Método withdraw (3)
Caso não tenha encontrado o objeto a excluir por
estar entre dois objetos do nó chama a si mesmo
da forma
subtree[index].withdraw(object)
Se o contador tornar-se menor do que o mínimo:


Se a nó corrente tiver ancestral chama o método
balance
Se for raiz e tiver ficado vazia chama o método
TrimmRoot
39
Método withdraw (1)
public void withdraw (Comparable object) throws
IllegalArgumentException,
InvalidOperationException
{
if (isEmpty ())
throw new IllegalArgumentException ("object not found");
int index = findIndex (object);
if (index != 0 && object.isEQ (key [index]))
{
if (!subtree [index - 1].isEmpty ())
{
Comparable max =
subtree [index - 1].findMax ();
key [index] = max;
subtree [index - 1].withdraw (max);
}
else if (!subtree [index].isEmpty ())
{
Comparable min =
subtree [index].findMin ();
key [index] = min;
subtree [index].withdraw (min);
}
40
Método withdraw (2)
else
{
--count;
int i;
for (i = index; i <= count; ++i)
{
key [i] = key [i + 1];
subtree [i] = subtree [i + 1];
}
key [i] = null;
subtree [i] = null;
}
}
else
subtree [index].withdraw (object);
if (count < getMin ())
if (parent != null)
balance ();
else if (count == 0)
rootTrim ();
}
41
Métodos getMin e isFull
public int getMin ()
{
return ((getM () + 1) / 2) - 1;
}
public boolean isFull ()
{
return getM () - 1 == count;
}
42
Método balance
Equilibra uma página sub povoada
Determina a posição no pai
Obtém a população das irmãs esquerda e direita
Caso a população da esquerda seja maior do que o mínimo
executa uma rotação à esquerda
Senão se a população da direita for maior do que o mínimo
executa uma rotação à direita
Caso contrário todas as páginas envolvidas estão com
população mínima e então:


concatena com a esquerda
(parent.concatenation(parentIndex)) ou
concatena com a direita
(parent.concatenation(parentIndex + 1))
Existe um teste de lado pois existe o tratamento diferenciado
das páginas extremas que possuem irmãs fictícias com
população menor do que a população mínima
43
Método balance
public void balance () throws IllegalArgumentException,
InvalidOperationException
{
int parentIndex = parent.findIndex (this.key [1]);
int LeftSister = getCountLeftSister (parentIndex);
int RightSister = getCountRightSister (parentIndex);
if (LeftSister > getMin ())
{
parent.doLLRotation (parentIndex);
}
else if (RightSister > getMin ())
{
parent.doRRRotation (parentIndex);
}
else if (LeftSister >= RightSister)
{
parent.concatenation (parentIndex);
}
else
{
parent.concatenation (parentIndex + 1);
}
}
44
Método printTree
public void printTree (Visitor visitor, int espaços)
throws ContainerEmptyException
{
if (!isEmpty ())
{
for (int i = count + 1; i >= 0; --i)
{
if (i <= count)
{
((BTree) subtree [i]).printTree (visitor, espaços +
3);
}
if (i >= 1 && i <= count)
{
for (int o = espaços; o > 0; --o)
System.out.print (" ");
visitor.visit (key [i]);
}
}
}
else if (parent == null)
throw new ContainerEmptyException ("Arvore vazia!");
}
45
Método getCountLeftSister
Obtém a população da irmã esquerda
Se for a primeira página sua irmã da esquerda
(inexistente) recebe população menor do que o
mínimo
Caso contrário usa-se o método getCount
parent.subtree[index - 1].getCount()
46
Método getCountLeftSister
public int getCountLeftSister
(int index)
{
if (index == 0)
return getMin () - 1;
else
return parent.subtree
[index - 1].getCount ();
}
47
Método getCountRightSister
Obtém a população da irmã direita
Se for a última página sua irmã da direita
(inexistente) recebe população menor do que o
mínimo
Caso contrário usa-se o método getCount
parent.subtree[index + 1].getCount()
48
Método getCountRightSister
public int getCountRightSister
(int index)
{
if (index == this.parent.count)
return getMin () - 1;
else
return parent.subtree
[index + 1].getCount ();
}
49
Método doLLRotation
Determina a posição do último objeto da irmã
esquerda e a sub árvore correspondente
No nó corrente pelo método insertPair são
gravados key[index] e a sub árvore determinada
no item anterior
key[index] recebe o último objeto da irmã
esquerda
O último objeto da irmã esquerda e a sub árvore
correspondente são removidos pelo método
removePair
50
Método doLLRotation
protected void doLLRotation (int index) throws
InvalidOperationException,
IllegalArgumentException
{
if (isEmpty ())
throw new InvalidOperationException ("Operação inválida!");
Comparable tempKey;
BTree tempSubtree;
int ultimaPosiçao;
ultimaPosiçao = subtree [index - 1].getCount ();
tempKey = subtree [index - 1].key [ultimaPosiçao];
tempSubtree = (BTree) subtree [index - 1].subtree
[ultimaPosiçao];
((BTree) subtree [index]).insertPair (key [index],
tempSubtree);
key [index] = tempKey;
((BTree) subtree [index - 1]).removePair (ultimaPosiçao);
}
51
Método doRRRotation
Determina a posição do primeiro objeto da irmã
direita e a sub árvore correspondente
No nó corrente pelo método insertPair são
gravados key[index + 1] e a sub árvore
determinada no item anterior
key[index + 1] recebe o primeiro objeto da irmã
direita
O primeiro objeto da irmã direita e a sub árvore
correspondente são removidos pelo método
removePair
52
Método doRRRotation
protected void doRRRotation (int index) throws
InvalidOperationException,
IllegalArgumentException
{
if (isEmpty ())
throw new InvalidOperationException
("Operação inválida!");
BTree tempSubtree;
tempSubtree = (BTree) subtree [index + 1].subtree [0];
((BTree) subtree [index]).insertPair
(key [index + 1], tempSubtree);
key [index + 1] = subtree [index + 1].key [1];
subtree [index + 1].subtree [0] =
subtree [index + 1].subtree [1];
((BTree) subtree [index + 1]).removePair (1);
}
53
Método concatenation
Concatena a página filha corrente (que será desalocada) com
sua irmã esquerda
A chave separadora de nós (key [index]) e a sub árvore da
esquerda da página filha corrente são copiados para a irmã
esquerda pelo método insertPair
Todas as chaves e sub árvores correspondentes da página filha
corrente são copiados para a irmã esquerda pelo método
insertPair
Todas as chaves e sub árvores da página corrente (ancestral
das que sofreram concatenação) maiores do que key
[index], que perdeu levado para a filha esquerda, são
deslocados para a esquerda
A última chave e a última sub árvore da página corrente são
anuladas
54
Método concatenation
protected void concatenation (int index) throws
IllegalArgumentException
{
((BTree) subtree [index - 1]).insertPair (key [index],
(BTree) subtree [index].subtree [0]);
for (int i = 1; i <= subtree [index].getCount (); ++i)
{
((BTree) subtree [index - 1]).insertPair
(subtree [index].key [i], BTree) subtree
[index].subtree [i]);
}
int i;
--count;
for (i = index; i <= count; ++i)
{
key [i] = key [i + 1];
subtree [i] = subtree [i + 1];
}
key [i] = null;
subtree [i] = null;
}
55
Método rootTrim
protected void rootTrim ()
{
count = subtree [0].getCount ();
int i;
for (i = count; i > 0; --i)
{
key [i] = subtree [0].key [i];
subtree [i] = subtree [0].subtree [i];
((BTree) subtree [i]).parent = this;
}
subtree [i] = subtree [0].subtree [i];
((BTree) subtree [i]).parent = this;
}
56
Método removePair
Remove de uma página a chave key [index] e
a sub árvore correspondente
O contador de objetos é decrementado
Todas as chaves e sub árvores da página corrente
maiores do que key [index], que perdeu
levado para a filha esquerda, são deslocados para a
esquerda
A última chave e a última sub árvore da página
corrente são anuladas
57
Método removePair
public void removePair (int index)
{
int i;
--count;
for (i = index; i <= count; ++i)
{
key [i] = key [i + 1];
subtree [i] = subtree [i + 1];
}
key [i] = null;
subtree [i] = null;
}
58
Árvores B
FrameWork C++ de Bruno Preiss
Framework de Árvores e Busca
60
Árvores MWay
61
Declaração da Classe Object
//
pgm05_01.cpp
class Object
{
protected:
virtual int CompareTo (Object const&) const = 0;
public:
virtual ~Object ();
virtual bool IsNull () const;
virtual int Compare (Object const&) const;
virtual HashValue Hash () const = 0;
virtual void Put (ostream&) const = 0;
};
62
Declaração da Classe Container
//
pgm05_09.cpp
class Container : public virtual Object, public virtual
Ownership
{
protected:
unsigned int count;
Container ();
public:
virtual unsigned int Count () const;
virtual bool IsEmpty () const;
virtual bool IsFull () const;
virtual HashValue Hash () const;
virtual void Put (ostream&) const;
virtual Iterator& NewIterator () const;
virtual void Purge () = 0;
virtual void Accept (Visitor&) const = 0;
};
63
Declaração da Classe Ownership
//
pgm05_17.cpp
class Ownership
{
bool isOwner;
protected:
Ownership () : isOwner (true)
{}
Ownership (Ownership& arg) : isOwner (arg.isOwner)
{ arg.isOwner = false; }
public:
void AssertOwnership ()
{ isOwner = true; }
void RescindOwnership ()
{ isOwner = false; }
bool IsOwner () const
{ return isOwner; }
};
64
Declaração da Classe
SearchableContainer
//
pgm05_21.cpp
class SearchableContainer : public
virtual Container
{
public:
virtual bool IsMember (Object const&)
const = 0;
virtual void Insert (Object&) = 0;
virtual void Withdraw (Object&) = 0;
virtual Object& Find (Object const&)
const = 0;
};
65
Declaração da Classe Tree
//
pgm09_01.cpp
class Tree : public virtual Container
{
class Iter;
public:
virtual Object& Key () const = 0;
virtual Tree& Subtree (unsigned int) const = 0;
virtual bool IsEmpty () const = 0;
virtual bool IsLeaf () const = 0;
virtual unsigned int Degree () const = 0;
virtual int Height () const;
virtual void DepthFirstTraversal (PrePostVisitor&) const;
virtual void BreadthFirstTraversal (Visitor&) const;
void Accept (Visitor&) const;
};
66
Declaração da Classe SearchTree
//
pgm10_01.cpp
class SearchTree :
public virtual Tree, public virtual
SearchableContainer
{
public:
virtual Object& FindMin () const = 0;
virtual Object& FindMax () const = 0;
};
67
Classe MwayTree: Definição
//
pgm10_13.cpp
class MWayTree : public SearchTree
{
protected:
unsigned int const m;
unsigned int numberOfKeys;
Array<Object*> key;
Array<MWayTree*> subtree;
unsigned int FindIndex (Object const&) const;
public:
MWayTree (unsigned int);
~MWayTree ();
Object& Key (unsigned int) const;
MWayTree& Subtree (unsigned int) const;
Object& Find (Object const& ) const;
int GetCount() { return numberOfKeys; }
};
68
Funções Membro Construtor e Destrutor
da Classe MWayTree
MWayTree::MWayTree (unsigned int n) : m(n)
{
key.SetLength(m);
subtree.SetLength(m);
}
MWayTree::~MWayTree ()
{
}
69
Funções Membro Subtree e Key da
Classe MWayTree
MWayTree& MWayTree::Subtree (unsigned int i)
const
{
return *subtree[m];
}
Object& MWayTree::Key(unsigned int i) const
{
return *key[m];
}
70
Método Find
Recebe uma referencia a um objeto e
localiza o item na árvore de busca que
coincide com o objeto buscado
Caso o objeto buscado não exista retorna
uma instancia de NullObject
71
Método Find da Classe MWayTree
sem uso de função FindIndex
//
pgm10_15.cpp
Object& MWayTree::Find (Object const& object) const
{
if (IsEmpty ())
return NullObject::Instance ();
unsigned int i = numberOfKeys;
while (i > 0)
{
int const diff = object.Compare (*key [i]);
if (diff == 0)
return *key [i];
if (diff > 0)
break;
--i;
}
return subtree [i]->Find (object);
}
72
Método FindIndex
Recebe uma referencia a um objeto x e
retorna i que é o maior valor tal que x ≥ ki,
sendo ki a chave de ordem i no nó
73
Método FindIndex da Classe MWayTree
// pgm10_16.cpp
unsigned int MWayTree::FindIndex (Object const& object) const
{
if (IsEmpty ())
throw std::domain_error (“operação inválida");
if (object < *key [1])
return 0;
unsigned int left = 1;
unsigned int right = numberOfKeys;
while (left < right)
{
int const middle = (left + right + 1) / 2;
if (object >= *key [middle])
left = middle;
else
right = middle - 1U;
}
return left;
74
}
Método Find da Classe MWayTree
com uso de função FindIndex
Object& MWayTree::Find (Object const& object) const
{
if (IsEmpty ())
return NullObject::Instance ();
unsigned int const index = FindIndex (object);
if (index != 0 && object == *key [index])
return *key [index];
else
return subtree [index]->Find (object);
}
75
Classe Btree (1)
//
pgm10_19.cpp
class BTree : public MWayTree
{
BTree* parent;
void InsertPair (Object&, BTree&);
void RemovePair(unsigned int index);
void AttachKey (unsigned int, Object&);
void AttachSubtree (unsigned int, MWayTree&);
Object& InsertKey (unsigned int, Object&);
BTree& InsertSubtree (unsigned int, BTree&);
void AttachLeftHalfOf (BTree const&);
void AttachRightHalfOf (BTree const&, Object&, BTree&);
bool IsFull();
unsigned int GetMin ();
void Balance ();
void PrintTree (Visitor& visitor, int spaces);
unsigned int GetCountRightSister (unsigned int index);
unsigned int GetCountLeftSister (unsigned int index);
void RRRotation (unsigned int index);
void LLRotation (unsigned int index);
void TrimmRoot ();
virtual MWayTree& Subtree (unsigned int) const ;
virtual bool IsEmpty () const ;
virtual bool IsLeaf () const ;
virtual unsigned int Degree () const ;
76
Classe Btree (2)
Object& FindMin () const;
Object& FindMax () const;
Object& Key(unsigned int );
bool IsMember (Object const& obj) const { return (
Find(obj) != NullObject::Instance() ); };
int CompareTo (Object const&) const { return 0; };
HashValue Hash () const { return 0; };
void Put (std::ostream&) const {};
protected:
void Concatenation (int index);
public:
BTree (unsigned int);
BTree (unsigned int, BTree&);
void Insert (Object&);
void Withdraw (Object&);
};
77
Função Membro Construtor da
Classe BTree
BTree::BTree (unsigned int m,
BTree& ancestral) : MWayTree(m)
{
this->parent = &ancestral;
}
78
Método Insert da Classe Btree (1)
//
pgm10_20.cpp
void BTree::Insert (Object& object)
{
if (IsEmpty ())
// ponteiro aterrado (folha)
{
if (parent == 0) // nó sem pai (raiz)
{
AttachSubtree (0, *new BTree (m, *this));
// nova árvore é o filho 0
AttachKey (1, object);
// objeto a inserir é a chave 1
AttachSubtree (1, *new BTree (m, *this));
// nova árvore é o filho 1
numberOfKeys = 1;
}
79
Método Insert da Classe Btree (2)
else
// folha com pai
// inserir no ancestral o objeto e árvore filho m
parent->InsertPair (object,
*new BTree (m, *parent));
}
else
// não estamos em folha
{
unsigned int const index = FindIndex (object);
// index é, no nó,a posição “abaixo” de object
if (index != 0 && object == *key [index])
throw std::domain_error (“chave duplicada");
subtree [index]->Insert (object);
// inserir o objeto na sub árvore adequada
}
}
80
Método InsertPair da Clase Btree (1)
//
pgm10_21.cpp
void BTree::InsertPair (Object& object, BTree& child)
{
unsigned int const index = FindIndex (object);
// posição da inserção
BTree& extraTree = InsertSubtree (index + 1,
child);
// insere sub árvore à direita de index
Object& extraKey = InsertKey (index + 1, object);
// insere objeto à direita de index
81
Método InsertPair da Clase Btree (2)
if (++numberOfKeys == m) // nó transborda
{
if (parent == 0)
// era a raiz
{
BTree& left = *new BTree (m, *this);
// left é nó de ordem m filho do corrente
BTree& right = *new BTree (m, *this);
// right é nó de ordem m filho do corrente
left.AttachLeftHalfOf (*this);
// adicionar a left a metade esquerda do nó corrente
right.AttachRightHalfOf (*this, extraKey, extraTree);
// adicionar a right o par inserido e a metade direita
// do nó corrente
AttachSubtree (0, left);
AttachKey (1, *key [(m + 1)/2]);
AttachSubtree (1, right);
numberOfKeys = 1;
}
82
Método InsertPair da Clase Btree (3)
else // nó transborda mas tem ancestral
{
numberOfKeys = (m + 1)/2 - 1;
// nova população da página corrente
BTree& right = *new BTree (m, *parent);
// right nova página irmã direita
right.AttachRightHalfOf (*this, extraKey, extraTree);
// adicionar a right o par a inserir e a metade direita
// do nó corrente
parent->InsertPair (*key [(m + 1)/2], right);
// inserir no ancestral o par objeto do meio e
// a página right
}
}
}
83
Função Membro AttachSubtree
void BTree::AttachSubtree (unsigned
int i, MWayTree& child)
{
subtree [i] = &child;
((BTree&) child).parent == this;
}
84
Função Membro InsertSubtree (1)
BTree& BTree::InsertSubtree (unsigned int index, BTree& child)
{
//Esta função vai retornar null quando o nó não estiver cheio
// quando o nó estiver cheio retorna a sub árvore que transbordou
if (IsFull ())
{
if (index == m)
// a sub árvore a inserir era maior do que as demais e vai sobrar
return child;
else
{
// vai sobrar a sub árvore que era a maior de todas
BTree& extraTree = (BTree&) *subtree [numberOfKeys];
for (int i = numberOfKeys - 1; i >= index; --i)
{
subtree[i + 1] = subtree[i];
}
AttachSubtree(index, child);
return extraTree;
}
}
85
Função Membro InsertSubtree (2)
else // nó com espaço
{
child.parent = this;
for (int i = numberOfKeys; i >= index;
--i)
{
subtree [i + 1] = subtree [i];
}
subtree [index] = &child;
}
return (BTree&) NullObject::Instance();
}
86
Função Membro InsertKey (1)
Object& BTree::InsertKey (unsigned int index, Object& object)
{
//Esta função vai retornar null quando o nó não
estiver cheio
// quando o nó estiver cheio retorna a chave que
transbordou
if (IsFull ())
{
if (index == m)
// a chave a inserir era maior do que as demais e
vai sobrar
return object;
else
{
// vai sobrar a chave que era a maior de todas
Object& extraKey = *key [numberOfKeys];
for (int i = numberOfKeys - 1; i >= index; --i)
{
key [i + 1] = key [i];
}
key [index] = &object;
return extraKey;
}
87
}
Função Membro InsertKey (2)
else // nó com espaço
{
for (int i = numberOfKeys; i >= index;
--i)
{
key [i + 1] = key [i];
}
key [index] = &object;
}
return NullObject::Instance ();
}
88
Função Membro Withdraw (1)
// pgm10_18.cpp
void MWayTree::Withdraw (Object& object)
{
if (IsEmpty ())
throw InvalidOperationException("objeto nao encontrado");
unsigned int const index = FindIndex (object);
if (index != 0 && object == *key [index])
{
if (!subtree [index - 1U]->IsEmpty ())
{
Object& max = subtree [index - 1U]->FindMax ();
key [index] = &max;
subtree [index - 1U]->Withdraw (max);
}
else if (!subtree [index]->IsEmpty ())
{
Object& min = subtree [index]->FindMin ();
key [index] = &min;
subtree [index]->Withdraw (min);
}
89
Função Membro Withdraw (2)
else
{
--numberOfKeys;
delete subtree [index];
for(unsigned int i = index; i <= numberOfKeys; ++i)
{
key [i] = key [i + 1];
subtree [i] = subtree [i + 1];
}
}
}
else
subtree [index]->Withdraw (object);
if (numberOfKeys < GetMin())
if (parent != 0)
Balance();
else if (numberOfKeys == 0)
RootTrim();
}
90
Função Membro FindMin
Object& BTree::FindMin () const
{
if (IsEmpty ())
return NullObject::Instance ();
else if (subtree[0]->IsEmpty ())
return *key[1];
else
return subtree[0]->FindMin();
}
91
Função Membro FindMax
Object& BTree::FindMax () const
{
if (IsEmpty ())
return NullObject::Instance ();
else if (subtree[numberOfKeys]->IsEmpty ())
return *key[numberOfKeys];
else
return subtree[numberOfKeys]->FindMax();
}
92
Função Membro GetMin e IsFull
unsigned int BTree::GetMin ()
{
return ((m + 1) / 2) - 1;
}
bool BTree::IsFull ()
{
return (m - 1) == numberOfKeys;
}
93
Função Membro Balance (1)
void BTree::Balance ()
{
int parentIndex = parent->FindIndex (this>key [1]);
int leftSister = GetCountLeftSister
(parentIndex);
int rightSister = GetCountRightSister
(parentIndex);
if (leftSister > GetMin ())
{
parent->LLRotation (parentIndex);
}
94
Função Membro Balance (2)
else if (rightSister > GetMin ())
{
parent->RRRotation (parentIndex);
} // else if (parentIndex + 2 != 0 && ...
else if (leftSister >= rightSister)
{
parent->Concatenation (parentIndex);
}
else
{
parent->Concatenation (parentIndex + 1);
}
}
95
Função Membro PrintTree (1)
void BTree::PrintTree (Visitor visitor, int spaces)
{
if (!IsEmpty ())
{
for (int i = numberOfKeys + 1; i >= 0; --i)
{
if (i <= numberOfKeys)
{
((BTree*) subtree [i])->printTree
(visitor, spaces + 3);
}
96
Função Membro printTree (2)
if (i >= 1 && i <= numberOfKeys)
{
for (int o = spaces; o > 0; --o)
printf (" ");
visitor.Visit (*key [i]);
}
}
}
else if (parent == 0)
throw new ContainerEmptyException
("Arvore vazia!");
}
97
Função Membro GetCountLeftSister
unsigned int BTree::GetCountLeftSister
(unsigned int index)
{
if (index == 0)
return GetMin () - 1;
else
return
parent->subtree [index - 1]-> GetCount();
}
98
Função Membro GetCountRightSister
unsigned int BTree::GetCountRightSister
(unsigned int index)
{
if (index ==
this->parent->numberOfKeys)
return GetMin () - 1;
else
return
parent->subtree [index + 1]-> GetCount();
}
99
Função
Membro
LLRotation
void BTree::LLRotation (unsigned int index)
{
if (isEmpty ())
throw new InvalidOperationException
("Operação inválida!");
int lastPosition;
lastPosition = subtree [index - 1]->GetCount ();
Object & tempKey = subtree[index - 1]->Key(lastPosition);
BTree & tempSubtree =
(BTree&) subtree[index - 1]>Subtree(lastPosition);
((BTree*)subtree [index])->InsertPair(*key [index],
tempSubtree);
key [index] = &tempKey;
((BTree*) subtree [index - 1])->RemovePair (lastPosition);
}
100
Função Membro RRRotation
void BTree::RRRotation (unsigned int index)
{
if (IsEmpty ())
throw new InvalidOperationException
("Operação inválida!");
BTree & tempSubtree =
(BTree &) subtree [index + 1]->Subtree(0);
((BTree*) subtree [index])->InsertPair
(*key [index + 1], tempSubtree);
key[index + 1] = &subtree[index + 1]->Key(1);
((Tree&)subtree [index + 1]->Subtree(0)) =
((Tree&)subtree [index + 1]->Subtree(1));
((BTree*) subtree [index + 1])->RemovePair (1);
}
101
Função Membro Concatenation
void BTree::Concatenation (int index)
{
((BTree*) subtree [index - 1])->InsertPair (*key [index],
(BTree&) subtree [index]->Subtree(0));
for (int i = 1; i <= subtree [index]->GetCount (); ++i)
{
((BTree*) subtree [index - 1])->InsertPair
(subtree [index]->Key(i), (BTree&) subtree [index]->Subtree(i));
}
--numberOfKeys;
for (i = index; i <= numberOfKeys; ++i)
{
key [i] = key [i + 1];
subtree [i] = subtree [i + 1];
}
key [i] = 0;
subtree [i] = 0;
}
102
Função Membro TrimmRoot
void BTree::TrimmRoot ()
{
{
numberOfKeys = subtree [0]->GetCount ();
int i;
for (i = numberOfKeys; i > 0; --i)
{
key [i] = &subtree [0]->Key(i);
subtree [i] = &subtree [0]->Subtree(i);
((BTree*) subtree [i])->parent = this;
}
subtree [i] = &subtree [0]->Subtree(i);
((BTree*) subtree [i])->parent = this;
}
}
103
Função Membro RemovePair
void BTree::RemovePair (unsigned int index)
{
int i;
--numberOfKeys;
for (i = index; i <= numberOfKeys; ++i)
{
key [i] = key [i + 1];
subtree [i] = subtree [i + 1];
}
key [i] = 0;
subtree [i] = 0;
}
104
Função Membro AttachLeftHalfOf
void BTree::AttachLeftHalfOf (BTree const& tree)
{
AttachSubtree (0, *tree.subtree [0]);
numberOfKeys = 0;
for (int ind = 1; ind < tree.m / 2; ++ind)
{
InsertPair (*tree.key [ind],
(BTree&)(*tree.subtree [ind]));
}
}
105
Função Membro AttachRightHalfOf
void BTree::AttachRightHalfOf
(BTree const&, Object& extraKey, BTree& tree)
{
AttachSubtree (0, *tree.subtree [(m + 1) / 2]);
numberOfKeys = 0;
for (int ind = tree.m - 1; ind > tree.m + 1) / 2;
--ind)
{
InsertPair (*tree.key[ind],
(BTree&) *tree.subtree[ind]);
}
}
106
class BTree : public MWayTree
{
BTree* parent;
void InsertPair (Object&, BTree&);
void AttachKey (unsigned int, Object&);
void AttachSubtree (unsigned int, MWayTree&);
Object& InsertKey (unsigned int, Object&);
BTree& InsertSubtree (unsigned int, BTree&);
void AttachLeftHalfOf (BTree const&);
void AttachRightHalfOf (BTree const&, Object&, BTree&);
bool IsFull();
public:
BTree (unsigned int);
BTree (unsigned int, BTree&);
void Insert (Object&);
void Withdraw (Object&);
};
107