Qeertyiplhsgbxbehakhdhfjdhdjekshhdjskwirndb

Hshdheheh

1. Discrete Mathematical Structures COURSE CODE: AS123 PROGRAM: BSSE ILMA UNIVERSITY

2. WHAT IS TREE? In graph theory, a tree is a connected, undirected graph with no cycles. In other words, it’s a collection of nodes (also called vertices) connected by edges, where there is exactly one path between any two nodes. Key Properties of Trees: Connectedness: All nodes are reachable from any other node. Acyclic: No cycles (paths that start and end at the same node without retracing steps). Edges and Nodes: A tree with 𝑛 nodes has exactly 𝑛−1 edges. Unique Path: There is a unique path between any two nodes.

3. Types of Trees 1.Binary Tree: Each node has at most two children, typically referred to as the left and right child. 2.Binary Search Tree (BST): A binary tree where the left child node contains values less than its parent node, and the right child node contains values greater. 3.Balanced Tree: A tree where the height of the two subtrees of any node differ by no more than one. Examples include AVL trees and Red-Black trees. 4.Heap: A specialized tree-based structure that satisfies the heap property; for example, a min-heap where each parent node is less than or equal to its children. 5.Trie: A tree used to store a dynamic set of strings where common prefixes are shared.

4. 1.Data Storage and Retrieval: 1. Binary Search Trees (BSTs): Efficient for lookup, insertion, and deletion operations. Useful in databases and file systems. 2. Heaps: Used in priority queues, heapsort algorithms, and efficient graph algorithms like Dijkstra's shortest path. 2.Searching and Sorting: 1. Trie : Optimizes the retrieval of strings, used in applications such as autocomplete and spell checking. 2. Segment Trees and Binary Indexed Trees (Fenwick Trees): Used for range queries and updates in computational geometry and data analysis. 3.Network Routing: 1. Spanning Trees: Used in network design to ensure there is a path between all nodes with minimal cost (e.g., MST algorithms like Kruskal's and Prim’s). Applications of Trees

5. 4.Hierarchical Data Representation: 1. File Systems: Represent directories and files in a hierarchical manner. 2. Organizational Charts: Model the structure of organizations 5.Expression Parsing and Compilation: 1. Parse Trees: Represent the syntax of expressions or code structures in compilers. 2. Abstract Syntax Trees (ASTs): Used to represent the structure of source code in a form that is easier for a compiler to manipulate. 6.Game Theory and AI: 1. Game Trees: Model different possible moves in games like chess or tic-tac-toe, used in decision-making and strategy formulation. 7.Artificial Intelligence: 1. Decision Trees: Used for decision-making and machine learning, where decisions are made based on certain criteria. 8.Graph Algorithms: 1. Tree Traversal Algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS) are used to explore nodes and edges of a tree or graph.

6. Thank you