Linked Lists, Trees, and Huffman Coding: A Comprehensive Guide

Posted on May 7, 2024 in Computers

Unit 2: Types of Linked Lists

1. Singly Linked List

Node Structure

class Node:
  data
  next

Functions

  • createNode(value): Creates a new node with the given value.
  • insertAtEnd(head, value): Inserts a node at the end of the linked list.
  • deleteNode(head, value): Deletes a node with the specified value.
  • printList(head): Traverses and prints the linked list.

2. Doubly Linked List

Node Structure

class Node:
  data
  next
  prev

Functions

  • createNode(value): Creates a new node with the given value.
  • insertAtEnd(head, value): Inserts a node at the end of the doubly linked list.
  • insertAtBeginning(head, value): Inserts a node at the beginning of the doubly linked list.
  • deleteNode(head, value): Deletes a node with the specified value.
  • printListForward(head): Traverses and prints the doubly linked list forward.
  • printListBackward(tail): Traverses and prints the doubly linked list backward.

3. Circular Linked List

Node Structure

class Node:
  data
  next

Functions

  • createNode(value): Creates a new node with the given value.
  • insertAtEnd(head, value): Inserts a node at the end of the circular linked list.
  • deleteNode(head, value): Deletes a node with the specified value.
  • printList(head): Traverses and prints the circular linked list.

Unit 3: Trees

Binary Tree Creation using Linked List

Node Structure

Structure Node:
  value
  left_child
  right_child

Functions

  • createNode(value): Creates a new node with the given value.
  • insertLeft(parent, value): Inserts a node as the left child of the parent node.
  • insertRight(parent, value): Inserts a node as the right child of the parent node.
  • createBinaryTree(): Creates a binary tree with specified values.

Implementation of Tree Traversal (Recursive)

Node Structure

struct TreeNode:
  int val
  TreeNode left
  TreeNode right

Functions

  • preOrderTraversal(node): Performs recursive pre-order traversal.
  • inOrderTraversal(node): Performs recursive in-order traversal.
  • postOrderTraversal(node): Performs recursive post-order traversal.

Printing Tree Level Wise (Recursive)

Node Structure

struct TreeNode:
  int val
  TreeNode left
  TreeNode right

Functions

  • height(node): Calculates the height of the tree.
  • printLevel(node, level): Prints nodes at a given level.
  • printTreeLevelWise(root): Prints the tree level-wise.

Counting Leaf Nodes of BST with Recursion

Node Structure

struct TreeNode:
  int val
  TreeNode left
  TreeNode right

Functions

  • countLeafNodes(node): Counts leaf nodes in a BST.

Finding Height of BST (Recursive and Non-Recursive)

Node Structure

struct TreeNode:
  int val
  TreeNode left
  TreeNode right

Functions

  • findHeight(node): Finds the height of a BST recursively.
  • findHeight(root): Finds the height of a BST without recursion.

Unit 4: Threaded Binary Tree (TBT) and AVL Tree

Threaded Binary Tree (TBT)

A threaded binary tree is a binary tree in which every node contains an additional thread (a link) to either the in-order successor or the in-order predecessor. This concept was introduced to optimize certain operations on binary trees, particularly traversal.

Implementation of TBT

class Node:
  data
  left
  right
  right_thread

class ThreadedBinaryTree:
  root

# ... (Functions for insertion and inorder traversal)

AVL Tree (Adelson-Velsky and Landis Tree)

An AVL tree is a self-balancing binary search tree (BST) where the heights of the two child subtrees of any node differ by at most one. This balance is maintained through rotations (LL, RR, LR, RL) during insertions and deletions.

Heap

A heap is a tree-based data structure that satisfies the heap property. There are two types of heaps:

  1. Max Heap: The value of each node is greater than or equal to the values of its children.
  2. Min Heap: The value of each node is less than or equal to the values of its children.

Huffman Tree

A Huffman tree is a binary tree used for data compression, specifically in Huffman coding. It assigns variable-length codes to input characters, with shorter codes assigned to more frequent characters.

Working

  1. Frequency Analysis: Analyze the input data and determine the frequency of each symbol.
  2. Create Huffman Tree: Build a binary tree based on the frequencies of the symbols.
  3. Assign Codes: Traverse the Huffman tree to assign variable-length binary codes to each symbol.
  4. Generate Huffman Codes: The binary codes represent the compressed form of the input data.
  5. Compression and Decompression: Replace each symbol in the input data with its corresponding Huffman code to compress the data. Use the Huffman tree to decode the compressed data and reconstruct the original input.