Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees...

Question 1

Question

Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees...

Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees T and T? with T=T? (interpreting = as structural equality), we store (w.l.o.g.) T and replace all pointers to T? with pointers to T. See uli's answer for an example.

Give an algorithm that takes a tree in the above sense as input and computes the (minimal) number of nodes that remain after compression. The algorithm should run in time O(nlogn) (in the uniform cost model) with n the number of nodes in the input.

This has been an exam question and I have not been able to come up with a nice solution, nor have I seen one.

engineering Computer-Science

Add a comment Improve this question Transcribed image text

Answer

Similar Homework Help Questions

(b.) Huffman code is a way to encode information using variable-length binary strings to represent symbols depending on the frequency of each individual letter. Specifically, letters that appear more...

(b.) Huffman code is a way to encode information using variable-length binary strings to represent symbols depending on the frequency of each individual letter. Specifically, letters that appear more frequently can be encoded into strings of shorter lengths, while rarer letters can be turned into longer binary strings. On average, Huffman code is a more efficient way to encode a message as the number of bits in the output string will be shorter than if a fixed-length code was used....

Question 2

(b.) Huffman code is a way to encode information using variable-length binary strings to represent symbols depending on the frequency of each individual letter. Specifically, letters that appear more...

(b.) Huffman code is a way to encode information using variable-length binary strings to represent symbols depending on the frequency of each individual letter. Specifically, letters that appear more frequently can be encoded into strings of shorter lengths, while rarer letters can be turned into longer binary strings. On average, Huffman code is a more efficient way to encode a message as the number of bits in the output string will be shorter than if a fixed-length code was used....

Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees...

Homework Answers

Request Answer!

Add Answer to:
Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees...

Post as a guest

Earn Coins

(b.) Huffman code is a way to encode information using variable-length binary strings to represent symbols depending on the frequency of each individual letter. Specifically, letters that appear more...

Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees...

Homework Answers

Request Answer!

Add Answer to: Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees...

Post as a guest

Earn Coins

(b.) Huffman code is a way to encode information using variable-length binary strings to represent symbols depending on the frequency of each individual letter. Specifically, letters that appear more...

Add Answer to:
Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees...