Construa a árvore binária com os códigos de prefixo que representam estes esquemas de codificação.
a: 11, e: (0, t: 101, s: 100)
a: 11, e: (0, t: 101, s: 100)
Passo 1
O enunciado pede para construir a árvore binária de prefixo que representa o código dado pelos pares
.
O assunto aqui é a construção de uma trie (árvore de prefixos), onde cada aresta leva a 0 (filho esquerdo) ou 1 (filho direito), e cada símbolo fica em uma folha.
O assunto aqui é a construção de uma trie (árvore de prefixos), onde cada aresta leva a 0 (filho esquerdo) ou 1 (filho direito), e cada símbolo fica em uma folha.
Passo 2
Definimos o procedimento de inserção de cada símbolo na árvore:
— Para cada bit do código, a partir da raiz seguimos à esquerda se for 0 e à direita se for 1.
— Se não existir nó, criamos um nó interno.
— Ao consumirmos todos os bits, colocamos o símbolo nessa folha.
— Para cada bit do código, a partir da raiz seguimos à esquerda se for 0 e à direita se for 1.
— Se não existir nó, criamos um nó interno.
— Ao consumirmos todos os bits, colocamos o símbolo nessa folha.
Passo 3
Inserção dos símbolos:
— com código
: da raiz vai-se à esquerda e coloca-se a folha
.
— com código
: da raiz vai-se à direita (1), depois à direita (1) e põe-se a folha
.
— com código
: raiz→direita(1)→esquerda(0)→esquerda(0) e põe-se a folha
.
— com código
: raiz→direita(1)→esquerda(0)→direita(1) e põe-se a folha
.
—
—
—
—
Passo 4
A árvore resultante, indicando em cada aresta o bit associado, fica assim (as folhas são os símbolos):
[raiz]
/
0───┘ └───1
e ●
/
0───┘ └───1
● a
/
0───┘ └───1
s t
/
0───┘ └───1
e ●
/
0───┘ └───1
● a
/
0───┘ └───1
s t
Resposta
A árvore binária de prefixo é:
[raiz]
/
0───┘ └───1
e ●
/
0───┘ └───1
● a
/
0───┘ └───1
s t
/
0───┘ └───1
e ●
/
0───┘ └───1
● a
/
0───┘ └───1
s t