Tree Data Structures Lecture Notes

Introduction to Data Structures

• Data Structure: Organization of data for efficient processing.
• Categories:
  • Linear Data Structures: Arrays, Linked Lists, Queues, Stacks.
  • Non-Linear Data Structures: Trees and Graphs.

Understanding Linear vs Non-Linear Data Structures

• Linear Data Structures: Sequential arrangement (single level).
• Non-Linear Data Structures: Hierarchical arrangement (multiple levels).

Hierarchical Data Example

• Example of a College Employee Structure:
  • Director
    • Deans (A, B, C)
      • HODs
        • Faculty Members

Trees: Definition and Context

• Tree: A non-linear data structure simulating hierarchy.
• Contextual Considerations:
  • Graph theory: Undirected, connected, acyclic.
  • Data structure: Directed (top to bottom).

Tree Structure Representation

• Root Node: Topmost element, has no parent.
• Nodes: Contain information and connections to other nodes.
• Parent Node: Immediate predecessor of a node.
• Child Node: Immediate successor of a node.
  • Example: Parent of G is C, children of A are B, C, D.
• Leaf Node: A node with no children (also known as external nodes).
• Non-Leaf Node: A node with at least one child (internal nodes).

Key Terminologies

• Path: Sequence of edges between nodes.
  • E.g., Path from A to L: A -> C -> G -> L.
• Ancestor and Descendant:
  • Ancestor: Predecessor nodes on the path from root.
  • Descendant: Successor nodes on the path to leaf nodes.
• Sibling: Nodes with the same parent.
• Degree of a Node: Number of children of that node.
• Depth of a Node: Number of edges from root to that node.
• Height of a Node: Length of path from that node to its furthest leaf node.
• Level of a Node: Distance from root to the node.

Properties of Trees

• In a tree with n nodes, there are n - 1 edges.
• Trees must be acyclic (no cycles).

Implementing Trees in Memory

• Node Representation: Contains data and links to left and right children.
• Example:
  • Struct representation with data part and two links.

Applications of Tree Data Structures

• File System Representation: Directories and files organized hierarchically.
• Routing Protocols: Uses tree structures for efficiency.
• Binary Search Trees and Heaps: For fast searching, inserting and deleting data.

Next Steps

• Next video will cover types of trees (Binary, Binary Search, AVL trees, etc.).

Conclusion

• Understanding tree structures is key to working with hierarchical data models effectively.