Scribd
Upload
4 views2 pages

Encoding Trees: Height-Based Labeling

The document outlines an encoding scheme for trees where internal nodes are labeled based on their height, with constraints on the maximum value and the presence of zeros in relation to the maximum. It discusses valid and invalid encodings, providing examples and constraints that must be adhered to. Additionally, it presents upper and lower bounds for the sum of encoded values based on the structure of the tree.

Uploaded by

smithsj0709
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views2 pages

Encoding Trees: Height-Based Labeling

The document outlines an encoding scheme for trees where internal nodes are labeled based on their height, with constraints on the maximum value and the presence of zeros in relation to the maximum. It discusses valid and invalid encodings, providing examples and constraints that must be adhered to. Additionally, it presents upper and lower bounds for the sum of encoded values based on the structure of the tree.

Uploaded by

smithsj0709
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Problem #6: Encoding Trees (20 marks)

Solution:
In the encoding scheme, every internal node is assigned a number, which is equal to its height. In other
words, the lowest internal nodes get a label of 0. The next level node gets 1, and so on. A node always
gets a label 1 more than the larger of its children’s labels. See the diagram below for an example labeling.
The number between two successive words x and y is equal to the label of the node which is the lowest
common ancestor of x and y.

Assignment 1

Tree-C: Time 3 flies 2 like 1 an 0 arrow

Tree-D: Time 0 flies 2 like 1 an 0 arrow

Assignment 2

Assignment 3

• a 0 b 2 c 0 d 2 e 1 f 0 g  a 0 b 3 c 0 d 2 e 1 f 0 g OR a 0 b 1 c 0 d 2 e 1 f 0 g
• a1b3c2d1e0fa0b3c2d1e0f
Constraints:

In the encoding a 0 b 2 c 0 d 2 e 1 f 0 g, the maximum number, which is 2, is present more than once. The
constraint it violates is “Every valid string must have one and only one maximum number.” This is because
the root of the tree, which is the topmost node, is unique and has the highest label.

a 1 b 3 c 2 d 1 e 0 f has no “0” on the left of 3 – the maximum value. Constraint it violates is “If there is
at least one number on the left/right of the maximum value, then there must be at least one 0 on the
left/right of the maximum value.” This is because the maximum value divides the tree into two sub-
trees. Any sub-tree, which is also a binary tree, must have at least one 0 in its encoding.

Assignment 4
Upper Bound:

If s: a1 x1 a2 x2 a3 … an-1 xn-1 an is a valid tree encoding, where the max{xi} is the maximum value of all xi’s,
then there must be at least one occurrence of the numbers 0, 1, 2, … max{xi} in s, because of the second
constraint stated in Assignment (3). Thus, max{xi} is bounded by n - 2. Hence, the maximum value of
∑𝑛−1 𝑥𝑖
𝑖=1 2 is achieved when s: a1 0 a2 1 a3 2… an-1 n-2 an.

Therefore,
𝑛−1

∑ 2𝑥𝑖 ≤ 20 + 21 + 22 + ⋯ + 2𝑛−2 = 2𝑛−1


𝑖=1

Lower Bound:

∑𝑛−1 𝑥𝑖
𝑖=1 2 is minimum when max{xi} is smallest, and the smaller values are repeated more often. This
happens when the tree has a balanced structure as shown below.

a0b1c0d2e0f1g0h

In such case, at least half of the xis are 0, a fourth of the xis are 1, an eighth of the xis are 2, and so on.
Therefore,
𝑛−1
𝑛 𝑛 𝑛 𝑛
∑ 2𝑥𝑖 ≥ ⌊ ⌋ 20 + ⌊ 2 ⌋ 21 + ⌊ 3 ⌋ 22 + ⋯ + ⌊ log 𝑛 ⌋ 2log2 𝑛−1
2 2 2 2 2
𝑖=1

𝑛 𝑛 𝑛 𝑛
= ⌊ ⌋+ ⌊ ⌋+ ⌊ ⌋+ ⋯+ ⌊ ⌋ (𝑎𝑡 𝑙𝑒𝑎𝑠𝑡 ⌊log 2 𝑛⌋ 𝑡𝑖𝑚𝑒𝑠)
2 2 2 2

𝑛
= ⌊log 2 𝑛⌋ ⌊ ⌋
2

You might also like