Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 4: Problem 30

Show that a binary tree corresponding to an optimal binary prefix code must be full. A full binary tree is a binary tree such that every node is either a leaf or it has two children.

Short Answer

Expert verified
The proof by contradiction shows that any binary tree corresponding to an optimal binary prefix code must be a full binary tree; otherwise, a tree with a shorter code length could be constructed, contradicting the optimality of the original tree.

Step by step solution

01

Proof assumption and contradiction

Assume that there exists an optimal binary prefix code corresponding to a binary tree which is not a full binary tree. A non-full binary tree will have at least one node with only one child. Let's consider one such node. We label the one child of this node as \(N1\) and we label the sibling node, if it exists, as \(N2\).
02

Modifying the tree

Next, a new binary tree is created by removing node \(N1\) and assign its child directly to node \(N1\)'s parent. This means that no node in this new tree has only one child, essentially creating the required full binary tree.
03

Exploring Code Length

The effect on the overall length of the binary prefix code by this modification is that the codeword for the child of \(N1\) is now shorter by one bit. Thus, the overall length of the new tree's code is less than or equal to the original tree.
04

Contradiction and Conclusion

But it contradicts our initial assumption that the original binary tree was optimal since there existed another binary tree with equivalent or shorter code length. Hence, a binary tree corresponding to an optimal binary prefix code has to be full.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Show that the worst-case number of entries computed by the refined dynamic programming algorithm for the 0 -1 Knapsack problem is in \(\Omega\) \(\left(2^{n}\right) .\) Do this by considering the instance in which \(W=2^{n}-2\) and \(w_{i}=2^{i-1}\) for \(1 \leq i \leq n\).

Draw a graph that has more than one minimum spanning tree.

Prove that the greedy approach to the Fractional Knapsack problem yields an optimal solution.

Show with a counterexample that the greedy approach does not always yield an optimal solution for the Change problem when the coins are U.S. coins and we do not have at least one of each type of coin.

Assume that in a network of computers any two computers can be linked. Given a cost estimate for each possible link, should Algorithm 4.1 (Prim's algorithm) or Algorithm 4.2 (Kruskal's algorithm) be used? Justify your answer.
See all solutions

Recommended explanations on Computer Science Textbooks

Data Representation in Computer Science

Read Explanation

Problem Solving Techniques

Read Explanation

Big Data

Read Explanation

Theory of Computation

Read Explanation

Data Structures

Read Explanation

Functional Programming

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free