UNIT III

TREE
a tree is a widely used abstract data type (ADT) or data structure implementing this
ADT that simulates a hierarchical tree structure
It is a collection of nodes that are connected by edges and has a hierarchical relationship
between the nodes.
The topmost node of the tree is called the root, and the nodes below it are called the child
nodes. Each node can have multiple child nodes.
Terminologies used in Trees
• Root - the top most node in a tree.
• Parent - the converse notion of child.
• Siblings - nodes with the same parent.
• Descendant - a node reachable by repeated proceeding from parent to child.
• Leaf - a node with no children.

• Internal node - a node with at least one child.

• Degree - number of sub trees of a node.

• Edge - connection between one node to another.
• Path - a sequence of nodes and edges connecting a node with a descendant.
• Level of a node: The count of edges on the path from the root node to that node.
The root node has level 0.
• Depth of a node: it can also be defined as the number of edges in the path from
the root of the tree to the node.
• Height of a node: The height of a node can be defined as the length of the longest
path from the node to a leaf node of the tree.
• Height of the Tree: The height of a tree is the length of the longest path from the
root of the tree to a leaf node of the tree.
• Degree of a Node: The total count of subtrees attached to that node is called the
degree of the node.
Types of Tree data structures:
Basic Operation Of Tree Data Structure:
• Create – create a tree in the data structure.
• Insert − Inserts data in a tree.
• Search − Searches specific data in a tree to check whether it is present or not.
• Traversal:
• Preorder Traversal – perform Traveling a tree in a pre-order manner in
the data structure.
• In order Traversal – perform Traveling a tree in an in-order manner.
• Post-order Traversal –perform Traveling a tree in a post-order manner.

Binary Tree
Binary Tree is defined as a tree data structure where each node has at most 2 children. Since each
element in a binary tree can have only 2 children, we typically name them the left and right child.
Binary Tree Representation

A Binary tree is represented by a pointer to the topmost node (commonly known as the “root”) of the
tree. If the tree is empty, then the value of the root is NULL. Each node of a Binary Tree contains the
following parts:
1. Data
2. Pointer to left child
3. Pointer to right child
Basic Operation On Binary Tree:
• Inserting an element.
• Removing an element.
• Searching for an element.
• Traversing the tree.

Inorder Traversal:
Algorithm Inorder(tree)
1. Recursively Traverse the left subtree
2. Visit the root.
3. RecursivelyTraverse the right subtree

Preorder Traversal:
Algorithm Preorder(tree)
1. Visit the root.
2. Recursively Traverse the left subtree
3. Recursively Traverse the right subtree

Postorder Traversal:
Algorithm Postorder(tree)
1. RecursivelyTraverse the left subtree
2. RecursivelyTraverse the right subtree
3. Visit the root
\Expression Tree
The expression tree is a binary tree in which each internal node corresponds to the operator
and each leaf node corresponds to the operand so for example expression tree for 3 +
((5+9)*2) would be:

In this tree, the internal node always denotes the operators.

o The leaf nodes always denote the operands.

o The operations are always performed on these operands.
o The main use of these expression trees is that it is used to evaluate, analyze and modify the
various expressions.

Construction of Expression Tree:

Now For constructing an expression tree we use a stack. We loop through input expression
and do the following for every character.
1. If a character is an operand push that into the stack
2. If a character is an operator pop two values from the stack make them its child and
push the current node again.
In the end, the only element of the stack will be the root of an expression tree.
Time complexity: O(n)
Applications of Tree:
• File Systems: The file system of a computer is often represented as a tree. Each
folder or directory is a node in the tree, and files are the leaves.
• XML Parsing: Trees are used to parse and process XML documents. An XML
document can be thought of as a tree, with elements as nodes and attributes as
properties of the nodes.
• Database Indexing: Many databases use trees to index their data. The B-tree and its
variations are commonly used for this purpose.
• Compiler Design: The syntax of programming languages is often defined using a
tree structure called a parse tree. This is used by compilers to understand the structure
of the code and generate machine code from it.
• Artificial Intelligence: Decision trees are often used in artificial intelligence to make
decisions based on a series of criteria.

Advantages of Tree:
• Efficient searching: Trees are particularly efficient for searching and retrieving data.
• Flexible size: Trees can grow or shrink dynamically depending on the number of
nodes that are added or removed.
• Easy to traverse: Traversing a tree is a simple operation, and it can be done in
several different ways depending on the requirements of the application.
• Easy to maintain: Trees are easy to maintain because they enforce a strict hierarchy
and relationship between nodes.
• Natural organization: Trees have a natural hierarchical organization that can be
used to represent many types of relationships.
• Fast insertion and deletion: Inserting and deleting nodes in a tree can be done in
O(log n) time, which means that it is very fast even for very large trees.

Binary Search Tree

Binary Search Tree is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

Basic Operations:
1. Insertion in Binary Search Tree
2. Searching in Binary Search Tree
3. Deletion in Binary Search Tree
 4. Binary Search Tree (BST) Traversals – Inorder, Preorder, Post Order
5. Convert a normal BST to Balanced BST
Insertion in Binary Search Tree (BST)
Now, let's see the creation of binary search tree using an example.

Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50

Step 1 - Insert 45.

Step 2 - Insert 15.

As 15 is smaller than 45, so insert it as the root node of the left subtree.

Step 3 - Insert 79.

As 79 is greater than 45, so insert it as the root node of the right subtree.

Step 4 - Insert 90.

90 is greater than 45 and 79, so it will be inserted as the right subtree of 79.

Step 5 - Insert 10.

10 is smaller than 45 and 15, so it will be inserted as a left subtree of 15.

Finaly BST is

Threaded Binary Tree

A threaded binary tree is a type of binary tree data structure where the empty left and right
child pointers in a binary tree are replaced with threads that link nodes directly to their in-

order predecessor or successor.

Need for a Threaded Binary Tree?

In a regular tree, the space complexity for insertion/ deletion can range from logarithmic
to linear time.
We get log time in a balanced binary tree and linear time is the worst case in an
unbalanced tree
Types of Threaded Binary Tree
There are two types of threaded Binary Tree:

o One-way threaded Binary Tree:Single Threaded Binary Tree As we can see from the
diagram, only the right pointer which is NULL point to the successor node in a
single-threaded binary tree

o
o Two-way threaded Binary Tree:Double Threaded Binary Tree In a double threaded
Binary tree, the left pointer also points to its predecessor node
Operations in Threaded Binary Tree
We can also perform various operations in a threaded binary tree like -

[Link]
[Link]
[Link]

AVL tree

An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference between
heights of left and right subtrees for any node cannot be more than -1,0,1..
The difference between the heights of the left subtree and the right subtree for any node is known
as the balance factor of the node.

The above tree is AVL because the differences between the heights of left and right subtrees for
every node are less than or equal to 1.

Operations on an AVL Tree:

• Insertion
• Deletion
• Searching

Rotating the subtrees in an AVL Tree:

An AVL tree may rotate in one of the following four ways to keep itself balanced:
Left Rotation:
When a node is added into the right subtree of the right subtree, if the tree gets out of balance, we
do a single left rotation.
Left-Rotation in AVL tree

Right Rotation:
If a node is added to the left subtree of the left subtree, the AVL tree may get out of balance, we
do a single right rotation.

Right Rotation in AVL tree

Left-Right Rotation:
A left-right rotation is a combination in which first left rotation takes place after that right rotation
executes.

Left-Right Rotation in AVL tree

Right-Left Rotation:
A right-left rotation is a combination in which first right rotation takes place after that left rotation
executes.
Right-Left Rotation in AVL tree

Applications of AVL Tree:

1. It is used to index huge records in a database and also to efficiently search in that.
2. For all types of in-memory collections, including sets and dictionaries, AVL Trees are used.
3. Database applications, where insertions and deletions are less common but frequent data
lookups are necessary
4. Software that needs optimized search.
5. It is applied in corporate areas and storyline games.

Advantages of AVL Tree:

1. AVL trees can self-balance themselves.

2. It is surely not skewed.
3. It provides faster lookups than Red-Black Trees
4. Better searching time complexity compared to other trees like binary tree.
5. Height cannot exceed log(N), where, N is the total number of nodes in the tree.

Disadvantages of AVL Tree:

1. It is difficult to implement.
2. It has high constant factors for some of the operations.
3. Less used compared to Red-Black trees.
4. Due to its rather strict balance, AVL trees provide complicated insertion and removal
operations as more rotations are performed.
5. Take more processing for balancing.
B-Tree
• All leaves are at the same level.
• B-Tree is defined by the term minimum degree ‘t‘. The value of ‘t‘ depends upon disk block
size.
• Every node except the root must contain at most t-1 keys. The root may contain a minimum
of 1 key.
• All nodes (including root) may contain at most (2*t – 1) keys.
• Number of children of a node is equal to the number of keys in it plus 1.
• All keys of a node are sorted in increasing order. The child between two
keys k1 and k2 contains all keys in the range from k1 and k2.
• B-Tree grows and shrinks from the root which is unlike Binary Search Tree. Binary Search
Trees grow downward and also shrink from downward.
• Like other balanced Binary Search Trees, the time complexity to search, insert and delete is
O(log n).
• Insertion of a Node in B-Tree happens only at Leaf Node.
Following is an example of a B-Tree of minimum order 5
Note: that in practical B-Trees, the value of the minimum order is much more than 5.

We can see in the above diagram that all the leaf nodes are at the same level and all non-leafs
have no empty sub-tree and have keys one less than the number of their children.
B + Tree
B + Tree is a variation of the B-tree data structure. In a B + tree, data pointers are stored only at
the leaf nodes of the tree. In a B+ tree structure of a leaf node differs from the structure
of internal nodes. The leaf nodes have an entry for every value of the search field, along with a
data pointer to the record (or to the block that contains this record).

Features of B+ Trees
• Balanced: B+ Trees are self-balancing, which means that as data is added or removed from
the tree, it automatically adjusts itself to maintain a balanced structure.
• Multi-level: B+ Trees are multi-level data structures, with a root node at the top and one or
more levels of internal nodes below it.
• Ordered: B+ Trees maintain the order of the keys in the tree, which makes it easy to perform
range queries and other operations that require sorted data.
• Fan-out: B+ Trees have a high fan-out, which means that each node can have many child
nodes.
• Cache-friendly: B+ Trees are designed to be cache-friendly, which means that they can take
advantage of the caching mechanisms
• Disk-oriented: B+ Trees are often used for disk-based storage systems because they are
efficient at storing and retrieving data from disk.

Difference between B+ Tree and B Tree

Some differences between B+ Tree and B Tree are stated below.
Parameters B+ Tree B Tree

Separate leaf nodes for data storage Nodes store both keys and data
Structure
and internal nodes for indexing values

Leaf nodes form a linked list for Leaf nodes do not form a linked
Leaf Nodes
efficient range-based queries list

Order Higher order (more keys) Lower order (fewer keys)

Parameters B+ Tree B Tree

Key Typically allows key duplication in Usually does not allow key
Duplication leaf nodes duplication

Better disk access due to sequential More disk I/O due to non-
Disk Access
reads in a linked list structure sequential reads in internal nodes

Database systems, file systems, In-memory data structures,

Applications
where range queries are common databases, general-purpose use

Better performance for range Balanced performance for search,

are
queries and bulk data retrieval insert, and delete operations

Memory Requires more memory for internal

Requires less memory same node
Usage nodes

Heap Data Structure

A Heap is a special Tree-based data structure in which the tree is a complete binary tree. What is a
complete binary tree?

A complete binary tree is a binary tree in which all the levels except the last level, i.e., leaf node
should be completely filled, and all the nodes should be left-justified.

example.

Operations of Heap Data Structure:

• Heapify: a process of creating a heap from an array.

• Insertion: process to insert an element in existing heap time complexity O(log N).
• Deletion: deleting the top element of the heap or the highest priority element, and then
organizing the heap and returning the element with time complexity O(log N).
• Peek: to check or find the first (or can say the top) element of the heap.

Types of Heap Data Structure

Generally, Heaps can be of two types:
1. Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys
present at all of it’s children. The same property must be recursively true for all sub-trees in
that Binary Tree.
2. Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys
present at all of it’s children. The same property must be recursively true for all sub-trees in
that Binary Tree.

Applications of Heap Data Structure

1. Priority Queues
2. Sorting Algorithms
3. Graph algorithms
4. File Compression
5. Dynamic programming
6. Medical Applications
7. External sorting
8. Load balancing
9. Online algorithms
10. Stock market