Árvores de busca - aula 4

Prévia do material em texto

24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 1/56
Árvores de busca
Prof.ª Simone Ingrid Monteiro Gama
Descrição
Apresentação dos percursos em árvores binárias. Conceituação de árvores AVL e dos algoritmos para
manutenção da propriedade AVL. Conceituação de árvores B e suas principais operações.
Propósito
A busca, inserção e remoção de informações em uma estrutura de dados é um dos principais problemas da
computação. Estruturas desorganizadas resolvem esse problema em tempo linear. Por outro lado,
utilizando-se árvores podemos otimizar e resolver em um tempo proporcional a log N.
Objetivos
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 2/56
Módulo 1
Conceitos de balanceamento
Identificar os principais conceitos sobre balanceamento de árvores de busca e árvores binárias de busca.
Módulo 2
Árvores AVL
Definir os principais conceitos sobre árvores AVL.
Módulo 3
Árvores B
Reconhecer os principais conceitos de árvores B, suas principais vantagens e operações.
Módulo 4
Frameworks em Python para árvores de busca balanceada
Identificar os principais módulos e bibliotecas em Python para implementação de árvores de busca
binária e AVL.

24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 3/56
Introdução
Um dos problemas mais estudados em computação é o da busca, inserção e remoção de dados de uma
massa de dados. Desde os primórdios da computação, a preocupação com o desempenho dessas
operações está presente. Mas como dimensionar o esforço necessário para resolver esse problema?
Podemos analisar o problema com um exemplo prático. Suponha que temos um saco opaco com bolinhas
coloridas com cores distintas entre si e que desejamos encontrar a bolinha azul, mas que não podemos
olhar dentro do saco. Como achar a bolinha azul?
A solução óbvia é tirar uma a uma. Se tivermos sorte, a primeira bolinha retirada do saco será a azul, com
azar, a última. Ou seja, na pior das hipóteses, temos que tirar bolinhas do saco, o que configura a
complexidade da busca em uma estrutura de dados não organizada. Isso é busca em . Como otimizar
isso?
Organizando para conseguir tentar reduzir a complexidade computacional. Neste material, vamos aprender
a utilizar uma estrutura de dados capaz de realizar busca, inserção e remoção em complexidade
computacional de . Para tal, partiremos do conceito de árvores de busca balanceadas, como AVL e
árvore B, explorando suas principais operações. Em seguida, conheceremos os principais módulos e/ou
bibliotecas em Python usadas para manipular árvores.
n
O(n)
O(logn)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 4/56
1 - Conceitos de balanceamento
Ao �nal deste módulo, você será capaz de identi�car os principais conceitos sobre
balanceamento de árvores de busca e árvores binárias de busca.
Balanceamento em árvores
Confira agora o conceito de balanceamento e sua relação com a complexidade computacional das
operações de busca, inserção e remoção.
Árvores binárias de busca são estruturas de dados dinâmicas, isto é, capazes de realizar busca, inserção e
remoção de chaves, uma a uma, sem perder suas propriedades nem necessitar de processamento
suplementar para manter suas características. Entretanto, a estrutura de dados é complexa e não apresenta
ganho em relação a uma massa de dados desorganizada, isto é, ambas, no pior caso, necessitam de O(n)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 5/56
operações para busca, o que implica para inserção e remoção. Ou seja, a árvore binária de busca nãõ
é melhor em termos de performance computacional que uma lista sem organização alguma.
Por que estudar uma estrutura de dados mais complexa que uma lista, se sua
complexidade computacional é a mesma?
A resposta para esta pergunta requer uma análise do estudo da complexidade computacional dos
algoritmos de busca, inserção e remoção em árvores binárias de busca.
A complexidade computacional da busca é proporcional à altura da árvore, e que, no pior caso, uma árvore
tem altura . A família de árvores com altura é chamada de árvores zig-zag. A imagem a seguir mostra
uma árvore zig-zag de altura 8.
Imagem 1 - Árvore zig-zag de altura 8.
Isto é, as árvores zig-zag são a família de árvores binárias de busca com pior desempenho possivel, uma
vez que a complexidade da busca e, consequentemente, da inserção e da remoção é e não é possível
construir uma árvore binária de busca com altura maior que .
O(n)
n n
O(n)
n
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 6/56
Se as zig-zag são as piores árvores (piores no sentido que a complexidade e a
manutenção da estrutura são as mesmas de uma lista desorganizada), qual a
família com melhor desempenho?
Para responder a essa pergunta, recordaremos alguns conceitos de árvore binárias.
Árvores binárias
Diz-se que uma árvore binária é completa se os nós de com subárvores vazias estão no último ou no
penúltimo nivel.
A árvore da imagem a seguir é uma árvore completa. Os nós que possuem subárvores vazias estão no nível
3 e no nível 4, respectivamente, no penúltimo e no último nível da árvore.
Imagem 2 - Árvore binária completa.
Um resultado importante sobre as árvores binárias completas é o que se segue:
Seja uma árvore binária completa nós. Então possui altura mínima
e .
Esse resultado é muito importante, mostra que não existe árvore binária com nós com altura inferior à
. Ou seja, a melhor árvore binária que podemos construir tem altura proporcional a .
T T
T comn > 0 T
h = 1 + ⌊logn⌋
n
h = 1 + ⌊logn⌋ logn
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 7/56
Se limitarmos a construção das árvores binárias de busca às árvores binárias
completas, temos os algoritmos de busca, inserção e remoção funcionando em
. Esse é o objetivo, melhorar a complexidade computacional da busca,
inserção e remoção.
De forma ampla, dizemos que árvores binárias cujas alturas são proporcionais a são árvores
balanceadas. Ou seja, árvores binárias completas são balanceadas, mas será que toda árvore balanceada é
completa?
Resposta
Não, existem outras famílias de árvores binárias, neste caso especificamente, de busca, que são
balanceadas, porém não são completas, por exemplo, as árvores AVL e as árvores rubro-negras.
Construindo árvores balanceadas
Antes de estudarmos as estruturas de dados completamente dinâmicas que fornecem árvores binárias de
busca balanceadas, isto é, com altura de , vamos estudar o algoritmo que transforma uma árvore
binária de busca em uma árvore binária de busca completa.
Existem várias formas de se construir uma árvore binária de busca completa. A mais intuitiva é derivada da
pesquisa binária, que é um método de busca em um vetor ordenado que se baseia na estratégia "dividir para
conquistar". A ideia é simples, compara-se a chave que está se buscando com a chave armazenada no
elemento central do vetor, isto é, se o vetor tem tamanho , o elemento . Caso a chave buscada seja
menor que o elemento armazenado na posição , aplica-se o método recursivamente na primeira metade
do vetor, caso contrário, na segunda metade.
Esse método de busca é eficiente, uma vez que é capaz de realizar a busca em . Um exemplo de
aplicação desse método pode ser visto na imagem 3, que ilustra a busca da chave "55".
logn
logn
O(logn)
n n/2
n/2
O(logn)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 8/56
Imagem 3 - Pesquisa binária de “55”.
Confira, a seguir, o passo a passo:
1. Compara-se a chave central 8/2 = 4, que armazena a chave “40”, com a chave “55”. Assim, se “55” estiver
na estrutura de dados, estará na segunda metade.2. Compara-se a chave central (5+8)/2=6, que armazena a chave “60”, com a chave “55”. Assim, se “55”
estiver na estrutura, estará na primeira metade.
3. Compara-se a chave central (5+6)/2=5, que armazena a chave “50”, com a chave “55”. Assim, se “55”
estiver no vetor, estará na segunda metade, que é o elemento 6 do vetor, que não armazena a chave “55”,
terminando, assim, a busca binária.
Como realizamos comparações no pior caso, que é não encontrar a chave buscada, se
transformarmos as comparações possíveis em uma árvore, teremos uma árvore com altura proporcional à
, ou seja, uma árvore balanceada. A imagem a seguir ilustra o processo para o mesmo vetor:
O(logn)
logn
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 9/56
Imagem 4 - Construção de uma árvore binária de busca balanceada.
A cada passo, elegemos uma raiz, elemento central, e aplicamos recursivamente o método nas metades
esquerda e direita, que nos fornece as raízes das subárvores esquerda e direita recursivamente.
O método mostrado constrói uma árvore balanceada, uma vez que o número de níveis da árvore deriva do
número de comparações na pesquisa binária, e esse número é . Na verdade, podemos ver que
construímos uma árvore binária de busca completa, que também é balanceada.
Esse método de construção, apesar de intuitivo, possui diversas desvantagens. Precisamos de um vetor
auxiliar e a sequência de chaves ordenadas, o que, sem dúvida, aumenta a necessidade de alocação de
memória. O ideal é aplicar um algoritmo que resolva o problema de construir uma árvore binária de busca
sem utilizar nenhuma estrutura de dados auxiliar.
Aplicações das árvores balanceadas
Confira agora o motivo pelo qual o uso da estrutura de dados complexa é vantajoso em relação à estrutura
de dados desorganizada.
logn
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 10/56
Árvores binárias balanceadas possuem diversas aplicações teóricas e práticas, embora elas sejam
amplamente utilizadas na teoria e em melhoramento de performance algorítmica. Vamos conferir!
Árvores binárias de busca balanceadas podem ser usadas para construir e manter listas
ordenadas, tais como filas de prioridade. Podem também ser usadas para implementar
qualquer algoritmo que requeira listas ordenadas, para alcançar o melhor desempenho
assintótico.
Alguns algoritmos de geometria computacional exploram variações de árvores de busca
balanceadas para resolver diversos problemas, tais como a interseção entre segmentos de
reta e o problema de localização do ponto de forma eficiente.
Árvores AVL podem ser usadas para formar um dicionário de uma linguagem ou de
programas, como os opcodes de um assembler ou um interpretador.
Árvores B são exemplos de árvores amplamente utilizadas para organizar dados em banco de
dados e HD.
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 11/56
Falta pouco para atingir seus objetivos.
Vamos praticar alguns conceitos?
Questão 1
Marque a opção correta sobre árvores balanceadas:
Parabéns! A alternativa A está correta.
As árvores balanceadas devem possuir altura proporcional a .
Questão 2
Considerando que a seguinte árvore é binária, assinale a opção correta.
A Toda árvore balanceada tem altura proporcional a .logn
B Toda árvore balanceada é completa.
C Toda árvore balanceada é cheia.
D Toda árvore balanceada é zig-zag.
E Toda árvore balanceada tem altura proporcional a .n
logn
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 12/56
Parabéns! A alternativa B está correta.
O número de folhas da árvore é 4, ou seja, são aqueles nós que possuem grau zero.
A A árvore acima possui raiz de valor 3.
B A quantidade de folhas da árvore é 4.
C É possível inserir mais um filho à esquerda no nó de valor 5.
D A quantidade de nós folha da árvore é de - 1, sem considerar o nó raiz.n
E Todos os nós podem ser considerados nós folha.
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 13/56
2 - Árvores AVL
Ao �nal deste módulo, você será capaz de de�nir os principais conceitos sobre árvores AVL.
Árvores AVL: principais de�nições
Confira agora o conceito de árvore AVL e entenda por que são balanceadas.
Ao estudar a complexidade dos algoritmos de construção de árvores (binárias) de busca, observamos que a
estrutura de dados, apesar de complexa, não tinha desempenho teórico superior às listas desorganizadas.
Isso se deve ao fato de que, no pior caso, a complexidade das operações de busca, inserção e remoção é
.O(n)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 14/56
Em seguida, vimos que, para uma redução de complexidade, temos que ter árvores binárias de busca com
altura proporcional à e as árvores com essa propriedade são chamadas de árvores balanceadas.
A evolução desse cenário é a obtenção de uma estrutura de dados completamente dinâmica que suporte
inserções, remoções e buscas em . As árvores AVL fornecem essa funcionalidade. A sigla AVL
corresponde às iniciais dos autores Adel'son-Vel'skii e Landis (S7WARCFITFR; MARKFNZON, 1994)
Uma árvore binária de busca é uma árvore AVL se, para qualquer nó de vale
a propriedade: .
Observação: é a altura da subárvore esquerda de e é a altura da subárvore direita.
Dizemos que um nó de uma árvore binária de busca está regulado se . Ou seja,
em uma árvore AVL, todos os nós estão regulados. A imagem a seguir mostra o exemplo da topologia de
uma árvore AVL.
Imagem 5 - Topologia de uma árvore AVL – exemplo.
As árvores completas são AVL. Esse fato deriva da própria definição das árvores completas. Além disso,
sabemos que as árvores completas com nós têm altura mínima, isto é, não existe topologia com nós
com altura inferior à da árvore completa . Ou seja, esse resultado garante que a altura
mínima de uma árvore AVL é proporcional a .
O(logn)
O(logn)
T r T ,
h (T er ) − h (T
d
r ) ≤ 1∣ ∣h (T er ) r h (T dr )r h (T er ) − h (T dr ) ≤ 1∣ ∣n n(h = 1 + ⌊logn⌋)logn
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 15/56
Entretanto, as árvores completas são o melhor caso, isto é, as árvores AVL de altura mínima. Vejamos a
árvore AVL da imagem 5. Essa árvore não é completa, uma vez que existe um nó na topologia que tem
subárvores vazias e este nó está no antepenúltimo nível da árvore. Assim, o teorema que versa sobre a
altura das árvores completas não garante que a árvore da imagem 5 tem altura proporcional a .
Vamos analisar a família de árvores AVL com pior desempenho, isto é, dada uma quantidade de nós, a
maior altura possível. Se essa família de árvores AVL tiver altura proporcional a , então garantiremos
que, no melhor e no pior caso, a altura de uma árvore AVL é proporcional a .
Vamos construir a família de árvores AVL com altura máxima e menor número de nós possível. A
construção será recursiva:
Para só existe uma solução, que é a árvore unitária.
Para , podemos construir a árvore com nós, a raiz e um dos filhos, à esquerda ou à direita,
para fins de análise não há diferença.
A imagem a seguir mostra essas topologias:
Imagem 6 - Árvores AVL com altura máxima e número mínimo de nós.
logn
n
logn
logn
h = 1
h = 2 n = 2
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 16/56
Para construir as árvores com altura e número mínimo de nós, comporemos as árvores da seguinte forma
recursiva:
1. Arbitra-se uma nova raiz.
2. Agregam-se a essa raiz como subárvore esquerda e direita as árvores de altura 1 e .
Assim, teremos as estruturas montadas da imagem a seguir:
Imagem 7 - Árvores AVL com altura e número mínimo de nós.
Provamos que a árvore tem altura e número mínimo de nós com a seguinteargumentação: em qualquer
uma da árvores a , qualquer folha que seja removida causa a destruição da propriedade AVL ou a
redução da altura da árvore, isto é, ou a árvore deixa de ser AVL ou perde a altura proposta. Sendo assim, as
topologias da imagem 7 representam as árvores AVL com altura e número mínimo de nós. Observe que
essas estruturas não são únicas. Dependendo de como fazemos a composição, alteramos a topologia, mas
não o número de nós.
Observe também que podemos encontrar o número mínimo de nós em função da altura com a seguinte
soma recursiva . Isto é: a cardinalidade da árvore com altura é igual à soma
da cardinalidade da árvore de altura com a cardinalidade da árvore de altura mais 1.
A tabela a seguir apresenta a evolução dessa série.
h
h− h − 2
h
h
T (1) T (5)
h
|Th| = |Th−1| + |Th−1| + 1 h
h − 1 h − 2
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 17/56
Tabela 1 - Comparação da sequência com (sequência de Fibonacci).
Da imagem, vemos que, para . Ou seja, o valor mínimo de para que possamos
construir uma árvore AVL com altura é . O termo geral da série de Fibonacci é:
Rotacione a tela. 
Sendo assim, é:
Th Fh
h > 2, |Th| = Fh+2 − 1 n
h n = Fh+2 − 1
Fn =
1
√5
[( 1 +
√5
2
)
n
− ( 1 −
√5
2
)
n
]
|Th| = n
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 18/56
Rotacione a tela. 
Isto é, a altura da árvore AVL é proporcional a . Ou seja, as árvores AVL são balanceadas. A família de
árvores AVL com essa propriedade é chamada de árvores de Fibonacci.
A conclusão desse estudo mostra que as melhores árvores AVL, isto é, as que têm
altura mínima são as árvores completas e têm altura proporcional a . As
piores árvores AVL, isto é, que têm altura máxima e número mínimo de nós, que são
as árvores de Fibonacci, também têm altura proporcional a .
De fato, não determinamos a função matemática para calcular a altura de uma árvore AVL com nós.
Entretanto, sabemos que essa função é limitada superiormente pela altura das árvores de Fibonacci e
inferiormente pela altura das árvores completas, ambas proporcionais a .
Sendo assim, a função que calcula a altura de uma árvore AVL com nós é "sanduichada" por duas funções
logarítmicas com bases diferentes, sendo assim, o comportamento da altura de uma árvore AVL qualquer é
proporcional a log , garantindo que as árvores AVL são balanceadas.
Árvores AVL: busca
Confira agora as operações de busca em árvores AVL e as operações de rotação.
n = |Th| =
1
√5
( 1 +
√5
2
)
h+2
− ( 1 −
√5
2
)
h+2
− 1
n =
1
√5
( 1 +
√5
2
)
h+2
−
1
√5
( 1 −
√5
2
)
h+2
− 1
n >
1
√5
( 1 +
√5
2
)
h+2
log 1+√5
2
n > h + 2 − log 1+√5
2
√5
h < log 1+√5
2
n + log 1+√5
2
√5 − 2
⎡
⎣
⎤
⎦
logn
logn
logn
n
logn
n
n
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 19/56
As operações básicas em uma árvore AVL geralmente envolvem os mesmos algoritmos de uma árvore de
busca binária desbalanceada. No entanto, para manter o balanceamento, operações extra são necessárias e
conhecidas como rotações de nós. Uma rotação simples ocorre quando um nó está desbalanceado e seu
filho estiver no mesmo sentido da inclinação.
Busca em árvores AVL
Uma árvore AVL é uma árvore binária de busca, portanto, não existe diferença entre o algoritmo da busca
em uma árvore binária de busca e o da busca em uma árvore AVL. O algoritmo é rigorosamente o mesmo.
Quando estudamos a busca nas árvores binárias de busca, concluímos que a complexidade era . Isso
acontece uma vez que o pior caso, isto é, as árvores com altura máxima e menor quantidade de nós são as
árvores zig-zag, que têm altura . Nas árvores AVL, as piores árvores, isto é, as árvores com altura máxima e
menor quantidade de nós, são as árvores de Fibonacci que têm altura proporcional a . Sendo assim, a
complexidade do algoritmo da busca, quando aplicado em árvores AVL, é .
Atenção!
O que define a complexidade da busca é a altura da árvore, não o algoritmo propriamente dito. Isso se deve
ao fato de que o algoritmo de busca tem como operação fundamental a comparação, e que esse algoritmo
executa uma comparação por nível na árvore e, ainda, no pior caso, a chave encontrada está no último nível
da árvore, que é igual à altura da árvore.
Inserção em árvores AVL
Confira agora as operações de inserção em árvores AVL e as operações de rotação.
O(n)
n
logn
O(logn)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 20/56
Seja uma árvore AVL na qual vamos inserir uma nova chave. Como uma árvore AVL é uma árvore binária
de busca, então o funcionamento do algoritmo de inserção, isto é, onde a nova chave deve ser inserida, é
definido da mesma forma que já estudamos. A busca determina a posição, que é a subárvore vazia onde a
busca deveria prosseguir para encontrar a chave que desejamos inserir.
Agora, vamos nos concentrar em verificar o que pode acontecer com a propriedade fundamental das
árvores AVL, isto é, a regulagem dos nós. Vamos recordar que, em uma árvore AVL, deve valer para todos os
nós . Quando isso ocorre, dizemos que o nó está regulado. Para fins de análise,
vamos considerar a árvore da imagem:
Imagem 8 - Árvore AVL.
Na árvore da imagem 8, se inserirmos uma nova chave, a chave “10”, por exemplo, não haverá a perda da
regulagem dos nós da árvore. A árvore resultante continuará a ser uma árvore AVL (imagem 9). Veja:
T
h (T er ) − h (T dr ) ≤ 1∣ ∣
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 21/56
Imagem 9 - Árvore resultante após inserção da chave “10”.
Contudo, se, ao invés de inserirmos a chave “10”, inserirmos a chave “30”, a árvore resultante deixa de ser
AVL. Na imagem a seguir, temos a árvore resultante e, nessa árvore, temos que o nó “20” está regulado,
porém o nó “15” está desregulado. A altura de sua subárvore esquerda é 0 e sua subárvore direita tem altura
2 (imagem 10).
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 22/56
Imagem 10 - Árvore resultante após a inserção da chave “30” – não é AVL.
Observe que, na árvore da imagem 10, o nó “15” é o nó mais profundo desregulado. O nó mais profundo é
aquele de maior nível, ou seja, “15” é o nó de maior nível na árvore desregulado. Vamos concentrar a análise
nesse nó, seja “u” esse nó. A situação que vamos analisar é a da imagem 11. Veja:
Imagem 11 - Inserção de uma chave na árvore AVL.x > u
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 23/56
Destacando a raiz de T2, temos as seguintes possíveis situações (imagem 12) antes da inserção da chave 
.
Imagem 12 - Árvore antes da inserção de .
Observe que o único cenário viável é o da imagem 12 (A). Ao inserir na árvore de A, T2 ou T3 podem
crescer e esse crescimento não desregula o nó " ". Nas árvores de B e C, a inserção de " " na árvore
desregularia " ", o que contraria nossa premissa de que " " é o nó mais profundo desregulado, ou não
desregula nó algum, o que também contraria nossa premissa.
Análise semelhante deve ser feita para o caso de inserirmos uma chave . Nesse caso, pode-se
concluir que o único cenário de estudo é o da imagem 13. Chamaremos de caso 1 o correspondente à
imagem 12 (A) e caso 2 o da imagem 13.
Imagem 13 - Caso 2 - Inserção de uma nova chave menor que .
Voltando à análise do caso 1, veremos que esse caso pode ser dividido em dois subcasos:
O subcaso 1.a, que corresponde à inserção de uma chave e .
x
x
x
v x
v u
y < u
u
x > u x > v
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 24/56
O subcaso 1.b, que corresponde à inserção de uma chave tal que .
Vejamos o subcaso 1.a:
Imagem 14 - Inserção de chave e ajusteda estrutura.
Na imagem 14, temos a ilustração do subcaso 1a. Suponhamos que, ao inserir a chave " ", o ramo T3 da
árvore cresça. Definindo balanço de , temos que o nó " " continua
regulado , conforme nossa hipótese de análise, entretanto " " está desregulado 
). Após a inserção, a subárvore esquerda de tem altura e a subárvore direita tem altura .
A operação que reajusta a estrutura é a rotação para a esquerda. Trata-se de transformar o nó " " como
raiz da subárvore, fazer " " seu filho esquerdo , lembre-se de que se trata de uma árvore binária de
busca) e fazer T1 subárvore esquerda de " " (os nós de T1 satisfazem a propriedade ), T2
subárvore direita de "u" (os nós de T2 satisfazem a propriedade ), e T3 subárvore direita de 
(os nós de T3 satisfazem a propriedade ).
Atenção!
Após a rotação, a árvore resultante tem mesma altura que a árvore original. Isso garante que, para os
ascendentes de , se houver, e porventura existirem e tiverem se tornado desregulados após a inserção, a
aplicação da rotação iria ajustá-los automaticamente.
Vejamos essa situação na árvore da imagem 15:
Imagem 15 - Inserção da chave “90”.
Na imagem 15, inserimos a chave “90” na estrutura. O resultado da inserção é que o nó “60” é o nó mais
profundo desregulado. Entretanto, os nós “50” e “30” também estão desregulados. Conforme vimos,
aplicamos a rotação para a esquerda no nó “60”, que resulta na estrutura com as chaves “60”, “80” e “90”
x u < x < v
x > v
x
x como   bal(x) = h (T dx ) − h (T ex ) v
(bal(v) = 1) u (bal(u) = 2
u h h + 2
v
u (u < v
u k k < u
k u < k < v v
k k > v
u

24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 25/56
com altura 2. A rotação regula a estrutura e, como a subárvore resultante tem altura 2, assim como o ramo
original, os nós “50” e “30” voltam a estar regulados automaticamente.
O caso 2a é análogo ao caso 1a. Após a inserção de uma chave na árvore da imagem 16 (A),
podemos ter como resultado a árvore da imagem 16 (B) e, após a aplicação da rotação para direita (imagem
16(C)), a árvore volta a estar regulada.
Todas as observações feitas para o caso 1a são análogas ao caso 2a, veja:
Imagem 16 - Caso 2a, inserção de chave .
Vejamos agora a análise do caso 1.b, isto é, a inserção de uma chave tal que . A imagem 17
ilustra o caso 1.b:
Imagem 17 - Inserindo .
Destacando a raiz de T2 antes da inserção da nova chave, podemos ter as configurações da imagem 18.
Veja as implicações e possibilidades dessas configurações:
Imagem 18 - Análise do subcaso 1.b
y < k
y < k
x u < x < v
u < x < v
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 26/56
No caso da imagem 18 (A), caso a nova chave seja maior ou menor que , pode implicar no crescimento do
ramo direito ou esquerdo da árvore com raiz . No caso da imagem 18 (A), T2 ou T3. Caso essas árvores
não cresçam, isto é, mantenham sua altura original, nada precisamos fazer. Contudo, se T2 ou T3 crescer
devido à inclusão, teremos regulado, regulado e desregulado, coerente com o que assumimos
inicialmente. Então, o cenário da figura 18(A) é um dos focos do nosso estudo.
No caso da imagem 18 (B) e (C), observe que os casos são semelhantes, divergem somente no ramo de
maior altura esquerdo (imagem 18 (B)) e direito (imagem 18(C)). Analisando a árvore de B, se inserirmos
uma nova chave no ramo direito (T3), poderá ocorrer o crescimento de T3, contudo, se T3 crescer, a árvore
de raiz tem balanço zero, não repercutindo nos nós e . Entretanto, se T2 crescer, isto é, passar a ter
altura , o nó passará a estar desregulado, o que fere o que supomos inicialmente, isto é, que é o nó
mais profundo desregulado. Assim, o único cenário plausível para análise é o de A.
Vejamos então o que pode ocorrer quando inserimos uma nova chave na subárvore de raiz da imagem 18
(A).
Imagem 19 - Rotação dupla para a esquerda.
A imagem 19 ilustra a situação, observe que é o nó desregulado. A rotação dupla para a esquerda resolve
a regulagem de . Nessa rotação, é posto como raiz da subárvore. Como é menor que é inserido
como filho esquerdo de e como filho direito de ). Observe que:
Os nós de T1 são menores que .
Os nós de T2 obedecem à propriedade .< /li>
Os nós de T3 obedecem à propriedade .< /li>
Os nós de obedecem .
Vejamos um exemplo:
w
w
w v u
w v u
h w u
w
u
u w u w,u
w v w(v > w
u
z u < z < w
z w < z < v
z T4 z > v
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 27/56
Imagem 20 - Inserção da chave 65.
Observe que, na árvore do exemplo, após a inserção da chave 65, os nós 50 e 70 permanecem regulados e
30 desregulado. Após a inserção dupla para a esquerda, todos os nós ficam regulados.
Após a aplicação da rotação dupla para a esquerda, a árvore resultante tem a
mesma altura que a árvore original, antes da inserção da nova chave. Essa
propriedade garante que, regulando o nó , todos os ancestrais de ficam
automaticamente regulados, como ocorreu no Caso 1a.
A análise do caso 2b é análoga à do caso 1b. A imagem 21 mostra como identificar e aplicar a rotação
dupla para a direita.
Imagem 21 - Caso 2b - rotação dupla para direita
Para concluir a análise do algoritmo de inclusão de nós na árvore AVL, resta determinar como é feita a
identificação das rotaçőes pelo algoritmo. Observe que, na análise, nos referimos à diferença de altura entre
o ramo direito e esquerdo. Essa diferença foi chamada de balanço do nó. Contudo, se calcularmos a altura
das subárvores esquerda e direita de um nó para determinar o balanço, não será possível manter a
complexidade de da operação de inserção, uma vez que, para calcular a altura de uma árvore, é
necessário executar um algoritmo com complexidade .
u u
O(logn)
O(n)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 28/56
A solução para esse problema é armazenar o balanço do nó junto com a chave. Conforme definido,
. O crescimento do módulo do balanço de uma chave indica que o ramo
cresceu, sendo necessário atualizar o balanço incrementando-o, caso o ramo que tenha crescido seja o
direito ou decrementando-o, caso o ramo que tenha crescido seja o esquerdo.
A identificação do caso ocorre quando um nó tem balanço 2 indicando o caso 1 ou balanço -2 indicando o
caso 2. O subcaso é identificado pelo balanço do filho direito:
No caso 1, se o balanço do filho direito for 1, temos o subcaso 1a.
Se o balanço do filho direito for -1, temos o subcaso 1b.
Analogamente, o balanço do filho esquerdo identifica o subcaso do caso 2.
Caso o balanço do filho esquerdo seja -1, temos o caso 2a.
Caso seja 1, temos o subcaso 2b.
O pseudocódigo do algoritmo será omitido, entretanto, pode ser facilmente encontrado na internet.
Remoção em árvores AVL
Confira agora a operação de remoção em árvores AVL.
A análise da remoção é muito semelhante à da inserção de novos nós na árvore. Toda a análise da inserção
baseia-se no estudo do crescimento de um ramo da árvore devido ao novo nó contendo a nova chave.
Além disso, a árvore AVL é uma árvore binária de busca, a remoção recai nos três subcasos estudados.
Como exemplo, vejamos a remoção de um nó de T3 que resulta no encurtamento de T3 (imagem 22).
bal(x) = h (T dx ) − h (T
e
x )
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 29/56
Imagem 22 - Remoção de uma chave .
O ajuste aplicado na estrutura foi o do caso 2a. Porém, observe que há uma sutil diferença em relação ao
balanço de , filho esquerdo de . No exemplo, tem balanço 0 e resultou na rotação para a direita. Na
inclusão, a rotação para a direita ocorria quando o balanço de era igual a -1.
Sendo assim, a aplicação da rotação para a direita ocorre quando e o balanço do filho
esquerdo de , no caso do exemplo , é 0 ou , isto é, ou (imagem 23).
Imagem23 - Aplicação da rotação do Caso 2a, possibilidade 2.
A imagem 23 mostra que, na aplicação da rotação na remoção, existe a possibilidade da estrutura
resultante ter seu tamanho reduzido de uma unidade. Nesse caso, caso haja ancestrais de na árvore
original, isto é, antes da remoção de , o efeito da remoção pode propagar-se para os ancestrais de .
Essa situação ocorre, por exemplo, na árvore de Fibonacci. A imagem 24 mostra um exemplo:
Imagem 24 - Árvore de Fibonacci.
y > v
k v k
k
bal(v) = −2
v k −2 bal(k) = 0 bal(k) = −1
v
y v
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 30/56
Ao removermos o nó 10, temos que o bal(11)=2 e bal(12)=1, que corresponde ao caso 1a. Aplicando a
rotação para a esquerda, temos a configuração da imagem 25:
Imagem 25 - Resultado da aplicação da rotação para a esquerda no nó 11.
Observe que, após a rotação, o nó “14” tem balanço 2 e o nó “17” tem balanço 1, também o caso 1a.
Aplicando a rotação, temos a árvore da imagem 26.
Imagem 26 - Resultado da aplicação da rotação para a esquerda no nó “14”.
Após a rotação, o nó “22” tem balanço 2 e o nó “30” tem balanço 1, também caso 1a. Aplicando a rotação
para a esquerda, no nó “22” temos a árvore da imagem 27:
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 31/56
Imagem 27 - Resultado da aplicação da rotação para a esquerda no nó “22”.
Observe que as rotações em sequência reestruturam a propriedade AVL após a remoção. A árvore de
Fibonacci é o pior caso da remoção. Conforme visto, nas árvores de Fibonacci é necessário realizar todas as
rotações do pai do nó removido; no caso do exemplo da imagem anterior, o nó “11” até a raiz.
Cada rotação tem complexidade da , assim, a aplicação da rotação no caminho da folha removida até
a raiz não tem impacto na complexidade da remoção que é .
Concluindo, o algoritmo de remoção recai nos subcasos estudados e, após a aplicação desses subcasos, o
balanço do nó pai do nó removido deve ser atualizado e aplicadas as rotações conforme os casos
estudados na inserção caso 1, subcaso 1a e 1b ou caso 2, subcaso 2a e 2b.
Na remoção, os subcasos 1a e 2a ocorrem quando bal(v) =2 e do filho direito é 1 ou 0 ou bal(v) = -2 ou o
balanço do filho esquerdo é -1 ou 0, respectivamente. Os subcasos 1b e 2b são identificados da mesma
forma que na inclusão.
Estudo da complexidade da árvore AVL
Confira agora a complexidade da busca, inserção e remoção de chaves em uma árvore AVL.
Vimos que as árvores AVL são balanceadas, isto é, toda árvore AVL tem altura proporcional a . Desse
fato ocorre que a complexidade da busca é . Foi visto que a complexidade da busca é proporcional
à altura da árvore, no caso da árvore , e que toda árvore AVL é uma árvore binária de busca. Sendo
assim, aplica-se o mesmo algoritmo estudado.
A inclusão de uma nova chave na árvore AVL também tem complexidade , isso decorre do fato de
que a inclusão é consequência direta da busca e a busca executa em . No pior caso, a inclusão de
uma nova chave pode resultar em uma rotação, que é uma operação simples, que executa em . Não é
impactante na complexidade, mas vimos que, após a aplicação da rotação na inclusão, o ramo alterado pela
inclusão preserva sua altura original, isto é, antes da inserção da nova chave, fazendo com que novas
rotações nos ancestrais sejam desnecessárias.
O(1)
O(logn)
logn
O(logn)
logn
O(logn)
O(logn)
O(1)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 32/56
Finalmente, o pior caso da remoção é a remoção da folha menos profunda de uma árvore de Fibonacci.
Nesse caso, realizamos todas as rotações da folha removida até a raiz. Contudo, cada rotação tem
complexidade da e são realizadas rotações até regular toda a árvore. Assim, as árvores AVL
fornecem algoritmos totalmente dinâmicos capazes de realizar busca, inserção e remoção em .
Falta pouco para atingir seus objetivos.
Vamos praticar alguns conceitos?
Questão 1
Marque a opção correta relativa à inserção de uma nova chave em uma árvore AVL.
O(1) O(logn)
O(logn)
A Toda inserção numa árvore AVL implica a aplicação de uma rotação.
B
Quando há necessidade de aplicar uma rotação para preservar a propriedade AVL, essa
rotação deve ser aplicada no nó de menor nível que se encontra desregulado.
C
Podemos sempre afirmar que, após a aplicação de uma rotação, a altura da árvore AVL
é a igual à altura da árvore antes da inserção da nova chave.
D A operação de rotação tem complexidade de .O(logn)
E
A operação de rotação tem complexidade de , porém, isso não impacta na
complexidade da inserção ou da remoção.
O(n)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 33/56
Parabéns! A alternativa C está correta.
Após a rotação, a altura da subárvore que sofreu a alteração é preservada mesmo após sofrer rotação.
Ou seja, isso corresponde à altura da árvore original antes da inserção da nova chave.
Questão 2
Marque a opção correta sobre a remoção de um nó de uma árvore AVL.
Parabéns! A alternativa A está correta.
Uma das formas mais complicadas da remoção de um nó de uma árvore AVL é quando se remove a
folha menos profunda de uma árvore de Fibonacci. Nesse caso, precisamos fazer todas as rotações, do
pai do nó removido até a raiz.
A
O pior caso da remoção de um nó de uma árvore AVL é a remoção da folha menos
profunda de uma árvore de Fibonacci. Nesse caso, temos que fazer todas as rotações,
do pai do nó removido até a raiz.
B Assim como na inserção, na remoção, somente uma rotação regula a árvore AVL.
C Na remoção, sempre é necessário aplicar rotações do pai do nó removido até a raiz.
D
Não é possível garantir a complexidade computacional de na operação de
remoção de um nó de uma árvore AVL, uma vez que pode ser necessário fazer diversas
operações de rotação. Mais especificamente, do pai do nó removido até a raiz da árvore.
O(logn)
E Infelizmente, a operação de remoção em uma árvore AVL tem complexidade de .O(n)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 34/56
3 - Árvores B
Ao �nal deste módulo, você será capaz de reconhecer os principais conceitos de árvores B,
suas principais vantagens e operações.
Árvores B: principais de�nições
Confira agora o conceito de árvore B e por que elas são balanceadas.
Como visto, as árvores binárias armazenam em um nó um único registro e possuem até dois nós (esquerdo
e direito) como filhos. Além disso, vimos que a árvore binária de busca tem como característica armazenar
na subárvore esquerda de um nó apenas elementos menores do que ele e, na direita, elementos maiores.
Podemos ampliar o conceito de armazenamento ordenado da árvore binária de busca para maiores ordens,
ou seja, uma árvore de busca com mais de dois filhos por nó.
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 35/56
Outra característica que pode ser adicionada é armazenar mais de um elemento (registro) por nó. Observe a
seguir:
Imagem 28 - A árvore B é um exemplo de árvore de busca de dados multidirecional.
O conceito é importante porque amplia as possibilidades de armazenamento além de manter uma árvore
com profundidade menor do que uma árvore binária de busca ou árvore AVL.
“[...] utilizando o recurso de manter mais de uma chave em cada nó da estrutura,
proporciona uma organização [...] tal que as operações mencionadas (busca, inserção
e remoção) são executadas rapidamente.
(SZWARCFITER; MARKENZON, 1994, p. 160)
As árvores com essas novas características citadas são conhecidas como árvore de busca multidirecional e
como árvores B. A árvore B foi proposta por Rudolf Bayer. Não se sabe de onde vem o B do nome da árvore.
Uma das hipóteses é que a letra B é a primeira letra do seu sobrenome, Bayer.
As árvores B são muito utilizadascomo forma de armazenamento em memória secundária (como HDs e
outros dispositivos de armazenamento secundário com acesso direto). As árvores B se destinam a
armazenar grandes tabelas, por isso diversos sistemas comerciais de bancos de dados, por exemplo,
utilizam esse tipo de árvore (SZWARCFITER; MARKENZON, 1994).
A árvore B é uma árvore balanceada em que o número de nós acessados nas operações de
busca/inserção/remoção é muito pequeno se comparado às outras árvores já estudadas.
A árvore B garante que as folhas se encontrem todas em um mesmo nível,
independentemente da ordem em que os dados serão inseridos.
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 36/56
Em outras palavras, Preiss (2000) define uma árvore B de ordem como uma árvore de busca com as
seguintes propriedades:
A raiz tem no mínimo duas e no máximo subárvores.
Cada um dos nós internos (diferentes da raiz) tem entre e subárvores e entre e 
elementos.
Todos os nós folhas estão no mesmo nível.
Imagem 29 - Árvore B.
Na imagem 29, temos um exemplo de árvore B de ordem 4. Observe que essa árvore obedece à definição:
A raiz possui duas subárvores (quantidade mínima).
Todas as folhas estão em um mesmo nível.
Todos os nós internos (que não são folhas e são diferentes da raiz) possuem quatro subárvores, ou seja,
entre e .
Sabemos que em uma árvore de ordem (em que é um número natural maior do que um), a árvore B
pode ter filhos. Além disso, é balanceada. Nesse caso, precisamos ter algoritmos que garantam essa
característica à árvore. Um elemento inserido em uma árvore B é sempre colocado em uma folha. Assim
como nas outras árvores e, de acordo com a necessidade, as redistribuições são feitas a fim de garantir que
a árvore fique sempre balanceada.
A árvore B generaliza as árvores binárias de busca, mais especificamente, a árvore AVL.
Árvores B: busca
n
⌈n/2⌉ n ⌈n/2⌉ − 1 n − 1
⌈n/2⌉ n
n n
n
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 37/56
Confira agora a operação de busca em árvores B.
A busca realizada em uma árvore B é semelhante à busca em uma árvore AVL e, consequentemente, a de
uma árvore binária de busca. Como é possível armazenar mais de um elemento em um nó, é necessário
adicionar testes a serem realizados em cada nó para indicar qual o próximo passo.
Na imagem 30, temos um exemplo de busca em árvore B. Considere a busca da chave 75. A primeira
comparação a ser feita é com a raiz. Como o elemento 75 é maior que o 60, está à direita de 60, segue a
busca para o nó que armazena os elementos 72 e 81. Nesse nó, são realizadas novas comparações a fim de
determinarmos para qual filho a busca deverá seguir. Como o elemento é maior do que 72 e menor do que
81, a busca segue para o filho localizado entre 72 e 81. O caminho percorrido nessa busca está destacado
na imagem 30:
Imagem 30 - Exemplo de busca em uma árvore B.
A análise de complexidade está relacionada ao número de acesso aos nós e pela busca linear
em cada nó considerado na busca ( em cada nó). Portanto, .
Árvores B: inserção
Confira agora a operação de inserção de uma nova chave em uma árvore B.
(O(logn))
t O(t logn)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 38/56
Na inserção de chaves na árvore B, devemos nos preocupar com a definição quanto à ordem da árvore,
porque um nó interno (que é diferente da raiz) deve possuir entre e subárvores.
1. O primeiro passo da inserção é buscarmos a folha na qual será inserido o novo elemento.
2. No segundo passo, devemos verificar se a folha está ou não completa e, se não estiver completa, basta
incluir o elemento em sua posição correta dentro do nó.
3. Se o nó estiver cheio, devemos proceder ao segundo passo de forma diferente.
3.1. Se o nó estiver cheio, ao invés de criar um nó com apenas esse novo elemento, devemos dividir o nó
cheio. Assim, se algum nó ficar com ordem maior do que n, o nó deve ser dividido. Para isso, o valor
central do nó que será dividido sobe para a posição do pai, repetindo recursivamente por toda árvore
até a raiz (se necessário).
4. Se acontecer da raiz estourar, um novo nó raiz será criado e poderá ter somente um elemento, se
necessário.
É importante acrescentar que, por proceder à inserção da forma descrita anteriormente, é que se garante
que todas as folhas sempre estarão em um mesmo nível. Vamos acompanhar esses passos de forma
figurada.
Seja a árvore B retratada na imagem a seguir:
Imagem 31 - Árvore B para inserção.
A partir da árvore B inicial da imagem 31, devemos proceder com as inserções dos seguintes elementos,
respectivamente: B, N, F. A inserção do elemento B resulta na árvore da imagem 32:
⌈n/2⌉ n
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 39/56
Imagem 32 - Inserção do elemento B na árvore da imagem 31.
Na sequência, deve ser inserido o elemento N. Contudo, o nó em que deve ser inserido N já está cheio.
Assim, devemos dividir o nó em dois e subir em um nível o elemento central. Lembre-se de que esse
processo repete recursivamente até a raiz. A árvore resultante após a inserção de N é apresentada na
imagem 33:
Imagem 33 - Inserção do elemento N na árvore B da imagem 32. Observe que, nesse passo, há necessidade de subida de níveis para
“comportar” o novo elemento.
O último elemento a ser inserido é o F. Mais uma vez, o nó em que deveria ser inserido o novo elemento,
nesse caso F, já está cheio. Procedemos à divisão do nó em dois e subimos o elemento central. A imagem a
seguir apresenta o resultado final das inserções da árvore B:
Imagem 34 - Inserção do elemento F na árvore B da imagem 32. Novamente, há necessidade de subida de níveis para “comportar” o novo
elemento.
A análise de complexidade da inserção na árvore B está relacionada ao número de acesso aos nós
 e pela busca linear em cada nó ( em cada nó) para encontrar o local a ser inserido o elemento.
Portanto, .
Árvores B: remoção
Confira agora a operação de remoção de uma chave em uma árvore B.
(O(logn)) t
O(t logn)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 40/56
Para a remoção de um elemento na árvore B, existem dois casos que devem ser observados:
O elemento a ser inserido estar ou não em uma folha.
Ao remover um elemento, um nó não atingir a quantidade mínima de elementos que devem estar
armazenados no nó, de acordo com a ordem da árvore.
O algoritmo de remoção ficará da seguinte forma:
1. Aplicar o procedimento de busca, verificando a existência do elemento a ser removido na árvore. 1
2. Se o elemento a ser removido se encontrar em uma folha, o elemento é simplesmente retirado.
3. Se o elemento a ser removido não se encontrar em uma folha (localizar-se em um nó interno), é
substituído pelo elemento imediatamente maior ou imediatamente menor. Observe que o elemento
imediatamente maior ou menor pertence, por definição, a uma folha. Com isso, reduzimos para o caso de
remover o elemento da folha.
4. Se o nó continuar com o número mínimo de elementos, fim.
5. Se não, a folha obrigatoriamente tem uma chave a menos que o mínimo. Assim, verifique os nós irmãos
(imediatamente à esquerda e direita):
5.1. Se um dos nós irmãos tiver mais do que o número mínimo de elementos, aplique redistribuição.
Lembre-se de que um nó interno deve possuir um mínimo de n/2 - 1 elementos. A redistribuição
consiste em concatenar o nó folha do elemento removido com o do irmão adjacente, o que resulta
em um nó maior do que o aceito pela definição. Em seguida, efetue a divisão do nó em dois e suba
em um nível o elemento central, igual à divisão da inserção.
5.2. Se não, concatene o nó com um dos irmãos e o elemento separador do pai.
6. Se ocorrer concatenação, volte ao passo 4 com o nó pai, porque remover um elemento do pai pode
acarretar de o pai nãoter mais o número mínimo de elementos.
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 41/56
Proceder à remoção da forma descrita anteriormente garante que todas as folhas sempre estarão em um
mesmo nível. Vamos acompanhar esses passos de forma figurada.
Veja a árvore B retratada na imagem 35:
Imagem 35 - Árvore B para remoção.
A partir da árvore B inicial da imagem 35, devemos proceder às remoções dos seguintes elementos
respectivamente: J e L.
No passo 1 da remoção, deve-se buscar o elemento a ser removido da árvore. É identificado o nó que
contém os elementos H e J.
Como o elemento se encontra em uma folha, remova o elemento (passo 2).
Já que o nó não continua com o número mínimo de elementos (passo 5), deve-se executar o passo 5.1
(redistribuição).
Faça a redistribuição com o nó irmão da direita. Após isso, a remoção é realizada.
O resultado da remoção é apresentado na imagem a seguir:
Imagem 36 - Resultado da remoção do elemento J. Observe que houve um reposicionamento dos elementos na raiz.
Vamos remover o elemento L:
Como passo 1 da remoção, deve-se buscar o elemento a ser removido da árvore. Assim, é identificado o
nó que contém os elementos H e L.
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 42/56
Como o elemento se encontra em uma folha, remova o elemento (passo 2).
Uma vez que o nó não continua com o número mínimo de elementos (passo 5), execute o passo 5.2
(concatenação).
A concatenação é feita com o pai e o irmão direito, o que resulta em um nó com os elementos H, M, P, T.
Execute o passo 6 voltando ao passo 4 para o pai (recursão, nó com os elementos F, U). Como o nó pai
continua obedecendo à definição do número mínimo de elementos, a remoção é finalizada.
O resultado é apresentado na imagem 37:
Imagem 37 - Resultado da remoção do elemento L. Observe que houve uma concatenação dos elementos de dois (2) nós folhas.
Cada passo relatado na remoção de um elemento possui uma complexidade envolvida. Porém, quase
sempre é concentrada na situação de pior caso. A remoção na árvore B também está relacionada ao
número de acesso aos nós e pela busca linear em cada nó ( em cada nó) para encontrar o
local a ser inserido o elemento. Portanto, .
Falta pouco para atingir seus objetivos.
Vamos praticar alguns conceitos?
Questão 1
As árvores B são uma generalização das árvores binárias. Seus nós (chamados de página nas árvores
B) podem carregar mais de uma chave e essa característica é conveniente, uma vez que
(O(logn)) t
O(t logn)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 43/56
Parabéns! A alternativa D está correta.
A opção "A" está errada, uma vez que a complexidade das operações citadas é O(log n). " B" e "C" estão
erradas, pois as árvores B podem ser representadas tanto em memória principal quanto em secundária.
"D" está correta pela característica da forma com que os blocos são alocados em memória secundária,
normalmente em múltiplos de 512 bytes, sendo as páginas mais bem acomodadas nos blocos. "E"
também está incorreta, uma vez que as árvores binárias têm grande desperdício de memória caso
sejam representadas em memória secundária.
Questão 2
Em uma árvore B, temos que:
(i) Cada nó contém no mínimo m registros (m+1 descendentes) e no máximo 2m registros (e 2m+1
descendentes), exceto o nó raiz, que pode conter entre 1 e 2m registros.
(ii) Todos os nós folhas aparecem no mesmo nível.
Sobre árvores B, é correto afirmar:
A faz com que as operações de busca, inserção e remoção ocorram em .O(1)
B faz com que as árvores B possam ser representadas somente em memória principal.
C faz com que as árvores B possam ser representadas somente em memória secundária.
D
as árvores B podem ser representadas tanto em memória principal quanto em memória
secundária, porém, a organização em páginas viabiliza o mínimo desperdício em
alocação de espaço em memória secundária.
E
as árvores binárias de busca balanceadas são totalmente equivalentes às árvores B,
independentemente do ambiente de memória no qual estão representadas.
A
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 44/56
Parabéns! A alternativa A está correta.
Para a inserção de um registro, é necessário inserir um nó com 2m registros e ao mesmo tempo ocorre
o particionamento de nós em uma árvore B.
O particionamento de nós em uma árvore B ocorre quando um registro precisa ser
inserido em um nó com 2m registros.
B
O particionamento de nós em uma árvore B ocorre quando um registro precisa ser
inserido em um nó com menos de 2m registros.
C
O particionamento de nós em uma árvore B ocorre quando a chave do registro a ser
inserido contém um valor (conteúdo) intermediário entre os valores das chaves dos
registros contidos no mesmo nó.
D O particionamento de nós ocorre quando é necessário diminuir a altura da árvore.
E
Em uma árvore B, aumenta em um nível sua altura, toda vez que ocorre o
particionamento de um nó.
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 45/56
4 - Frameworks em Python para árvores de busca
balanceada
Ao �nal deste módulo, você será capaz de identi�car os principais módulos e bibliotecas em
Python para implementação de árvores de busca binária e AVL.
Módulos Python para árvores balanceadas
Confira agora as principais bibliotecas e suas características.
A linguagem Python está emergindo como uma das linguagens de crescimento mais rápido no mercado. É o
maior concorrente do JavaScript, especialmente por causa da onda crescente de IA (Inteligência Artificial).
O Python foi desenvolvido por Guido van Rossum em 1991 e possui características vantajosas, como:

Simplicidade

Versatilidade

Recursos de portabilidade
Os frameworks são coleções de módulos de softwares e ferramentas que ajudam o programador no
momento de construir seus projetos. Eles proporcionam uma ajuda fundamental aos profissionais, porque
contêm embasamentos teóricos e práticos que otimizam o tempo, evitam erros comuns e repetitivos e,
portanto, deixam o processo mais fluido e simplificado.
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 46/56
Existem diversos tipos de framework em Python, que veremos a seguir, mas as outras linguagens de
programação também contam com seus próprios frameworks. Essa não é uma ferramenta exclusiva do
Python.
Alguns módulos em Python para árvores balanceadas ainda são pouco explorados. Vejamos alguns
exemplos:
Trata-se de um pacote em C composto de um conjunto independente de rotinas dedicadas à
manipulação de árvores AVL (arquivos avl.c, avl.h) e de um módulo de extensão para Python que se
baseia nele (arquivo avlmodule.c) para fornecer objetos do tipo 'avl_tree' em Python, que pode se
comportar como contêineres classificados ou listas sequenciais. Apesar da existência desse pacote
de módulos, ele ainda é pouco explorado, existindo poucos exemplos na literatura de sua
implementação.
Trata-se, sob a licença GPL 3, de um pacote composto de conjunto de rotinas para manutenção de
árvores balanceadas rubro-negras. Ainda é um pacote com poucos módulos desenvolvidos e que
carece de atualização (a última é de 2008).
Módulo bisect
Confira agora as principais funcionalidades da biblioteca bissect com um exemplo.
pyavl 
rbtree 
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 47/56
A pesquisa binária é uma técnica usada para pesquisar elementos em uma lista classificada. O módulo
bisect fornece suporte para manter uma lista em ordem de classificação sem ter que classificar a lista após
cada inserção. Para listas grandes de itens com operações de comparação custosas computacionalmente,
isso pode ser uma melhoria em relação à abordagemmais comum na inserção dos dados.
É possível usar o módulo bisect para simular o uso da classe TreeSet, disponível em Java, inclusive evitando
elementos duplicados nas árvores.
A classe TreeSet classifica os elementos em ordem crescente. É uma coleção para armazenar um conjunto
de elementos únicos (objetos) de acordo com sua ordem natural. Ele cria uma coleção classificada que usa
uma estrutura de árvore para o armazenamento de elementos ou objetos. Ou seja, os elementos são
mantidos em ordem ascendente no conjunto de árvores.
Dica
Para usar os recursos do bisect, é necessário instalar seus pacotes. Use o pip install bisect.
No algoritmo a seguir, utilizamos os recursos do bisect para implementar as operações básicas de uma
árvore binária:
Python 
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 48/56
Implementação de uma estrutura árvore usando o módulo bisect para auxiliar nas operações básicas de inserção dos nós.
Ainda dentro da classe Arvore, podemos inserir um iterator de objetos (__iter()__). Você pode inserir outros
métodos interessantes para complementar a sua classe Arvore.
Python 
Método de iteração e método de modo de exibição (__str()__).
Para fazer uso das funcionalidades da nossa classe Arvore, no script principal invocamos os métodos
implementados dentro da classe.
No algoritmo a seguir, temos implementadas as operações de busca, inserção e remoção em uma árvore
binária:
1. Na operação de busca, usamos o operador in do Python, que verifica se o elemento está na árvore.
2. Na operação de inserção, usamos os métodos addElemento() e addElementos() para inserir um (1) ou
mais elementos, respectivamente, na árvore.
2.1. addElemento(var): inserindo um (1) elemento (parâmetro).
2.2. addElementos(): inserindo vários elementos (enviando uma lista de elementos por parâmetro).
3. Na operação de remoção, usamos o método removeElementos() para remover algum item (enviado por
parâmetro) da árvore.
Python 
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 49/56
Script principal do programa com as principais funcionalidades de uma árvore.
Módulo sbbst
Confira agora, por meio de um exemplo de implementação, o uso das principais funcionalidades da
biblioteca sbbst.
Uma árvore binária de busca autobalanceada é uma estrutura de dados avançada, que otimiza os tempos de
inserção, deleção e busca. Um módulo Python que implementa e executa essas atividades eficientemente é
a sbbst (do inglês self-balancing binary search tree).
Dica
Use !pip install sbbst para instalar o módulo.
O módulo sbbst possui espaço ) na memória, em que equivale à quantidade de nós de uma árvore.
Os tempos de complexidade respectivos e funções são:
O(n n
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 50/56
Tempo de complexidade Funções de classe Ação
sbbst.getSize() Tamanho da árvore
sbbst.getHeightTree() Altura da árvore
sbbst.search(x) Busca na árvore
sbbst.insert(x) Inserção na árvore
sbbst.delete(x) Deletar x da árvore
sbbst.getMinVal() Valor mínimo
sbbst.getMaxVal() Valor máximo
sbbst.kthsmallest(k) k-ésimo valor mínimo
sbbst.kthlargest(k) k-ésimo valor máximo
str(sbbst) Visualizar árvore
Tabela 2 - Método de iteração e método de modo de exibição.
Adaptada da documentação contida em Pypi.org (2022).
Exemplo de implementação com sbbst
A seguir, teremos um exemplo de implementação de árvore AVL usando o módulo sbbst. No algoritmo a
seguir, na linha 1, invocamos o import from sbbst import sbbst. Veja:
Python 
O(1)
O(1)
O(logn)
O(logn)
O(logn)
O(logn)
O(logn)
O(k + logn)
O(k + logn)
O(n)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 51/56
Método de iteração e método de modo de exibição.
Na linha 3 até a linha 6 do algoritmo anterior, temos a instanciação do objeto tree, uma lista de elementos e
a inserção desses elementos, usando um loop. Nas próximas linhas, temos o exemplo de uso das funções.
Confira!
Linha 8: quantidade de elementos da árvores.
Linha 9: altura da árvore.
Linhas 10 e 11: valor mínimo e valor máximo, respectivamente.
Linhas 12 e 13: valor mínimo e máximo na -ésima posição.k
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 52/56
Falta pouco para atingir seus objetivos.
Vamos praticar alguns conceitos?
Questão 1
Marque a opção que apresenta corretamente a complexidade de espaço de execução do módulo sbbst:
Linhas 14, 15 e 16: percurso pré-ordem, in-ordem e pós-ordem.
Linhas 17 e 18: deleção de elemento na árvore.
Linha 19: inserção de elemento na árvore.
A O(n)
B O(logn)
C O(n logn)
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 53/56
Parabéns! A alternativa A está correta.
Módulos sbbst possuem complexidade de espaço igual a .
Questão 2
Sobre as classes de funções módulo sbbst, sejam as seguintes afirmativas:
I. A classe sbbst. getMinVal () possui complexidade de tempo .
II. A classe sbbst.kthsmallest sempre retorna o maior elemento de uma árvore binária, balanceada
ou não, independentemente do valor do parâmetro enviado.
III. A classe sbbst.gettheightTree() possui complexidade de execução .
Está(ão) correta(s) a(s) afirmativa(s):
D O (n2)
E O (n3)
O(n)
O(logn)
(k)
O(n)
A I.
B I e II.
C I e III.
D I, II e III.
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 54/56
Parabéns! A alternativa A está correta.
A afirmativa II está errada, pois o retorno do maior elemento é baseado no parâmetro enviado , ou
seja, o -ésimo valor, e a afirmativa III está errada porque sbbst.getHeightTree() possui complexidade
de tempo . Logo, apenas a I está correta.
Considerações �nais
Como vimos ao longo do material, árvores AVL e árvores B compreendem requisitos fundamentais para
modelagem de diversos problemas teóricos em computação. Além do mais, esses elementos podem ser
abstraídos e aplicados em diversos problemas do dia a dia, bem como em diversos outros temas
interessantes na ciência da computação.
Entender as principais características e operações dessas árvores é fundamental para aprofundar o
conhecimento das diversas estruturas de dados.
Podcast
Ouça, agora, uma entrevista sobre Árvores de Busca.
E III.
(k)
k
O(1)

24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 55/56
Explore +
Confira as indicações que separamos para você!
Busque pelo simulador INE 5408/INE 5609 - Simulação de Árvores AVL, da UFSC.
Pesquise o simulador (animação) de árvores rubro-negras Red/Black Tree Visualization, da Usfca.
Procure o material Complete Binary Tree, da Geeksforgeeks, e veja outros tipos de estruturas de árvores.
Referências
ADEL’SON-VEL’SKII, G. M.; LANDIS, E. M. Algorithm for the Organization of Information. Soviet Mathematics
Doklady, 3, 1962.
CORMEN, T. H. et al. Algoritmos: teoria e prática. v. 2. 2002. p. 296.
PREISS, B. Estruturas de dados e algoritmos: padrões de projetos orientados a objetos com Java. [S.l.]:
Elsevier, 2000.
STOUT, Q.; WARREN, B. Tree Rebalancing in Optimal Time and Space. Communications of the ACM, v. 29, n.
9, 1986.
SZWARCFITER, J. L.; MARKENZON, L. Estruturas de dados e seus algoritmos. [S.l.]: Livros Técnicos e
Científicos, 1994.
24/09/2023, 12:04 Árvores de busca
https://stecine.azureedge.net/repositorio/00212ti/07392/index.html# 56/56
Material para download
Clique no botão abaixo para fazer o download do conteúdo completo em formato PDF.
Download material
O que você achou do conteúdo?
Relatar problema
javascript:CriaPDF()