Unit IV Trees and Graphs (1)

Unit IV

• Overview of Trees and Graphs

Trees

• Definition: A tree data structure is a hierarchical structure that organizes data for easy navigation and search.

• Structure: Composed of nodes and edges, demonstrating a hierarchical relationship where the topmost node is termed the root, and other nodes are termed child nodes.

• Characteristics: Nodes can have multiple children, forming a recursive structure.

Tree Concepts

Node

• An entity containing a key/value and pointers to child nodes.

• Leaf Nodes: Last nodes in any path, have no children.

• Internal Nodes: Nodes with at least one child.

Edge

• The connection/link between any two nodes.

Root

• The Topmost Node of a tree.

Height of a Tree

• Height is determined by the depth of the deepest node or the height of the root node.

Tree Applications

• Binary Search Trees (BSTs): For quick element presence checks in a set.

• Heaps: Used for efficient sorting.

• Tries: Modified tree structures in routers for storing routing information.

• Databases: Utilize B-Trees and T-Trees for enhanced data management.

• Compilers: Syntax trees validate programming code syntax.

• File Systems: Facilitate efficient navigation and organization of files.

• Data Compression: Huffman coding employs binary trees for compressing data.

Basic Operations of Tree Data Structure

Create

• Establishing a new tree.

Insert

• Adding data to the tree.

Search

• Finding specific data within the tree.

Traversal Methods

• Preorder Traversal: (Root, Left, Right)

• Inorder Traversal: (Left, Root, Right)

• Postorder Traversal: (Left, Right, Root)

Traversal Results

• Inorder: D, B, E, A, F, C, G

• Preorder: A, B, D, E, C, F, G

• Postorder: D, E, B, F, G, C, A

Types of Trees

• Binary Tree

• Binary Search Tree

• AVL Tree

• B-Tree

Binary Tree

• A hierarchical structure where each node has at most two children (left and right).

• Utilized for efficient data storage, retrieval, and various operations (insertion, deletion, traversal).

Representation of a Binary Tree

• Linear (Array) Representation

• Linked List Representation

Structure of a Node in a Binary Tree

• typedef struct BTree { int data; struct BTree *lchild; struct BTree *rchild; } node;

Expression Trees

• Definition: A binary tree where each internal node is an operator and each leaf node is an operand.

• Construction Process:

  1. Use a stack to process input expressions.

  2. Push operands onto the stack.

  3. For operators, pop two values, create a parent node, and push back to the stack.

  4. Convert expressions to postfix to form the tree then traverse in-order for results.

Binary Search Trees (BST)

• Properties:

  • Left sub-tree values are less than or equal to the parent node's key.

  • Right sub-tree values are greater than or equal to the parent node's key.

Height-Balanced Binary Trees

• Defined by the property that any node's left and right subtree heights differ by no more than 1.

• Height Definition: Length of the longest path from a node to a leaf.

AVL Trees

• An AVL Tree is a height-balanced BST where each node has a balance factor (height of left subtree - height of right subtree).

• Balance Factor Ranges:

  • -1: Left subtree is one level lower.

  • 0: Subtrees are equal height.

  • +1: Right subtree is one level lower.

Multi-way Trees

• Generalized binary trees allowing multiple elements in each node.

• Characteristics:

  • Nodes can have multiple keys and children; 2-3-4 trees keep leaves at the same level.

B-Trees

• Self-balancing trees designed for handling massive data efficiently.

• Each node contains multiple keys, resulting in a larger branching factor and shallower height.

• Properties:

  • Nodes must maintain a sorted data arrangement and a specific number of children and keys, ensuring balanced paths among leaf nodes.

Inserting into a B-Tree

• Example insertion sequence: 5, 3, 21, 9, 13, 22, 7, 10, 11, 14, 8, 16.