Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

ÁRVORE 2-3-4

No description
by

Fernando Machado

on 8 December 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of ÁRVORE 2-3-4

ANALISE
CONCEITOS
FUNCIONAMENTO
APLICABILIDADE
Árvores 2-3-4
Introdução
Introdução
Os 4-nós tem as seguintes propriedades

Introdução
Inserção de Nós

Se o local for 4-nós,
split

Busca de uma Chave


3)
Recursivamente, segue os links associados

Remoçao de Nós
Ao encontrá-lo, reduza o elemento da árvore

Remoção de Nós
Porém, ao remover um elemento de um 2-nós se causa
Underflow
(Abaixo do Solicitado)
Para eliminar o
Underflow
é preciso fazer uma
Transferência

(Transfer)

Remoção de Nós
Um outro caso, é quando todos os filhos de 3-nós são 2-nós
A solução é fazer a
F
usão (fuse)




O 2, 3 e 4, no nome árvore 2-3-4, referem-se a quantos links para filhos podem estar contidos em um dado nó.


Passos:
Passos:
Regras de Inserção de Nós
Alunos:
Mathias
Fernando
Victor
Machado
Philipe
Moreira
de Castro
Custodio
Moreira
Introdução



Balanço Perfeito: todos nós externos têm a mesma profundidade (same depth)


As chaves devem estar na ordem correta após a inserção de um novo item.
Primeiro de tudo, deve percorrer a árvore até encontrar o nodo que se deseja deletar
1)
Compara a chave requisitada com a chave do nodo
2)
Encontra o intervalo que contém a chave requisitada
*
Pesquise o local onde a chave deve ser inserida, lembrando que está é uma árvore ordenada
Se o local for 2-nós, converte para 3-nós
Se o local for 3-nós, converte para 4-nós
Novos itens de dados são sempre inseridos nas folhas (Bottom-up / Baixo p/ cima).
Cada nó tem dois ou mais filhos.
Se os itens forem inseridos em um nó que já possui filhos:
O número de filhos precisará ser mudado para manter a estrutura da árvore.
Assim, esta árvore deve ter um filho a mais do que os itens de dados em um nó.
A inserção começa pela busca do nó folha apropriado.
A inserção pode envolver a movimentação de um ou dois itens em um nó.
Inserção Nós
Existem 3 Casos na inserção:

3. Promote (Promoção):
uma nova raiz é criada (novo nível)
subindo uma das chaves que estarão no ramo inferior.
2.

Split (sub-divisão):
onde um nó é subdividido (split) em dois
nós, distribuindo as chaves igualmente entre eles.
As inserções tornam-se mais complicadas se um nó cheio é encontrado no caminho abaixo do ponto de inserção.
Quando isso acontece o nó precisa ser dividido (Split).
É esse processo de divisão que mantém a árvore balanceada.
1.

Inserção ordenada nas folhas.
Não tem divisão de nó. (Deslocamento chaves ou não)

A menos que seja um nó folha, e neste caso, ele não possui
links
.
Comparação
3)
Permite nós com mais de 3 filhos, deixando a árvore 2-3-4 com um altura menor do que a 2-3

Árvore 2-3 x Árvore 2-3-4
1)
Tanto uma como a outra são fáceis de manter balanceada
2)
Inserção do algoritmo da árvore 2-3-4 requer menos passos do que a árvore 2-3
Aplicações Práticas
Outras

(Em suas generalizações e equivalencias)
Dicionários
Auto Completar

(Code Completion)
Origem
Sendo assim, cada nó interno teria 2, 3 ou 4 filhos. Portanto a árvore-B é uma generalização da árvore 2-3-4
(Sedgewick, R. et al., 1998)
, que foi criada por
J.E. Hopcroft em
1970

(embora não tenha sido publicado).
A árvore-B mais simples é aquela que tem
t = 2 = ordem 2
(Arvore 2-3-4), isto é, cada nó tem pelo menos 1 e no máximo 3 chaves.
Equivalentes
Indexação de Discos (Bloco)

Generalização
Árvore-B
(
B-Tree
)
Há uma correspondência, equivalencia um para um, entre uma Árvore 2-3-4 e uma Árvore
Rubro
-
Negra

(
Red
-
Black
-Tree)
.
Muitos SGBDs utilizam
Árvore B
ou alguma variante (Exemplo:

Árvores B+
).
Características da Arvore-B:
A maioria das operações em uma
B-Tree
é proporcional ao número de acessos a disco executados.
Apesar de tanto a
Red
-
Black
Tree
como a
B-Tree

terem o crescimento da altura na ordem de O(log n) (Cormen, T.D. et al., 1990), a base do logaritmo para a B-Tree pode ser muito maior.
Desta forma, a
B-Tree
economiza aproximadamente log t em relação a red-black tree quanto ao crescimento da altura da árvore.
Buscas
Se
todos os nós forem 2-nós
, então a árvore será uma
Árvore Binária Completa
(
altura log n
), se tiver nós 3 ou 4, isto só pode diminuir a altura.
• Buscas em árvores 2-3-4 nunca passam mais de
log n + 1
nós, logo
O(log n)
A distância da raiz para as folhas é sempre a mesma.
Transformações não mudam esta distância, exceto no
pior caso
em que a transformação
divide a raiz
e aumenta em 1 a distância de todos os nós para a raiz.
Inserções
Árvores construídas a partir de uma permutação randômica de
n,
o
Pior Caso
se torna pouco provável.

Inserções requerem menos de

logn n + 1
divisões de

nos pior caso (
na média menos de 1
)
O
Pior Caso
da inserção seria todos os nós no caminho de inserção fossem
4-Nós
, e neste caso todos seriam divididos.
Inserções
O algoritmo é projetado para que funcione em uma única passada
Descendente
a partir da raiz.
Ao contrário de árvores binárias, a inserção em árvores 2-3-4 faz a árvore crescer “para cima” e não “para baixo”.
(Up Down)
Ou seja, a árvore só aumenta de altura, através da
Divisão da Raiz
. Isto garante que todos os nós folhas são sempre mantidos em um único nível.
Pesquisa
Logo, requer tempo
0(h)
, onde h é a altura da árvore.
A recuperação em árvores 2-3-4 é feita através do algoritmo para árvores
n-árias
.(
Multi Via
)
Vantagens
x
Desvantagens
A árvore 2-3-4
desperdiça espaço
porque muitos nós não estão nem mesmo cheios pela metade.

A altura de uma árvore 2-3-4 é menor que

log2N
.
Os tempos de busca são proporcionais à altura
h
.
Referências
ZIVIANE, N.,
Projetos de Algoritmos com Implementação em Pascal e C
. Livraria Pioneira Editora. 1996.

LAFORE, Robert.
Estruturas de dados e algoritmos em Java
. Rio de Janeiro: Ciência Moderna, 2005.

GOODRICH, Michael T.; TAMASSIA, Roberto. P
rojeto de Algoritmos: Fundamentos, análise e exemplos da Internet
. Bookman, 2004.

Notas de aula da disciplina, disponível no Moodle
.

Este tipo de árvore permite 1, 2 ou 3 chaves por nó
2-nós: uma chave, dois filhos
3-nós: duas chaves, três filhos
4-nós: três chaves, quatro filhos
Os nós 2 e 3 contém as mesmas propriedades da árvore 2-3
A generalização de um nó permite múltiplas chaves e filhos
A árvore 2-3-4 ou 2-4 é uma árvore ordenada e balanceada
Árvore 2-3-4 são árvores B de ordem ou grau 4, sendo a árvore B a generalização
Assim como a árvore 2-3, esta mantém o “balanço perfeito”, ou seja, altura invariante
Cada nodo tem no maximo quatro filhos.
Porque uma árvore 2-3-4 não é chamada de árvore 1-2-3-4?
Um nó não pode ter somente um filho, como os nós das Árvores Binárias.
Um nó com um item de dado precisa ter sempre dois links.
Cada valor v inserido na subárvore
A
deve ser <=
F
Cada valor v inserido na subárvore
B
deve ser >
F
e <=
G
Cada valor v inserido na subárvore
C
deve ser >
G
e <=
J
Cada valor v inserido na subárvore
D
deve ser >
J
O tamanho do caminho a partir da raiz do 4-nós até a qualquer folha deve ser o mesmo
Remoção de Nós
O
underflow
pode acontecer em cascata
Full transcript