unit4

UNIT IV: Trees

Introduction

• Trees represent hierarchical relationships between individual data elements.

• Non-linear data structure, differentiating trees from linear data structures like arrays, stacks, queues, and linked lists.

• Graphs, as unrestricted trees, show similar hierarchical relationships.

• Definition of a tree: A finite set of nodes with a designated root and subtrees.

Properties of Trees

• Root: Top node with no parent; must exist in any tree.

• Edges: Connections between nodes; in a tree with N nodes, there are at most N-1 edges.

• Parent and Child Nodes: Parent nodes have branches to child nodes; each child node has at most one parent.

• Siblings: Nodes sharing the same parent.

• Leaf Nodes: Terminal nodes with no children.

• Internal Nodes: Nodes with at least one child; root is an internal node if it has children.

Tree Terminology

1. Degree: Total number of children of a node.

2. Level: Starting from root at level 0, increments downward.

3. Height: Longest path from a leaf node to a specific node.

4. Depth: Total edges from root to a particular node.

5. Path: Sequence of nodes and edges between two nodes.

6. Subtree: Any child node forms a subtree encapsulating further child nodes.

Advantages of Trees

• Reflect structural relationships among data.

• Efficient for insertion and searching.

• Flexible; allows relocation of subtrees with ease.

Tree Representations

1. List Representation: Nodes linked with data nodes and reference nodes.

2. Left Child - Right Sibling Representation: Each node has a data field, a left child reference, and a right sibling reference.

   • This maintains the hierarchical structure with pointers facilitating navigation.

Binary Trees

• Special tree structure where each node can have a maximum of two children (left and right).

Types of Binary Trees

1. Strictly Binary Tree: Every internal node has exactly two children or none.

2. Complete Binary Tree: Every internal node has two children; all leaf nodes on the same level.

3. Extended Binary Tree: Binary trees with dummy nodes added to fulfill full binary tree conditions.

Abstract Data Type (ADT) for Binary Trees

• A binary tree is defined as a set either empty or with a root and two binary trees (left/right).

• Key operations:

  • Create(): Create an empty binary tree.

  • IsEmpty(bt): Check if tree is empty.

  • MakeBT(bt1, item, bt2): Create a new binary tree with specified subtrees.

Properties of Binary Trees

• Maximum number of nodes at level i: 2^i - 1.

• Relationship between leaf and degree-2 nodes in a binary tree: leaf nodes = degree-2 nodes + 1.

Binary Tree Traversals

1. In-order Traversal (left - root - right):

   • Visits nodes in a sequence where root is visited between its children.

2. Pre-order Traversal (root - left - right):

   • Visits root before its children, captures tree structure.

3. Post-order Traversal (left - right - root):

   • Visits children before their parent, useful for deletions.

4. Level-order Traversal: Implemented using queues to traverse nodes level by level.

Binary Search Trees (BST)

• Each node's left child must have a lesser value; right child must have a greater value.

• Basic operations include search, insertion, deletion, and calculating height.

Searching in a BST

• Recursive and iterative search algorithms target left or right subtrees based on comparisons with the root's key.

Insertion into a BST

• Locate the point in the tree for a new node based on comparisons.

• Always insert nodes as leaf nodes.

Deletion from a BST

• Three cases determine the method of deletion:

  1. Leaf Node: Direct removal.

  2. One Child Node: Link child to parent's parent.

  3. Two Children Node: Replace with largest node from left subtree or smallest node from the right subtree.

Height of a Binary Tree

• The height is defined based on the depth of nodes and is calculated recursively.