Write short notes on: i) AVL tree ii) Minimum cost spanning tree using Huffman codes. iii) Sparse matrix and its implementation

Q.) Write short notes on: i) AVL tree ii) Minimum cost spanning tree using Huffman codes. iii) Sparse matrix and its implementation

 Subject: Data Structure and Algorithm

i) AVL tree

An AVL tree is a self-balancing binary search tree where the difference between the heights of the left and right subtrees is at most one. This ensures that the tree remains balanced even after insertions and deletions, resulting in efficient searching and retrieval operations. The height of an AVL tree is always O(log n), where n is the number of nodes in the tree.

The following operations are performed to maintain the balance of an AVL tree:

  1. Insertion: When a new node is inserted into the tree, the balance factors of the affected nodes are checked. If the balance factor of a node becomes greater than 1 or less than -1, a rotation is performed to restore the balance.

  2. Deletion: When a node is deleted from the tree, the balance factors of the affected nodes are checked. If the balance factor of a node becomes greater than 1 or less than -1, a rotation is performed to restore the balance.

ii) Minimum cost spanning tree using Huffman codes

Huffman coding is a lossless data compression algorithm that assigns variable-length codes to symbols based on their frequency of occurrence. The more frequent a symbol, the shorter its code. This allows for efficient compression of data.

Huffman codes can be used to construct a minimum cost spanning tree (MCST) for a given set of weighted edges. The MCST is a tree that connects all the vertices in the graph while minimizing the total weight of the edges in the tree.

The steps involved in constructing an MCST using Huffman codes are as follows:

  1. Assign a Huffman code to each vertex in the graph.
  2. Construct a new graph where each edge is weighted by the sum of the weights of the edges in the original graph that correspond to the Huffman codes of its endpoints.
  3. Find the MCST of the new graph.
  4. The MCST of the new graph is also the MCST of the original graph.

iii) Sparse matrix and its implementation

A sparse matrix is a matrix in which most of the elements are zero. Sparse matrices are often encountered in scientific and engineering applications, where large systems of linear equations need to be solved.

There are several ways to implement sparse matrices, but the most common is the compressed sparse row (CSR) format. In the CSR format, the matrix is stored as a list of three arrays:

  1. row_pointers: This array contains the starting indices of the rows in the other two arrays.
  2. col_indices: This array contains the column indices of the nonzero elements in the matrix.
  3. values: This array contains the values of the nonzero elements in the matrix.

The CSR format allows for efficient storage and retrieval of the nonzero elements in a sparse matrix. It also enables efficient operations such as matrix-vector multiplication and matrix-matrix multiplication.