-
Gabarito, letra B
Primeiramente transforma os valores binários em decimais, para facilitar a visualização:
.........32........16........8.........4.........2..........1
A=.... 0.........1..........1.........0..........0..........1 = 25
B=....1..........1..........0.........0..........1..........0 = 50
C=....1..........0..........0.........1..........0..........1 = 37
D=....0..........0..........1.........0..........1..........1 = 11
E=....0..........1..........1.........0..........1..........0 = 26
F=....1..........1..........0.........1..........0..........1 = 53
Agora construímos a árvore onde os maiores valores são encaixados nas subárvores direita e os menores nas subárvores esquerdas, que fica:
......................................25........................................................ Raiz = 0
................................/........... \....................................................
.............................11 ............50 ...............................................altura = 1
........................................./............\...........................................
.....................................37...............53..................................... altura = 2
..................................../............................................................
.................................26........................................................... altura = 3
A altura de uma árvore é a distância de sua raiz (0) até a o seu nó folha (nó sem filhos) mais distante, no caso 3.
fonte: Estrutura de dados e seus algoritmos, Jayme Szwarcfiter. 3ª Ed.
instagram: @papirobizurado
-
Gabarito B
Excelente explicação do companheiro Irvin BM !
"Retroceder Nunca Render-se Jamais !"
Força e Fé !
Fortuna Audaces Sequitur !
-
A inserção na árvore Patricia (Compressed Trie) é realizada a partir dos bits. Assim, após as duas primeiras inserções, a árvore fica:
...................................RAIZ....................................................... Raiz = 0
................................/........... \....................................................
.........................011001 ....110010 ............................................altura = 1
Isso porque pelo bit 0 a inserção ocorre à esquerda; pelo bit 1 à direita. A terceira inserção (100101) começa pelo bit 1. Assim ocorrerá a divisão do lado direito da árvore, que fica assim:
...................................RAIZ....................................................... Raiz = 0
................................/........... \....................................................
.........................011001..........1.................................................altura = 1
........................................./............\...........................................
...................................00101.....10010..................................... altura = 2
A árvore final fica da seguinte forma:
...................................RAIZ....................................................... Raiz = 0
............................/.................... \...............................................
...........................0......................1.............................................altura = 1
....................../..........\.........../............\.......................................
................01011......110....00101.......10................................... altura = 2
.............................../......\................./........\................................
.............................01......10..........010......101............................altura = 3
-
Força Guerreiro!!!!!!