Árvore AVL

Estrutura de Dados Avançada — QXD0115

Prof. Atı́lio Gomes Luiz

[Link]@[Link]

Universidade Federal do Ceará

1º semestre/2024
Introdução

• Contexto: Temos um conjunto de n chaves S = {s1 , s2 , . . . , sn } com

probabilidade de acesso idênticas entre si.

2
Introdução

• Contexto: Temos um conjunto de n chaves S = {s1 , s2 , . . . , sn } com

probabilidade de acesso idênticas entre si.

• Dentre TODAS as árvores binárias de busca com n nós, as árvores

binárias de busca completas são aquelas que minimizam o número de
comparações efetuadas no pior caso para uma busca com chaves de
probabilidades de ocorrência idênticas.
◦ Uma árvore binária completa com n > 0 nós tem altura h = 1 + ⌊lg n⌋.

2
Introdução

• Contexto: Temos um conjunto de n chaves S = {s1 , s2 , . . . , sn } com

probabilidade de acesso idênticas entre si.

• Dentre TODAS as árvores binárias de busca com n nós, as árvores

binárias de busca completas são aquelas que minimizam o número de
comparações efetuadas no pior caso para uma busca com chaves de
probabilidades de ocorrência idênticas.
◦ Uma árvore binária completa com n > 0 nós tem altura h = 1 + ⌊lg n⌋.

• Alguns questionamentos:
◦ Seria possı́vel manter a árvore sempre completa após consecutivas
remoções ou inclusões?
◦ Quanto custa isso? Vale o esforço?

2
Um exemplo ruim para o restabelecimento de
árvores completas
8
4 12
2 6 10 14

1 3 5 7 9 11 13

Vamos incluir 0

3
Um exemplo ruim para o restabelecimento de
árvores completas
8 8
4 12
4 12
2 6 10 14
2 6 10 14
1 3 5 7 9 11 13
1 3 5 7 9 11 13
0
Vamos incluir 0 Não é mais completa

3
Um exemplo ruim para o restabelecimento de
árvores completas
8 8
4 12
4 12
2 6 10 14
2 6 10 14
1 3 5 7 9 11 13
1 3 5 7 9 11 13
0
Vamos incluir 0 Não é mais completa
7
3 11

1 5 9 13

0 2 4 6 8 10 12 14

3
Um exemplo ruim para o restabelecimento de
árvores completas
8 8
4 12
4 12
2 6 10 14
2 6 10 14
1 3 5 7 9 11 13
1 3 5 7 9 11 13
0
Vamos incluir 0 Não é mais completa
7
3 11

1 5 9 13

0 2 4 6 8 10 12 14

O algoritmo de restabelecimento requer, pelo menos, Ω(n) passos.

Árvores completas não são recomendadas para aplicações dinâmicas.
3
Alternativa — Árvores Balanceadas

• Uma árvore binária é balanceada se sua altura é da ordem de O(lg n) e,

além disso, esta propriedade se estende a todas as suas subárvores:

4
Alternativa — Árvores Balanceadas

• Uma árvore binária é balanceada se sua altura é da ordem de O(lg n) e,

além disso, esta propriedade se estende a todas as suas subárvores:
◦ Cada subárvore que contém m nós deve possuir altura O(lg m).

4
Alternativa — Árvores Balanceadas

• Uma árvore binária é balanceada se sua altura é da ordem de O(lg n) e,

além disso, esta propriedade se estende a todas as suas subárvores:
◦ Cada subárvore que contém m nós deve possuir altura O(lg m).

• Nossa esperança: Como a forma de uma árvore balanceada é menos rı́gida

que a de uma completa, torna-se “mais fácil” o seu rebalanceamento.

4
Árvore AVL

5
Árvore AVL

• Primeira árvore binária de busca a garantir tempo de execução O(log n)

para inserção, busca e remoção no pior caso.

• Criada pelos soviéticos Adelson-Vělsky e Landis, em 1962.

Adelson-Vělsky Landis

6
Árvore AVL

Definição

Uma árvore binária T é do tipo AVL se, para todo nó v de T , as alturas
de suas duas subárvores, esquerda e direita, diferem em módulo de até
uma unidade.

7
Árvore AVL

Definição

Uma árvore binária T é do tipo AVL se, para todo nó v de T , as alturas
de suas duas subárvores, esquerda e direita, diferem em módulo de até
uma unidade.

• Um nó v que satisfaz essa propriedade é dito regulado;

caso contrário, v é dito desregulado.
Uma árvore que contém nó desregulado é dita desregulada.

7
Árvore AVL

Definição

Uma árvore binária T é do tipo AVL se, para todo nó v de T , as alturas
de suas duas subárvores, esquerda e direita, diferem em módulo de até
uma unidade.

• Um nó v que satisfaz essa propriedade é dito regulado;

caso contrário, v é dito desregulado.
Uma árvore que contém nó desregulado é dita desregulada.

• Fator de balanceamento (f b(v)): a diferença entre as alturas direita e

esquerda de v, ou seja, f b(v) = hD (v) − hE (v).

7
Exemplos de árvores binárias AVL

−1 1

0 0 0 −1

0 0 0

• Todos os nós nestas duas árvores estão regulados.

8
Exemplos de árvores binárias AVL

−1 1

0 0 0 −1

0 0 0

• Todos os nós nestas duas árvores estão regulados.

• Ou seja, para todo nó v, temos |hD (v) − hE (v)| ≤ 1.

8
Exemplos de árvores binárias de busca AVL

1
4
−1 1
2 6
0 0 0 −1
50 1 5 9
0 0 0
23 66 7

• Além de possuirem a propriedade AVL, essas árvores possuem a

propriedade de serem binárias de busca.

9
Árvore completa × Árvore AVL

Fato: Toda árvore completa é AVL, mas nem toda árvore AVL
é completa.

10
Árvore completa × Árvore AVL

Fato: Toda árvore completa é AVL, mas nem toda árvore AVL
é completa.

Árvore completa

10
Árvore completa × Árvore AVL

Fato: Toda árvore completa é AVL, mas nem toda árvore AVL
é completa.

É AVL mas não é

Árvore completa
completa. Por quê?

10
Árvore completa × Árvore AVL

Fato: Toda árvore completa é AVL, mas nem toda árvore AVL
é completa.

É AVL mas não é Não é completa e nem

Árvore completa
completa. Por quê? AVL. Por quê?

10
Prova do balanceamento

11
Balanceamento de árvores AVL

• Ideia: Dada uma árvore AVL T , vamos fixar a altura h e determinar o

valor mı́nimo do número n de nós.

12
Balanceamento de árvores AVL

• Ideia: Dada uma árvore AVL T , vamos fixar a altura h e determinar o

valor mı́nimo do número n de nós.

Problema
Dada uma árvore AVL de altura h, qual seria o valor mı́nimo possı́vel
para n?

12
Árvores de Fibonacci
• Árvores AVL com os piores fatores de balanceamento.
T4
T3
T2
T0 T1
NULL

13
Árvores de Fibonacci
• Árvores AVL com os piores fatores de balanceamento.
T4
T3
T2
T0 T1
NULL

Th

Th−2
Th−1
13
Número de nós — Árvores de Fibonacci
• Denotamos por N (T ) o número de nós de uma árvore T

14
Número de nós — Árvores de Fibonacci
• Denotamos por N (T ) o número de nós de uma árvore T
• Número de nós de Th :

0
 se h = 0;
N (Th ) = 1 se h = 1;
se h > 1.

1 + N (Th−1 ) + N (Th−2 )


14
Número de nós — Árvores de Fibonacci
• Denotamos por N (T ) o número de nós de uma árvore T
• Número de nós de Th :

0
 se h = 0;
N (Th ) = 1 se h = 1;
se h > 1.

1 + N (Th−1 ) + N (Th−2 )


• A fórmula acima, lembra a fórmula do h-ésimo termo da sequência de

Fibonacci:

0
 se h = 0;
F (h) = 1 se h = 1;
se h > 1.

F (h − 1) + F (h − 2)


14
Número de nós — Árvores de Fibonacci
• Denotamos por N (T ) o número de nós de uma árvore T
• Número de nós de Th :

0
 se h = 0;
N (Th ) = 1 se h = 1;
se h > 1.

1 + N (Th−1 ) + N (Th−2 )


• A fórmula acima, lembra a fórmula do h-ésimo termo da sequência de

Fibonacci:

0
 se h = 0;
F (h) = 1 se h = 1;
se h > 1.

F (h − 1) + F (h − 2)


• Logo, N (Th ) ≥ F (h), para todo h ≥ 0.

14
Número de nós — Árvores de Fibonacci

Fato: Dada uma árvore AVL T de altura h, temos que:

N (T ) ≥ N (Th ) ≥ F (h).

15
Número de nós — Árvores de Fibonacci

Fato: Dada uma árvore AVL T de altura h, temos que:

N (T ) ≥ N (Th ) ≥ F (h).

Fórmula do h-ésimo termo da sequência de Fibonacci:


0
 se h = 0;
F (h) = 1 se h = 1;
se h > 1.

F (h − 1) + F (h − 2)


Fato: Para h > 1, o h-ésimo termo da sequência de Fibonacci é dado

por: " √ h  √ h #
1 1+ 5 1− 5
F (h) = √ −
5 2 2

15
Prova h = O(lg n)
Se T é uma árvore AVL com altura h e com n nós, então h = O(lg n).

16
Prova h = O(lg n)
Se T é uma árvore AVL com altura h e com n nós, então h = O(lg n).
√ √
Prova: Do slide anterior, temos que n ≥ F (h) = √1 ( 1+ 5 )h
5 2 − √15 ( 1−2 5 )h .

16
Prova h = O(lg n)
Se T é uma árvore AVL com altura h e com n nós, então h = O(lg n).
√ √
Prova: Do slide anterior, temos que n ≥ F (h) = √1 ( 1+ 5 )h
5 2 − √15 ( 1−2 5 )h .
√
Como h > 0, temos que √1 ( 1− 5 )h
5 2 < 1.

16
Prova h = O(lg n)
Se T é uma árvore AVL com altura h e com n nós, então h = O(lg n).
√ √
Prova: Do slide anterior, temos que n ≥ F (h) = √1 ( 1+ 5 )h
5 2 − √15 ( 1−2 5 )h .
√
Como h > 0, temos que √1 ( 1− 5 )h < 1.
5 2
 √ h
Portanto, n ≥ F (h) > √1
5
1+ 5
2 − 1.

16
Prova h = O(lg n)
Se T é uma árvore AVL com altura h e com n nós, então h = O(lg n).
√ √
Prova: Do slide anterior, temos que n ≥ F (h) = √1 ( 1+ 5 )h
5 2 − √15 ( 1−2 5 )h .
√
Como h > 0, temos que √1 ( 1− 5 )h < 1.
5 2
 √ h
Portanto, n ≥ F (h) > √1
5
1+ 5
2 − 1.
√
ah
Fazendo a = 2 ,
1+ 5
tem-se n > √1 ah
5
− 1. O que implica, n + 1 > √
5
.

16
Prova h = O(lg n)
Se T é uma árvore AVL com altura h e com n nós, então h = O(lg n).
√ √
Prova: Do slide anterior, temos que n ≥ F (h) = √1 ( 1+ 5 )h
5 2 − √15 ( 1−2 5 )h .
√
Como h > 0, temos que √1 ( 1− 5 )h < 1.
5 2
 √ h
Portanto, n ≥ F (h) > √1
5
1+ 5
2 − 1.
√
ah
Fazendo a = 2 ,
1+ 5
tem-se n > √1 ah
5
− 1. O que implica, n + 1 > √
5
.
Aplicando logaritmo na base a em ambos os lados, temos:
√
loga (n + 1) > loga ah − loga 5
√
loga (n + 1) > h − loga 5
√
h < loga (n + 1) + loga 5
1 √
h< log2 (n + 1) + loga 5 (mudança de base)
log2 a
h < 1.44 · log2 (n + 1) + 1.67 = O(lg n).

16
Inserção em árvores AVL

17
Inserção em Árvores AVL
• Ideia: Após cada inserção, verificar se algum nó p se encontra
desregulado.
◦ Em caso positivo, aplicar transformações apropriadas para regulá-lo.

18
Inserção em Árvores AVL
• Ideia: Após cada inserção, verificar se algum nó p se encontra
desregulado.
◦ Em caso positivo, aplicar transformações apropriadas para regulá-lo.

• Pergunta: Após a inserção de um nó, quais nós podem ter se

tornado desregulados?

18
Inserção em Árvores AVL
• Ideia: Após cada inserção, verificar se algum nó p se encontra
desregulado.
◦ Em caso positivo, aplicar transformações apropriadas para regulá-lo.

• Pergunta: Após a inserção de um nó, quais nós podem ter se

tornado desregulados?
Exemplo: Inserir 3 na árvore abaixo.

50
20 60
10 30 9

5 15

18
Inserção em Árvores AVL

• Em alguns casos, a inserção de um novo nó x na árvore AVL pode vir a

modificar o fator de balanceamento de algum nó no caminho que vai de x
até a raiz.

19
Inserção em Árvores AVL

• Em alguns casos, a inserção de um novo nó x na árvore AVL pode vir a

modificar o fator de balanceamento de algum nó no caminho que vai de x
até a raiz.

• No caso em que algum nó v neste caminho ficar desregulado, uma

operação de regulagem do nó v deve ser realizada a fim de regular o nó.

19
Inserção em Árvores AVL

• Em alguns casos, a inserção de um novo nó x na árvore AVL pode vir a

modificar o fator de balanceamento de algum nó no caminho que vai de x
até a raiz.

• No caso em que algum nó v neste caminho ficar desregulado, uma

operação de regulagem do nó v deve ser realizada a fim de regular o nó.
◦ A essa operação de regulagem do nó v chamaremos de rotação do nó v.

19
Inserção em Árvores AVL

• Em alguns casos, a inserção de um novo nó x na árvore AVL pode vir a

modificar o fator de balanceamento de algum nó no caminho que vai de x
até a raiz.

• No caso em que algum nó v neste caminho ficar desregulado, uma

operação de regulagem do nó v deve ser realizada a fim de regular o nó.
◦ A essa operação de regulagem do nó v chamaremos de rotação do nó v.

• Usaremos basicamente quatro tipos de rotações:

19
Inserção em Árvores AVL

• Em alguns casos, a inserção de um novo nó x na árvore AVL pode vir a

modificar o fator de balanceamento de algum nó no caminho que vai de x
até a raiz.

• No caso em que algum nó v neste caminho ficar desregulado, uma

operação de regulagem do nó v deve ser realizada a fim de regular o nó.
◦ A essa operação de regulagem do nó v chamaremos de rotação do nó v.

• Usaremos basicamente quatro tipos de rotações:

◦ Rotação esquerda

19
Inserção em Árvores AVL

• Em alguns casos, a inserção de um novo nó x na árvore AVL pode vir a

modificar o fator de balanceamento de algum nó no caminho que vai de x
até a raiz.

• No caso em que algum nó v neste caminho ficar desregulado, uma

operação de regulagem do nó v deve ser realizada a fim de regular o nó.
◦ A essa operação de regulagem do nó v chamaremos de rotação do nó v.

• Usaremos basicamente quatro tipos de rotações:

◦ Rotação esquerda
◦ Rotação direita

19
Inserção em Árvores AVL

• Em alguns casos, a inserção de um novo nó x na árvore AVL pode vir a

modificar o fator de balanceamento de algum nó no caminho que vai de x
até a raiz.

• No caso em que algum nó v neste caminho ficar desregulado, uma

operação de regulagem do nó v deve ser realizada a fim de regular o nó.
◦ A essa operação de regulagem do nó v chamaremos de rotação do nó v.

• Usaremos basicamente quatro tipos de rotações:

◦ Rotação esquerda
◦ Rotação direita
◦ Rotação dupla à esquerda

19
Inserção em Árvores AVL

• Em alguns casos, a inserção de um novo nó x na árvore AVL pode vir a

modificar o fator de balanceamento de algum nó no caminho que vai de x
até a raiz.

• No caso em que algum nó v neste caminho ficar desregulado, uma

operação de regulagem do nó v deve ser realizada a fim de regular o nó.
◦ A essa operação de regulagem do nó v chamaremos de rotação do nó v.

• Usaremos basicamente quatro tipos de rotações:

◦ Rotação esquerda
◦ Rotação direita
◦ Rotação dupla à esquerda
◦ Rotação dupla à direita

19
Rotação Esquerda e Rotação Direita
p u
Rotação
Direita(p)
u p
T3 T1
Rotação
Esquerda(u)
T1 T2 T2 T3

20
Rotação Esquerda e Rotação Direita
p u
Rotação
Direita(p)
u p
T3 T1
Rotação
Esquerda(u)
T1 T2 T2 T3

Propriedade 1

As rotações preservam a natureza da árvore como sendo binária de

busca.

20
Rotação Dupla à Direita
p v
u
Rotação Dupla u p
v T4 à Direita (p)
T1
T2 T3 T1 T2 T3 T4

21
Rotação Dupla à Direita
p v
u
Rotação Dupla u p
v T4 à Direita (p)
T1
T2 T3 T1 T2 T3 T4

• Rotação Dupla à Direita = Rot. Esquerda(u) + Rot. Direita(p)

p p v
u v
u p
v T4 u T4
T1 T3
T2 T3 T1 T2 T1 T2 T3 T4

21
Rotação Dupla à Esquerda
p y

z
Rotação Dupla p z
T1 y à Esquerda (p)
T4
T2 T3 T1 T2 T3 T4

22
Rotação Dupla à Esquerda
p y

z
Rotação Dupla p z
T1 y à Esquerda (p)
T4
T2 T3 T1 T2 T3 T4

• Rotação Dupla à Esquerda = Rot. Direita(z) + Rot. Esquerda(p)

p p y
z y
p z
T1 y T1 z
T4 T2
T2 T3 T3 T4 T1 T2 T3 T4

22
Exemplo
Inclusão da chave 1 na árvore e posterior efeito de uma rotação direita
do nó 5, que tornou-se desregulado após a inclusão de 1.

7
7
5 8
5 8
Insert(1) 3 6 9
3 6 9
2 4
2 4
1

23
Exemplo
Inclusão da chave 1 na árvore e posterior efeito de uma rotação direita
do nó 5, que tornou-se desregulado após a inclusão de 1.

7
7
5 8
5 8
Insert(1) 3 6 9
3 6 9
2 4
2 4
1

7
7
5 8
3 8
3 6 9 RightRotation(5)
2 5 9
2 4
1 4 6
1
23
Análise da operação de inserção

24
Análise da Inserção

• Após a inserção de um nó x na árvore, as chamadas recursivas vão se

“desenrolando” e todos os vértices no caminho de x até a raiz da árvore
devem ter seus fatores de balanceamento devidamente checados.

25
Análise da Inserção

• Após a inserção de um nó x na árvore, as chamadas recursivas vão se

“desenrolando” e todos os vértices no caminho de x até a raiz da árvore
devem ter seus fatores de balanceamento devidamente checados.

• Vamos provar que, uma vez que um nó p torna-se desregulado, a

regulagem de p é restabelecida pela aplicação de uma das rotações AVL
estudadas.

25
Análise da Inserção

• Suponha que o nó x acabou de ser inserido em T .

26
Análise da Inserção

• Suponha que o nó x acabou de ser inserido em T .

• Se após a inclusão de x todos os nós mantiveram-se regulados, então a

árvore manteve-se AVL e não há nada o que efetuar.

26
Análise da Inserção

• Suponha que o nó x acabou de ser inserido em T .

• Se após a inclusão de x todos os nós mantiveram-se regulados, então a

árvore manteve-se AVL e não há nada o que efetuar.

• Caso contrário, seja p o ancestral de x mais próximo que se tornou

desregulado.

26
Análise da Inserção

• Suponha que o nó x acabou de ser inserido em T .

• Se após a inclusão de x todos os nós mantiveram-se regulados, então a

árvore manteve-se AVL e não há nada o que efetuar.

• Caso contrário, seja p o ancestral de x mais próximo que se tornou

desregulado.
◦ Temos que |hD (p) − hE (p)| = 2 pois T era uma árvore AVL antes da
inclusão de x e, além disso, a inclusão de um nó não pode aumentar
em mais de uma unidade a altura de qualquer subárvore.

26
Análise da Inserção

• Suponha que o nó x acabou de ser inserido em T .

• Se após a inclusão de x todos os nós mantiveram-se regulados, então a

árvore manteve-se AVL e não há nada o que efetuar.

• Caso contrário, seja p o ancestral de x mais próximo que se tornou

desregulado.
◦ Temos que |hD (p) − hE (p)| = 2 pois T era uma árvore AVL antes da
inclusão de x e, além disso, a inclusão de um nó não pode aumentar
em mais de uma unidade a altura de qualquer subárvore.

• Há exatamente dois casos a considerar:

26
Análise da Inserção

• Suponha que o nó x acabou de ser inserido em T .

• Se após a inclusão de x todos os nós mantiveram-se regulados, então a

árvore manteve-se AVL e não há nada o que efetuar.

• Caso contrário, seja p o ancestral de x mais próximo que se tornou

desregulado.
◦ Temos que |hD (p) − hE (p)| = 2 pois T era uma árvore AVL antes da
inclusão de x e, além disso, a inclusão de um nó não pode aumentar
em mais de uma unidade a altura de qualquer subárvore.

• Há exatamente dois casos a considerar:

◦ Caso (1): hE (p) > hD (p)

26
Análise da Inserção

• Suponha que o nó x acabou de ser inserido em T .

• Se após a inclusão de x todos os nós mantiveram-se regulados, então a

árvore manteve-se AVL e não há nada o que efetuar.

• Caso contrário, seja p o ancestral de x mais próximo que se tornou

desregulado.
◦ Temos que |hD (p) − hE (p)| = 2 pois T era uma árvore AVL antes da
inclusão de x e, além disso, a inclusão de um nó não pode aumentar
em mais de uma unidade a altura de qualquer subárvore.

• Há exatamente dois casos a considerar:

◦ Caso (1): hE (p) > hD (p)
◦ Caso (2): hD (p) > hE (p)

26
Caso 1: hE (p) > hD (p)

• O nó x foi inserido na subárvore esquerda de p.

27
Caso 1: hE (p) > hD (p)

• O nó x foi inserido na subárvore esquerda de p.

• p possui o filho esquerdo u, u ̸= x. Pois caso contrário, p não estaria
desregulado.

27
Caso 1: hE (p) > hD (p)

• O nó x foi inserido na subárvore esquerda de p.

• p possui o filho esquerdo u, u ̸= x. Pois caso contrário, p não estaria
desregulado.
• Por esse mesmo motivo, sabe-se que hE (u) ̸= hD (u).

27
Caso 1: hE (p) > hD (p)

• O nó x foi inserido na subárvore esquerda de p.

• p possui o filho esquerdo u, u ̸= x. Pois caso contrário, p não estaria
desregulado.
• Por esse mesmo motivo, sabe-se que hE (u) ̸= hD (u).
• Há dois subcasos a considerar:

27
Caso 1: hE (p) > hD (p)

• O nó x foi inserido na subárvore esquerda de p.

• p possui o filho esquerdo u, u ̸= x. Pois caso contrário, p não estaria
desregulado.
• Por esse mesmo motivo, sabe-se que hE (u) ̸= hD (u).
• Há dois subcasos a considerar:
◦ Caso 1(a): hE (u) > hD (u).

27
Caso 1: hE (p) > hD (p)

• O nó x foi inserido na subárvore esquerda de p.

• p possui o filho esquerdo u, u ̸= x. Pois caso contrário, p não estaria
desregulado.
• Por esse mesmo motivo, sabe-se que hE (u) ̸= hD (u).
• Há dois subcasos a considerar:
◦ Caso 1(a): hE (u) > hD (u).
◦ Caso 1(b): hE (u) < hD (u).
27
Caso 1(a): hE (u) > hD (u)
Solução: Rotação direita simples em p.

O nó x é inserido à esquerda de u.

Note que h(T1 ) = h(T2 ) + 1.
Após a rotação simples, a altura final permanece inalterada.
Nenhuma modificação futura é necessária.

28
Caso 1(b): hE (u) < hD (u)
Solução: Rotação dupla direita em p.

O nó inserido pode ser X ou Y .

Quando h = 2, as árvores T1 e T3 são vazias, e o nó inserido é o próprio nó
C; neste caso as árvores T21 e T22 são vazias.
A altura final permanece inalterada.
Nenhuma modificação futura é necessária.
29
Caso 2: hE (p) < hD (p)

• O nó x foi inserido na subárvore direita de p.

30
Caso 2: hE (p) < hD (p)

• O nó x foi inserido na subárvore direita de p.

• p possui o filho direito u, u ̸= x. Pois caso contrário, p não estaria
desregulado.

30
Caso 2: hE (p) < hD (p)

• O nó x foi inserido na subárvore direita de p.

• p possui o filho direito u, u ̸= x. Pois caso contrário, p não estaria
desregulado.
• Por esse mesmo motivo, sabe-se que hE (u) ̸= hD (u).

30
Caso 2: hE (p) < hD (p)

• O nó x foi inserido na subárvore direita de p.

• p possui o filho direito u, u ̸= x. Pois caso contrário, p não estaria
desregulado.
• Por esse mesmo motivo, sabe-se que hE (u) ̸= hD (u).
• Há dois subcasos a considerar:

30
Caso 2: hE (p) < hD (p)

• O nó x foi inserido na subárvore direita de p.

• p possui o filho direito u, u ̸= x. Pois caso contrário, p não estaria
desregulado.
• Por esse mesmo motivo, sabe-se que hE (u) ̸= hD (u).
• Há dois subcasos a considerar:
◦ Caso 2(a): hE (u) < hD (u).

30
Caso 2: hE (p) < hD (p)

• O nó x foi inserido na subárvore direita de p.

• p possui o filho direito u, u ̸= x. Pois caso contrário, p não estaria
desregulado.
• Por esse mesmo motivo, sabe-se que hE (u) ̸= hD (u).
• Há dois subcasos a considerar:
◦ Caso 2(a): hE (u) < hD (u).
◦ Caso 2(b): hE (u) > hD (u).
30
Caso 2(a): hE (u) < hD (u)
Solução: Rotação esquerda simples em p.

O nó x é inserido à direita de u.

Note que h(T1 ) = h(T2 ) + 1.
Após a rotação, a altura final permanece inalterada.
Nenhuma modificação futura é necessária.

31
Caso 2(b): hE (u) > hD (u)
Solução: Rotação dupla esquerda em p.

O nó inserido pode ser X ou Y .

Quando h = 2, as árvores T1 e T3 são vazias, e o nó inserido é o próprio nó
C; neste caso as árvores T21 e T22 são vazias.
A altura final permanece inalterada.
Nenhuma modificação futura é necessária.
32
Propriedades das rotações
Propriedade 1

As rotações preservam a natureza da árvore como sendo binária de

busca.

33
Propriedades das rotações
Propriedade 1

As rotações preservam a natureza da árvore como sendo binária de

busca.

Propriedade 2

Uma vez que um nó p torna-se desregulado, a regulagem de p é res-

tabelecida pela aplicação de uma das 4 rotações vistas.

33
Propriedades das rotações
Propriedade 1

As rotações preservam a natureza da árvore como sendo binária de

busca.

Propriedade 2

Uma vez que um nó p torna-se desregulado, a regulagem de p é res-

tabelecida pela aplicação de uma das 4 rotações vistas.

Propriedade 3

Dado um nó p desregulado, uma rotação apropriada de p assegura a

regulagem de TODOS os nós ancestrais de p.

33
Atividade
Mostre o passo-a-passo da inserção das chaves 1,2,3,4,5,6,7 em uma
árvore AVL inicialmente vazia. Em cada passo, ilustre o valor do fator
de balanceamento de cada nó, assim como as rotações realizadas.

34
Implementação da inserção

35
Como determinar o fator de balanço de um nó?

Como verificar se algum nó v de T se tornou desregulado após a inclusão?

• Basta calcular as alturas de suas subárvores e subtrair uma da outra.

36
Como determinar o fator de balanço de um nó?

Como verificar se algum nó v de T se tornou desregulado após a inclusão?

• Basta calcular as alturas de suas subárvores e subtrair uma da outra.
• Precisamos fazer isso mantendo o tempo de inserção em O(log n).
◦ É possı́vel?

36
Como determinar o fator de balanço de um nó?

Como verificar se algum nó v de T se tornou desregulado após a inclusão?

• Basta calcular as alturas de suas subárvores e subtrair uma da outra.
• Precisamos fazer isso mantendo o tempo de inserção em O(log n).
◦ É possı́vel?

Ideia: Cada nó v da árvore terá um campo adicional chamado height

que guardará a altura da árvore enraizada em v.
• Assim, não será preciso percorrer a árvore enraizada em v.
• Poderemos calcular o fator de balanceamento do nó v em tempo
constante O(1).

36
Como a altura de cada nó é determinada?

• Cada nó da árvore possui o campo height, que guarda sua altura.
• Assim que um nó p é inserido na árvore ele é um nó folha.
◦ A altura de p é igual a 1 logo após sua inserção.
◦ Fazendo p->height = 1 assim que o nó p é inserido, determinamos
sua altura em tempo O(1).

37
Como a altura de cada nó é determinada?

• Cada nó da árvore possui o campo height, que guarda sua altura.
• Assim que um nó p é inserido na árvore ele é um nó folha.
◦ A altura de p é igual a 1 logo após sua inserção.
◦ Fazendo p->height = 1 assim que o nó p é inserido, determinamos
sua altura em tempo O(1).
• Observação: A partir deste momento, os únicos nós da árvore que podem
ter alturas modificadas são os nós no caminho de p até a raiz.

37
Como a altura de cada nó é determinada?

• Cada nó da árvore possui o campo height, que guarda sua altura.
• Assim que um nó p é inserido na árvore ele é um nó folha.
◦ A altura de p é igual a 1 logo após sua inserção.
◦ Fazendo p->height = 1 assim que o nó p é inserido, determinamos
sua altura em tempo O(1).
• Observação: A partir deste momento, os únicos nós da árvore que podem
ter alturas modificadas são os nós no caminho de p até a raiz.
◦ Todos eles devem ser verificados e ter seus campos height
corretamente atualizados.

37
Como a altura de cada nó é determinada?

• Cada nó da árvore possui o campo height, que guarda sua altura.
• Assim que um nó p é inserido na árvore ele é um nó folha.
◦ A altura de p é igual a 1 logo após sua inserção.
◦ Fazendo p->height = 1 assim que o nó p é inserido, determinamos
sua altura em tempo O(1).
• Observação: A partir deste momento, os únicos nós da árvore que podem
ter alturas modificadas são os nós no caminho de p até a raiz.
◦ Todos eles devem ser verificados e ter seus campos height
corretamente atualizados.
◦ Existem O(log n) destes nós e essa atualização pode ser feita em tempo
constante a medida que as chamadas recursivas “se desenrolam”.

37
 Arquivo Node.h

1 # ifndef NODE_H
2 # define NODE_H
3
4 struct Node {
5 int key ;
6 int height ;
7 Node * left ;
8 Node * right ;
9 };
10
11 # endif

38
 Arquivo Tree.h (com código inicial)
1 # ifndef TREE_H
2 # define TREE_H
3 # include " Node . h "
4
5 class Tree {
6 public :
7 Tree () = default ;
8 void add ( int key ) ;
9 ˜ Tree () ;
10
11 private :
12 Node * root { nullptr };
13 int height ( Node * node ) ;
14 int balance ( Node * node ) ;
15 Node * rightRotation ( Node * p ) ;
16 Node * leftRotation ( Node * p ) ;
17 Node * add ( Node *p , int key ) ;
18 Node * fixup_node ( Node *p , int key ) ;
19 };
20
21 # endif

39
Determinando fator de balanceamento de um nó

Calculamos o fator de balanceamento de um nó v através da subtração das

alturas das subárvores esquerda e direita do nó:

40
 Determinando fator de balanceamento de um nó

Calculamos o fator de balanceamento de um nó v através da subtração das

alturas das subárvores esquerda e direita do nó:

1 int Tree :: height ( Node * node ) {

2 return ( node == nullptr ) ? 0 : node - > height ;
3 }

40
 Determinando fator de balanceamento de um nó

Calculamos o fator de balanceamento de um nó v através da subtração das

alturas das subárvores esquerda e direita do nó:

1 int Tree :: height ( Node * node ) {

2 return ( node == nullptr ) ? 0 : node - > height ;
3 }

1 int Tree :: balance ( Node * node ) {

2 return height ( node - > right ) - height ( node - > left ) ;
3 }

40
Rotação Direita

p u

u p
Right(p)
T3 T1

T1 T2 T2 T3

41
 Rotação Direita

p u

u p
Right(p)
T3 T1

T1 T2 T2 T3

1 Node * Tree :: rightRotation ( Node * p ) {

2 Node * u = p - > left ;
3 p - > left = u - > right ;
4 u - > right = p ;
5 // atualiza altura dos nodes
6 p - > height = 1 + max ( height (p - > left ) , height (p - > right ) ) ;
7 u - > height = 1 + max ( height (u - > left ) , height (u - > right ) ) ;
8 return u ; // nova raiz
9 }

41
Rotação Esquerda

p u

u p
Left(p)
T1 T3

T2 T3 T1 T2

42
 Rotação Esquerda

p u

u p
Left(p)
T1 T3

T2 T3 T1 T2

1 Node * Tree :: leftRotation ( Node * p ) {

2 Node * u = p - > right ;
3 p - > right = u - > left ;
4 u - > left = p ;
5 // atualiza altura dos nodes
6 p - > height = 1 + max ( height (p - > left ) , height (p - > right ) ) ;
7 u - > height = 1 + max ( height (u - > left ) , height (u - > right ) ) ;
8 return u ; // nova raiz
9 }

42
 Inserção

Função pública:

1 void Tree :: add ( int key ) {

2 root = add ( root , key ) ;
3 }

43
 Inserção

Função privada:

1 Node * Tree :: add ( Node *p , int key ) {

2 if ( p == nullptr ) // subarvore vazia
3 return new Node { key , 1 , nullptr , nullptr };

44
 Inserção

Função privada:

1 Node * Tree :: add ( Node *p , int key ) {

2 if ( p == nullptr ) // subarvore vazia
3 return new Node { key , 1 , nullptr , nullptr };
4 if ( key == p - > key ) // chave repetida
5 return p ;

44
 Inserção

Função privada:

1 Node * Tree :: add ( Node *p , int key ) {

2 if ( p == nullptr ) // subarvore vazia
3 return new Node { key , 1 , nullptr , nullptr };
4 if ( key == p - > key ) // chave repetida
5 return p ;
6 if ( key < p - > key )
7 p - > left = add (p - > left , key ) ;
8 else
9 p - > right = add (p - > right , key ) ;

44
 Inserção

Função privada:

1 Node * Tree :: add ( Node *p , int key ) {

2 if ( p == nullptr ) // subarvore vazia
3 return new Node { key , 1 , nullptr , nullptr };
4 if ( key == p - > key ) // chave repetida
5 return p ;
6 if ( key < p - > key )
7 p - > left = add (p - > left , key ) ;
8 else
9 p - > right = add (p - > right , key ) ;
10
11 p = fixup_node (p , key ) ; // regula o node p
12
13 return p ;
14 }

44
 Inserção
1 Node * Tree :: fixup_node ( Node *p , int key ) {
2 // atualiza altura deste node ancestral p
3 p - > height = 1 + max ( height (p - > left ) , height (p - > right ) ) ;

45
 Inserção
1 Node * Tree :: fixup_node ( Node *p , int key ) {
2 // atualiza altura deste node ancestral p
3 p - > height = 1 + max ( height (p - > left ) , height (p - > right ) ) ;
4 // obtem balanco de p
5 int bal = balance ( p ) ;

45
 Inserção
1 Node * Tree :: fixup_node ( Node *p , int key ) {
2 // atualiza altura deste node ancestral p
3 p - > height = 1 + max ( height (p - > left ) , height (p - > right ) ) ;
4 // obtem balanco de p
5 int bal = balance ( p ) ;
6 // Caso 1( a ) : rotacao direita
7 if ( bal < -1 && key < p - > left - > key )
8 return rightRotation ( p ) ;

45
 Inserção
1 Node * Tree :: fixup_node ( Node *p , int key ) {
2 // atualiza altura deste node ancestral p
3 p - > height = 1 + max ( height (p - > left ) , height (p - > right ) ) ;
4 // obtem balanco de p
5 int bal = balance ( p ) ;
6 // Caso 1( a ) : rotacao direita
7 if ( bal < -1 && key < p - > left - > key )
8 return rightRotation ( p ) ;
9 // Caso 1( b ) : rotacao dupla direita
10 else if ( bal < -1 && key > p - > left - > key ) {
11 p - > left = leftRotation (p - > left ) ;
12 return rightRotation ( p ) ;
13 }

45
 Inserção
1 Node * Tree :: fixup_node ( Node *p , int key ) {
2 // atualiza altura deste node ancestral p
3 p - > height = 1 + max ( height (p - > left ) , height (p - > right ) ) ;
4 // obtem balanco de p
5 int bal = balance ( p ) ;
6 // Caso 1( a ) : rotacao direita
7 if ( bal < -1 && key < p - > left - > key )
8 return rightRotation ( p ) ;
9 // Caso 1( b ) : rotacao dupla direita
10 else if ( bal < -1 && key > p - > left - > key ) {
11 p - > left = leftRotation (p - > left ) ;
12 return rightRotation ( p ) ;
13 }
14 // Caso 2( a ) : rotacao esquerda
15 else if ( bal > 1 && key > p - > right - > key )
16 return leftRotation ( p ) ;

45
 Inserção
1 Node * Tree :: fixup_node ( Node *p , int key ) {
2 // atualiza altura deste node ancestral p
3 p - > height = 1 + max ( height (p - > left ) , height (p - > right ) ) ;
4 // obtem balanco de p
5 int bal = balance ( p ) ;
6 // Caso 1( a ) : rotacao direita
7 if ( bal < -1 && key < p - > left - > key )
8 return rightRotation ( p ) ;
9 // Caso 1( b ) : rotacao dupla direita
10 else if ( bal < -1 && key > p - > left - > key ) {
11 p - > left = leftRotation (p - > left ) ;
12 return rightRotation ( p ) ;
13 }
14 // Caso 2( a ) : rotacao esquerda
15 else if ( bal > 1 && key > p - > right - > key )
16 return leftRotation ( p ) ;
17 // Caso 2( b ) : rotacao dupla esquerda
18 else if ( bal > 1 && key < p - > right - > key ) {
19 p - > right = rightRotation (p - > right ) ;
20 return leftRotation ( p ) ;
21 }

45
 Inserção
1 Node * Tree :: fixup_node ( Node *p , int key ) {
2 // atualiza altura deste node ancestral p
3 p - > height = 1 + max ( height (p - > left ) , height (p - > right ) ) ;
4 // obtem balanco de p
5 int bal = balance ( p ) ;
6 // Caso 1( a ) : rotacao direita
7 if ( bal < -1 && key < p - > left - > key )
8 return rightRotation ( p ) ;
9 // Caso 1( b ) : rotacao dupla direita
10 else if ( bal < -1 && key > p - > left - > key ) {
11 p - > left = leftRotation (p - > left ) ;
12 return rightRotation ( p ) ;
13 }
14 // Caso 2( a ) : rotacao esquerda
15 else if ( bal > 1 && key > p - > right - > key )
16 return leftRotation ( p ) ;
17 // Caso 2( b ) : rotacao dupla esquerda
18 else if ( bal > 1 && key < p - > right - > key ) {
19 p - > right = rightRotation (p - > right ) ;
20 return leftRotation ( p ) ;
21 }
22 return p ;
23 }
45
Remoção

46
Remoção em árvores AVL

• A remoção também pode ser feita em O(log n).

• Após a exclusão da chave, verificamos se a árvore se tornou desregulada.

• Assim como na inserção, os nós a serem examinados pertencem ao

caminho da raiz até uma de suas folhas.

• Ao contrário da inserção, agora o número de rotações necessárias para a

regulagem da árvore pode atingir O(log n).

47
Algoritmo de remoção em árvores AVL
1. Fazemos uma busca pelo nó a ser removido.

48
Algoritmo de remoção em árvores AVL
1. Fazemos uma busca pelo nó a ser removido.

2. Se o nó encontrado for nulo, então a árvore é vazia ou a chave não existe
na árvore. Não há o que remover neste caso.

48
Algoritmo de remoção em árvores AVL
1. Fazemos uma busca pelo nó a ser removido.

2. Se o nó encontrado for nulo, então a árvore é vazia ou a chave não existe
na árvore. Não há o que remover neste caso.

3. Caso contrário, uma vez encontrado o nó x com a chave desejada,

tratamos de removê-lo da árvore. Há somente dois casos a considerar:

48
Algoritmo de remoção em árvores AVL
1. Fazemos uma busca pelo nó a ser removido.

2. Se o nó encontrado for nulo, então a árvore é vazia ou a chave não existe
na árvore. Não há o que remover neste caso.

3. Caso contrário, uma vez encontrado o nó x com a chave desejada,

tratamos de removê-lo da árvore. Há somente dois casos a considerar:
(a) Se o nó x não tiver filho direito, então o seu filho esquerdo (seja ele
vazio ou não) assume o papel de x e o nó x é liberado.

48
Algoritmo de remoção em árvores AVL
1. Fazemos uma busca pelo nó a ser removido.

2. Se o nó encontrado for nulo, então a árvore é vazia ou a chave não existe
na árvore. Não há o que remover neste caso.

3. Caso contrário, uma vez encontrado o nó x com a chave desejada,

tratamos de removê-lo da árvore. Há somente dois casos a considerar:
(a) Se o nó x não tiver filho direito, então o seu filho esquerdo (seja ele
vazio ou não) assume o papel de x e o nó x é liberado.
• Todos os ancestrais de x devem ter suas alturas atualizadas e devem ser
regulados, caso necessário, por meio de rotação apropriada.

48
Algoritmo de remoção em árvores AVL
1. Fazemos uma busca pelo nó a ser removido.

2. Se o nó encontrado for nulo, então a árvore é vazia ou a chave não existe
na árvore. Não há o que remover neste caso.

3. Caso contrário, uma vez encontrado o nó x com a chave desejada,

tratamos de removê-lo da árvore. Há somente dois casos a considerar:
(a) Se o nó x não tiver filho direito, então o seu filho esquerdo (seja ele
vazio ou não) assume o papel de x e o nó x é liberado.
• Todos os ancestrais de x devem ter suas alturas atualizadas e devem ser
regulados, caso necessário, por meio de rotação apropriada.
(b) Se o nó x tiver filho direito, trocamos a chave de x com a chave do seu
nó sucessor e o nó sucessor é liberado.

48
Algoritmo de remoção em árvores AVL
1. Fazemos uma busca pelo nó a ser removido.

2. Se o nó encontrado for nulo, então a árvore é vazia ou a chave não existe
na árvore. Não há o que remover neste caso.

3. Caso contrário, uma vez encontrado o nó x com a chave desejada,

tratamos de removê-lo da árvore. Há somente dois casos a considerar:
(a) Se o nó x não tiver filho direito, então o seu filho esquerdo (seja ele
vazio ou não) assume o papel de x e o nó x é liberado.
• Todos os ancestrais de x devem ter suas alturas atualizadas e devem ser
regulados, caso necessário, por meio de rotação apropriada.
(b) Se o nó x tiver filho direito, trocamos a chave de x com a chave do seu
nó sucessor e o nó sucessor é liberado.
• Todos os nós que estiverem no caminho do antigo pai do sucessor de x
até a raiz da árvore devem ter suas alturas atualizadas e devem ser
regulados, caso necessário, por meio de rotação apropriada.

48
Análise do balanceamento na remoção

• Os únicos nós que podem ter se tornado desregulados após a remoção são
os ancestrais do nó fisicamente removido.

• Analisaremos os casos que podem influenciar no fator de balanceamento

de um nó p quando um nó x é removido do lado esquerdo de p.

49
Análise do balanceamento na remoção

• Os únicos nós que podem ter se tornado desregulados após a remoção são
os ancestrais do nó fisicamente removido.

• Analisaremos os casos que podem influenciar no fator de balanceamento

de um nó p quando um nó x é removido do lado esquerdo de p.

Atenção: Os casos em que o nó x é removido do lado direito de p são

simétricos aos apresentados nestes slides, e sua análise e exame será
deixada como exercı́cio para casa.

49
Análise do balanceamento na remoção

Caso 1: As alturas das subárvores do nó p eram iguais.

A altura permanece inalterada.

Nenhuma regulagem é necessária aqui, e nem será futuramente.

50
Análise do balanceamento na remoção

Caso 2: Remoção da subárvore mais alta de p.

A altura diminui.
Nenhuma regulagem é necessária aqui. Porém, algum ancestral de p pode
ter se tornado desregulado.

51
Análise do balanceamento na remoção

Caso 3: Removendo x da subárvore mais baixa de p. Antes da remoção de

x, balanco(p) = +1 e após a remoção, balanco(p) = +2.

Há três subcasos a considerar, dependendo do fator de balanceamento do

filho direito da raiz p, que pode ser 0, +1 ou −1.

52
Análise do balanceamento na remoção
Caso 3(a): Filho direito de p tem balanço = 0.
Antes da remoção de x, balanço(p) = +1 e, após, balanço(p) = +2.

Solução: Rotação esquerda em p.

Os balanços são ajustados!
A altura permanece inalterada.
Nenhuma regulagem acontecerá mais.

53
Análise do balanceamento na remoção
Caso 3(b): Filho direito de p tem balanço = +1.
Antes da remoção de x, balanço(p) = +1 e, após, balanço(p) = +2.

Solução: Rotação esquerda em p.

Os balanços são ajustados!
A altura diminui (algum ancestral pode ter se tornado desregulado).

54
Análise do balanceamento na remoção
Caso 3(c): Filho direito de p tem balanço = −1.
Antes da remoção de x, balanço(p) = +1 e, após, balanço(p) = +2.

Solução: Rotação esquerda dupla no p.

Os balanços são ajustados!
A altura diminui (algum ancestral pode ter se tornado desregulado).

55
Remoção — Exercı́cio 1
Excluir o nó 28 e fazer as regulagens para manter a árvore AVL.

57

21 88

13 28 70 90

16 65 73 92

64

56
Remoção — Exercı́cio 2
Excluir a chave 61 e, depois, a chave 10 da árvore abaixo e fazer as
regulagens necessárias.
50

21 83

10 27 61 95

7 14 24 55 70 90 99

5 53 57 71 97

52 54 56 58

57
 Remoção — Função Pública

1 void avl_tree :: remove ( int key ) {

2 root = remove ( root , key ) ;
3 }

58
 Remoção – Função privada que busca o nó
1 Node * avl_tree :: remove ( Node * node , int key ) {
2 if ( node == nullptr ) // node nao encontrado
3 return nullptr ;

59
 Remoção – Função privada que busca o nó
1 Node * avl_tree :: remove ( Node * node , int key ) {
2 if ( node == nullptr ) // node nao encontrado
3 return nullptr ;
4 if ( key < node - > key )
5 node - > left = remove ( node - > left , key ) ;
6 else if ( key > node - > key )
7 node - > right = remove ( node - > right , key ) ;

59
 Remoção – Função privada que busca o nó
1 Node * avl_tree :: remove ( Node * node , int key ) {
2 if ( node == nullptr ) // node nao encontrado
3 return nullptr ;
4 if ( key < node - > key )
5 node - > left = remove ( node - > left , key ) ;
6 else if ( key > node - > key )
7 node - > right = remove ( node - > right , key ) ;
8 // encontramos no node
9 else if ( node - > right == nullptr ) { // sem filho direito
10 Node * child = node - > left ;
11 delete node ;
12 return child ;
13 }
14 else // tem filho direito : troca pelo sucessor
15 node - > right = r e m ov e _ s u c c e s s o r ( node , node - > right ) ;

59
 Remoção – Função privada que busca o nó
1 Node * avl_tree :: remove ( Node * node , int key ) {
2 if ( node == nullptr ) // node nao encontrado
3 return nullptr ;
4 if ( key < node - > key )
5 node - > left = remove ( node - > left , key ) ;
6 else if ( key > node - > key )
7 node - > right = remove ( node - > right , key ) ;
8 // encontramos no node
9 else if ( node - > right == nullptr ) { // sem filho direito
10 Node * child = node - > left ;
11 delete node ;
12 return child ;
13 }
14 else // tem filho direito : troca pelo sucessor
15 node - > right = r e m ov e _ s u c c e s s o r ( node , node - > right ) ;
16
17 // Atualiza a altura do node e regula o node
18 node = fix up_delet ion ( node ) ;
19 return node ;
20 }

59
 Remoção
Função privada que remove o sucessor

1 Node * avl_tree :: r em o v e _ s u c c e s s o r ( Node * root , Node * node ) {

2 if ( node - > left != nullptr )
3 node - > left = r e m o v e _ s u c c e s s o r ( root , node - > left ) ;
4 else {
5 root - > key = node - > key ;
6 Node * aux = node - > right ;
7 delete node ;
8 return aux ;
9 }
10 // Atualiza a altura do node e regula o node
11 node = fix up_delet ion ( node ) ;
12 return node ;
13 }

60
 Remoção — Função privada de rebalanceamento
1 Node * avl_tree :: fixup_d eletion ( Node * node ) {
2 node - > height =
3 1 + max ( height ( node - > left ) , height ( node - > right ) ) ;
4
5 int bal = balance ( node ) ;
6
7 // node pode estar desregulado , ha 4 casos a considerar
8 if ( bal > 1 && balance ( node - > right ) >= 0) {
9 return leftRotation ( node ) ;
10 }
11 else if ( bal > 1 && balance ( node - > right ) < 0) {
12 node - > right = rightRotation ( node - > right ) ;
13 return leftRotation ( node ) ;
14 }
15 else if ( bal < -1 && balance ( node - > left ) <= 0) {
16 return rightRotation ( node ) ;
17 }
18 else if ( bal < -1 && balance ( node - > left ) > 0) {
19 node - > left = leftRotation ( node - > left ) ;
20 return rightRotation ( node ) ;
21 }
22 return node ;
23 }
61
FIM

62