Short Notes: Trees | Programming and Data Structures - Computer Science Engineering (CSE) PDF Download

 Page 1


1 Trees in Programming and Data Structures
1.1 Introduction to Trees
A tree is a hierarchical, non-linear data structure consisting of nodes connected by edges.
Each tree has a root node, and nodes have parent-child relationships, with no cycles.
Trees are widely used in computer science for organizing and retrieving data e?ciently.
1.2 Basic Terminology
• Node: Stores data and links to other nodes.
• Root: The topmost node with no parent.
• Leaf: A node with no children.
• Height: The length of the longest path from root to a leaf.
• Depth: The length of the path from the root to a node.
1.3 Types of Trees
• Binary Tree: Each node has at most two children (left and right).
• Binary Search Tree (BST): A binary tree where the left childs value is less than
the parents, and the right childs value is greater.
• AVL Tree: A self-balancing BST where the height di?erence between left and
right subtrees is at most 1.
• Red-Black Tree: A self-balancing BST with color properties (red or black) to
ensure balanced height.
• B-Tree: Aself-balancingtreeforlargedatasets, usedindatabasesand?lesystems.
• B+ Tree: A variant of B-Tree where only leaf nodes store data, used in databases.
• Binary Heap: A complete binary tree used for priority queues, with min-heap
(smallest at root) or max-heap (largest at root) properties.
• Expression Tree: A binary tree representing expressions, with leaves as operands
and internal nodes as operators.
1.4 Binary Tree Representation
• Node Structure: Contains data, left child pointer, and right child pointer.
• ArrayRepresentation: Storesabinarytreeinanarraywhereforanodeatindex
i, left child is at 2i+1, right child at 2i+2.
• Linked Representation: Uses pointers for left and right children, allowing dy-
namic allocation.
1.5 Basic Operations
• Traversal:
– Pre-order: Root, Left, Right.
– In-order: Left, Root, Right (sorted order for BST).
– Post-order: Left, Right, Root.
• Insertion: Adds a node at the appropriate position (e.g., based on value in BST).
• Deletion: Removes a node while maintaining tree properties (e.g., rebalancing in
AVL/Red-Black trees).
• Search: Finds a node with a given value (O(log n) in balanced BSTs).
1
Page 2


1 Trees in Programming and Data Structures
1.1 Introduction to Trees
A tree is a hierarchical, non-linear data structure consisting of nodes connected by edges.
Each tree has a root node, and nodes have parent-child relationships, with no cycles.
Trees are widely used in computer science for organizing and retrieving data e?ciently.
1.2 Basic Terminology
• Node: Stores data and links to other nodes.
• Root: The topmost node with no parent.
• Leaf: A node with no children.
• Height: The length of the longest path from root to a leaf.
• Depth: The length of the path from the root to a node.
1.3 Types of Trees
• Binary Tree: Each node has at most two children (left and right).
• Binary Search Tree (BST): A binary tree where the left childs value is less than
the parents, and the right childs value is greater.
• AVL Tree: A self-balancing BST where the height di?erence between left and
right subtrees is at most 1.
• Red-Black Tree: A self-balancing BST with color properties (red or black) to
ensure balanced height.
• B-Tree: Aself-balancingtreeforlargedatasets, usedindatabasesand?lesystems.
• B+ Tree: A variant of B-Tree where only leaf nodes store data, used in databases.
• Binary Heap: A complete binary tree used for priority queues, with min-heap
(smallest at root) or max-heap (largest at root) properties.
• Expression Tree: A binary tree representing expressions, with leaves as operands
and internal nodes as operators.
1.4 Binary Tree Representation
• Node Structure: Contains data, left child pointer, and right child pointer.
• ArrayRepresentation: Storesabinarytreeinanarraywhereforanodeatindex
i, left child is at 2i+1, right child at 2i+2.
• Linked Representation: Uses pointers for left and right children, allowing dy-
namic allocation.
1.5 Basic Operations
• Traversal:
– Pre-order: Root, Left, Right.
– In-order: Left, Root, Right (sorted order for BST).
– Post-order: Left, Right, Root.
• Insertion: Adds a node at the appropriate position (e.g., based on value in BST).
• Deletion: Removes a node while maintaining tree properties (e.g., rebalancing in
AVL/Red-Black trees).
• Search: Finds a node with a given value (O(log n) in balanced BSTs).
1
• Height Calculation: Determines the height of the tree (O(n) for unbalanced
trees).
1.6 Insertion and Deletion in Speci?c Trees
• BSTInsertion: Insertbasedonvaluecomparison; O(h)where histhetreeheight.
• BST Deletion: Handle cases for leaf nodes, single-child nodes, or nodes with two
children; may require successor replacement.
• AVL Insertion/Deletion: Perform rotations (LL, RR, LR, RL) to maintain bal-
ance after insertion or deletion.
• Red-Black Tree: Adjust colors and perform rotations to maintain balance prop-
erties.
1.7 Applications of Trees
• BST: E?cient searching, insertion, and deletion (e.g., symbol tables).
• Heaps: Priority queues, heapsort, and scheduling tasks.
• B-Tree/B+ Tree: Database indexing and ?le systems for fast retrieval.
• Expression Trees: Evaluate mathematical expressions or parse code.
• Decision Trees: Used in machine learning for classi?cation and decision-making.
• File Systems: Represent hierarchical directory structures.
1.8 Advantages and Disadvantages
• Advantages:
– Hierarchical organization for e?cient data retrieval.
– Balanced trees (AVL, Red-Black) provide O(log n) operations.
– Flexible for various applications like databases and expression parsing.
• Disadvantages:
– Unbalanced trees (e.g., skewed BST) degrade to O(n) performance.
– Complex implementation for self-balancing trees (e.g., AVL, Red-Black).
– Higher memory overhead compared to arrays due to pointers.
1.9 Short Questions and Answers
1. What is a binary tree? A tree where each node has at most two children.
2. How does a BST di?er from a binary tree? A BST maintains an order where
left child < parent < right child.
3. What is the purpose of AVL trees? To ensure balanced height for O(log n)
operations through rotations.
4. What is a binary heap used for? Priority queues and e?cient sorting (heap-
sort).
2