Understanding Trees in Data

Structures

Dr. Sugandhi K.
Assistant Professor, CSE
VFSTR Deemed to be University
 Contents
• Basic Terminology
• Types of Trees
• Binary Tree – Introduction
• Binary Tree Properties
• Array and Linked Representations
• Tree Traversals
• Traversal Implementations
• Expression Trees
• Binary Search Tree (BST)
• AVL Trees
• AVL Tree Construction
• Applications of Binary Trees
• Recap and Summary
 Basic Terminology

• Definition of key terms

– Nodes: Individual elements in a tree that store data and are
connected by edges.
– Edges: Connections between nodes that define relationships
in the tree structure.
– Root: The topmost node of a tree, serving as the starting point
for traversal.
– Leaf: Nodes with no children, located at the ends of branches.
– Parent: A node that has one or more child nodes connected to
it.
– Child: A node that is connected to a parent node.
 Types of Trees

• Overview of Tree Types:

– Trees come in various forms, each with specific
characteristics and purposes.
– Different types of trees serve different functions and
solve various problems in computer science and beyond.
– Binary Trees:
• Binary trees are a fundamental type of tree structure.
• Each node has at most two children: a left child and a right
child.
• Binary trees play a key role in various data structure
implementations, such as binary search trees and heaps.
– AVL Trees:
• AVL trees are a type of self-balancing binary search
tree.
• They maintain a balance condition, ensuring efficient
operations.
• AVL trees are used to speed up search, insertion, and
deletion operations in comparison to regular binary
search trees.
– Expression Trees:
• Expression trees represent mathematical expressions in a
tree format.
• Operators and operands are stored as nodes, facilitating
expression evaluation.
• Expression trees are vital in compilers and mathematical
software.
– Other Tree Types:
• There are many other specialized types of trees, including
B-trees, Red-Black trees, and Trie trees.
• These trees cater to specific needs like database indexing
and string searches.
 Binary Tree – Introduction

• Definition of a Binary Tree:

– A binary tree is a hierarchical data structure where each node
can have at most two children.
– Nodes are connected by edges, and the topmost node is called
the root.
• Structure of Binary Trees:
– The structure follows a parent-child relationship:
• Each node has a parent (except the root).
• Each node can have at most two children: a left child and a right child.
– Binary trees provide a way to organize data hierarchically.
– They're used in various algorithms and data manipulation tasks.
 Binary Tree Properties

• Height:
– The height of a binary tree is the length of the
longest path from the root to a leaf node.
– It indicates the depth of the tree and affects the
efficiency of operations.
• Depth:
– The depth of a node is the length of the path from
the root to that node.
– It quantifies the level of the node within the tree.
• Level:
– Each node in a binary tree resides at a specific level.
– The root is at level 0, its children are at level 1, and
so on.
• Full Binary Tree:
– A full binary tree (also called a proper or 2-tree) is a
tree where each node has either 0 or 2 children.
– It leads to a balanced structure and has applications
in priority queues and heap data structures.
• Complete Binary Tree:
– A complete binary tree is a binary tree where all
levels are filled except possibly the last level.
– In the last level, nodes are filled from left to right.
– Complete binary trees are used in array-based
representations.
 Array and Linked Representations

• Array Representation: Pros and Cons:

– Pros:
• Simple and memory-efficient for complete binary trees.
• Constant-time access to nodes using indexes.
– Cons:
• Wasteful for sparse trees, as memory is allocated for all
possible nodes.
• Insertion and deletion operations can be costly due to
shifting.
• Linked Representation Using Pointers:
– Linked representation uses nodes with pointers to
their children.
– Each node has pointers to its left and right children.
• Advantages of Linked Representation:
– Efficient for sparse trees as memory is allocated only
for existing nodes.
– Insertion and deletion can be more efficient in
certain cases.
• Considerations:
– Choice of representation depends on the use case
and the tree's characteristics.
 Tree Traversals
• In-Order Traversal:
– Traverses left subtree, visits the current node,
traverses right subtree.
– Useful for visiting nodes in ascending order in a
binary search tree.
• Pre-Order Traversal:
– Visits the current node, traverses left subtree,
traverses right subtree.
– Useful for copying a tree structure or evaluating
expression trees.
• Post-Order Traversal:
– Traverses left subtree, traverses right subtree,
visits the current node.
– Useful for deleting a tree, as it ensures children
are deleted before the parent.
 Traversal Implementations

• Pseudocode for In-Order Traversal:

inOrder(node):
if node is not null:
inOrder([Link])
visit(node)
inOrder([Link])
• Pseudocode for Pre-Order Traversal:
preOrder(node):
if node is not null:
visit(node)
preOrder([Link])
preOrder([Link])
• Pseudocode for Post-Order Traversal:
postOrder(node):
if node is not null:
postOrder([Link])
postOrder([Link])
visit(node)
• Recursion and Iterative Approaches:
– Traversals can be implemented using both
recursion and iteration.
– Recursion follows the natural structure of the tree
and is elegant but might face stack overflow issues
for very large trees.
– Iterative approaches often involve using a stack or
queue data structure.
 Expression Trees

• Definition and Purpose:

– Expression Trees are a type of binary tree used to
represent mathematical expressions.
– The nodes of the tree represent operators and
operands, creating a structured representation of
the expression's syntax.
• Converting Expressions to Expression Trees:
– To convert an expression into an expression tree:
• Break down the expression into tokens (operands and
operators).
• Use a parser to build the expression tree while
adhering to operator precedence and associativity
rules.
• The resulting expression tree captures the hierarchical
structure of the expression.
 Binary Search Tree (BST)

• Definition and Properties:

– A Binary Search Tree (BST) is a binary tree with
the following properties:
• Each node has a value.
• The left subtree of a node contains values less than the
node's value.
• The right subtree of a node contains values greater
than the node's value.
• Operations: Insertion, Deletion, Searching:
– Insertion:
• To insert a new value:
– Start from the root.
– Traverse left or right based on comparison with node values.
– Insert the new value as a leaf node.
– Deletion:
• To delete a value:
– Find the node to be deleted.
– Handle cases based on the node's children.
– Reorganize the tree while maintaining the BST properties.
– Searching:
• To search for a value:
– Start from the root.
– Traverse left or right based on comparison with node values.
– Repeat until the value is found or the traversal reaches a leaf.
• Add pseudocodes
 AVL Trees
• Definition and Importance:
– An AVL Tree is a self-balancing binary search tree.
– It ensures that the height difference between left and
right subtrees (balancing factor) is limited, maintaining
efficient operations.
• Balancing Factor and Rotations:
– Balancing Factor:
• The balancing factor of a node is the height difference
between its left and right subtrees.
• It's denoted as
BF = height(left subtree) - height(right subtree).
– Rotations:
• Rotations are tree-restructuring operations to maintain
balance.
• Single Right Rotation: Corrects left-heavy imbalance.
• Single Left Rotation: Corrects right-heavy imbalance.
• Double Right-Left Rotation: Corrects left-right
imbalance.
• Double Left-Right Rotation: Corrects right-left
imbalance.
• Add figures
 AVL Tree Construction
• Step-by-Step Example of AVL Tree
Construction:
– Start with an unbalanced binary search tree.
– Perform insertions that cause imbalances.
– Apply rotations to restore balance.
– Walk through the entire construction process.
• Illustration of Rotations:
– Show how rotations are performed on specific nodes.
– Visualize how rotations maintain balance.
– Display the transformed tree after rotations.
• Include a sequence of diagrams illustrating the
insertion of nodes and the corresponding rotations
performed.
• .
 Applications of Binary Trees
• Use Cases in Computer Science and Real-World Scenarios:
– Binary trees have diverse applications in various fields.
– They solve problems by efficiently organizing data and enabling
effective algorithms.
• Hierarchical Data Structures:
– Binary trees are commonly used to represent hierarchical structures.
– Examples include file systems, organization charts, and family trees.
• Decision-Making Processes:
– Binary trees facilitate decision-making processes in algorithms.
– They are used in search algorithms like binary search and decision
trees in machine learning.
• Consider including examples of hierarchical
structures and decision trees to showcase real-
world applications.
 Recap and Summary

• Key Points from Each Topic Covered:

– Basic terminology and types of trees.
– Binary tree properties and representations.
– Tree traversals and their implementations.
– Expression trees and their purpose.
– Binary Search Trees and their operations.
– AVL Trees and balancing concepts.
– Applications of binary trees.
• Emphasis on Understanding Tree Structures
and Applications:
– Understanding tree structures is fundamental to
effective data representation.
– Tree concepts have broad applications in
computer science and beyond.