Árvores B Implementação pelos FrameWork Bruno Preiss

Árvores B

Implementação pelos FrameWork Bruno Preiss

Árvores B

FrameWork Java de Bruno Preiss

3

Framework de Árvores e Busca

4

Interface Comparable

//pgm05_01.txtpublic 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);}

5

Declaração da classe AbstractObject// pgm05_02.txtpublic 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;

}

6

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 ()); } // ...}

7

Interface Container

public interface Container extends Comparable{ int getCount (); boolean isEmpty (); boolean isFull (); void purge (); void accept (Visitor visitor); Enumeration getEnumeration ();}

8

Interface SearchableContainer

public interface SearchableContainer extends Container{ boolean isMember (Comparable object); void insert (Comparable object); void withdraw (Comparable obj); Comparable find (Comparable object);}

9

Interface Tree

//pgm09_01.txtpublic 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);}

10

Interface SearchTree

//pgm10_01.txtpublic interface SearchTree extends Tree, SearchableContainer

{ Comparable findMin (); Comparable findMax ();}

11

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; }

// ...}

12

Classe Abstrata AbstractTree

// pgm09_02.txtpublic 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 ());}

} // ...}

13

Árvores MWay

14

Classe MwayTree: Métodos construtor e getM

//pgm10_14.txtpublic 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; }

// ...}

15

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

16

Método find da Classe MWayTree//pgm10_16.txtpublic 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);

} }

17

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ó

18

Método findIndex da Classe MWayTree//pgm10_17.txtpublic 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;

}

19

Classe BTree

// pgm10_20.txtpublic 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;

} // ...}

20

Método insert da Classe BTree

Insere uma chave em uma página de árvore BSe 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 insertPairSe 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)

21

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; } elseparent.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);}

}

22

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

23


A página transbordou e é preciso balancear a árvoreSe 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

24


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)

25

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;

}

26

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);

}}

}

27

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

28

Método attachSubtree

public void attachSubtree

(int i, MWayTree arg)

{

BTree btree = (BTree) arg;

subtree [i] = btree;

btree.parent = this;

}

29

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]); } }

30

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]);

} }

31

Método insertSubtree

Recebe um inteiro índice e uma sub árvore e deve inserir na correta posição do array de sub árvoresCaso 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

32

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); } }

33

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; }

34

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

35

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; } }

36

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; }

37

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

38


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

39


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

40

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); }

41

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 (); }

42

Métodos getMin e isFull

public int getMin ()

{

return ((getM () + 1) / 2) - 1;

}

public boolean isFull ()

{

return getM () - 1 == count;

}

43

Método balanceEquilibra uma página sub povoadaDetermina a posição no paiObtém a população das irmãs esquerda e direitaCaso a população da esquerda seja maior do que o mínimo executa uma rotação à esquerdaSenão se a população da direita for maior do que o mínimo executa uma rotação à direitaCaso 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

44

Método balancepublic 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); } }

45

Método printTreepublic 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!"); }

46

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 getCountparent.subtree[index - 1].getCount()

47

Método getCountLeftSister

public int getCountLeftSister (int index) { if (index == 0) return getMin () - 1; else return parent.subtree [index - 1].getCount (); }

48

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 getCountparent.subtree[index + 1].getCount()

49

Método getCountRightSister

public int getCountRightSister (int index) { if (index == this.parent.count) return getMin () - 1; else return parent.subtree [index + 1].getCount (); }

50

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 anteriorkey[index] recebe o último objeto da irmã esquerdaO último objeto da irmã esquerda e a sub árvore correspondente são removidos pelo método removePair

51

Método doLLRotationprotected 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); }

52

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 anteriorkey[index + 1] recebe o primeiro objeto da irmã direitaO primeiro objeto da irmã direita e a sub árvore correspondente são removidos pelo método removePair

53

Método doRRRotationprotected 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); }

54

Método concatenationConcatena a página filha corrente (que será desalocada) com sua irmã esquerdaA 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 insertPairTodas as chaves e sub árvores correspondentes da página filha corrente são copiados para a irmã esquerda pelo método insertPairTodas 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 esquerdaA última chave e a última sub árvore da página corrente são anuladas

55

Método concatenationprotected 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; }

56

Método rootTrimprotected 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; }

57

Método removePair

Remove de uma página a chave key [index] e a sub árvore correspondenteO contador de objetos é decrementadoTodas 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 esquerdaA última chave e a última sub árvore da página corrente são anuladas

58

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; }

Árvores B

FrameWork C++ de Bruno Preiss

60

Framework de Árvores e Busca

61

Árvores MWay

62

Declaração da Classe Object

// pgm05_01.cppclass 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;};

63

Declaração da Classe Container// pgm05_09.cppclass 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;};

64

Declaração da Classe Ownership

// pgm05_17.cppclass 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; }};

65

Declaração da Classe SearchableContainer

// pgm05_21.cppclass 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;

};

66

Declaração da Classe Tree

// pgm09_01.cppclass 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;};

67

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;};

68

Classe MwayTree: Definição// pgm10_13.cppclass 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; }};

69

Funções Membro Construtor e Destrutor da Classe MWayTree

MWayTree::MWayTree (unsigned int n) : m(n)

{

key.SetLength(m);

subtree.SetLength(m);

}

MWayTree::~MWayTree ()

{

}

70

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];

}

71

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

72

Método Find da Classe MWayTreesem uso de função FindIndex // pgm10_15.cppObject& 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);}

73

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ó

74

Método FindIndex da Classe MWayTree// pgm10_16.cppunsigned 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;}

75

Método Find da Classe MWayTreecom 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);

}

76

Classe Btree (1)// pgm10_19.cppclass 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 ;

77

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&);};

78

Função Membro Construtor da Classe BTree

BTree::BTree (unsigned int m,

BTree& ancestral) : MWayTree(m)

{

this->parent = &ancestral;

}

79

Método Insert da Classe Btree (1)

// pgm10_20.cppvoid 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;}

80

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 }}

81

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

82


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;}

83


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

} }}

84

Função Membro AttachSubtree

void BTree::AttachSubtree (unsigned

int i, MWayTree& child)

{

subtree [i] = &child;

((BTree&) child).parent == this;

}

85

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; } }

86

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(); }

87

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; } }

88

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 (); }

89

Função Membro Withdraw (1)// pgm10_18.cppvoid 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);}

90

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();

}

91

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();

}

92

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();

}

93

Função Membro GetMin e IsFull

unsigned int BTree::GetMin ()

{

return ((m + 1) / 2) - 1;

}

bool BTree::IsFull ()

{

return (m - 1) == numberOfKeys;

}

94

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); }

95

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); } }

96

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); }

97

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!"); }

98

Função Membro GetCountLeftSister

unsigned int BTree::GetCountLeftSister (unsigned int index)

{ if (index == 0) return GetMin () - 1; else return parent->subtree [index - 1]-> GetCount(); }

99

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(); }

100

Função Membro LLRotationvoid 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);}

101

Função Membro RRRotationvoid 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);}

102

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;}

103

Função Membro TrimmRootvoid 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; } }

104

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; }

105

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]));

} }

106

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]);

} }

107

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&);};

Documents

Árvores B Implementação pelos FrameWork Bruno Preiss