Page 193 - DCAP407_DATA_STRUCTURE

Data Structure

10.2.3 2-3 Trees
A 2-3 tree is another type of tree which has 2 types of nodes, 2-node and 3-node.

The figure 10.14 represents a 2-node tree.
Figure 10.14: A 2-Node Tree

The 2-node structure shown in figure 8.14 has one data element and two children. Every 2-node must
have the following properties:
1. Every value appearing in the child P must be ≤X.
2. Every value appearing in the child Q must be ≥X.
3. The length of the path from the root of a 2-node to every leaf in its child must be the same.

The figure 10.15 represents a 3-node tree.

Figure 10.15: A 3-Node Tree

The 3-node structure shown in figure 10.15 has two data elements and three children. Every 3-node
must have the following properties:

1. Every value appearing in child P must be ≤ X.
2. Every value appearing in child Q must be in between X and Y.
3. Every value appearing in child R must be ≥ Y.
4. The length of the path from the root of a 3-node to every leaf in its child must be the same.
10.2.4 Huffman Trees

Huffman codes are digital data compression codes which were devised by Prof. David A. Huffman
(1925-1999). Huffman codes provide good compression ratios. Even today, after 50 years, Huffman
codes are very useful. Huffman compression is a compression technique in which there is no loss of
information when the data is compressed i.e., after we decompress the data, the original information
can be retrieved. Hence, it is named as ‘lossless compression’. Lossless compression is desired in
compressing text documents, bank records, and so on.

186 LOVELY PROFESSIONAL UNIVERSITY