Trees in Data Structures
Presented By:
Pawan Kumar
Assistant Professor
GJUS&T, Hisar
Outlines
• Introduction
• Binary Tree
• Binary Search Tree (BST)
• BST Operations
• Searching
• Insertion
• Deletion
• Traversal
• Complexity in BST
• Applications of BST
• Types of BST
Trees in Data Structures 2
Data Structure Hierarchy
Data Structure
Primitive Data Structure Non-Primitive Data Structure
Integer Float Double Pointer Array Lists Files
Linear Lists Non-Linear Lists
Stacks Queues Trees Graphs
Figure 1: Data Structure Hierarchy
Trees in Data Structures 3
Tree
• Tree – A tree can be defined as
finite set of data items (nodes).
• Tree is a non-linear type of data A
structure in which data items are
stored in order. B C D
• It is mainly used to represent data
containing a hierarchical
E F G
relationship between elements.
• Each node in a tree can have 0 or
more children. Figure 2: Tree
• Each node can have at most one
parent.
Trees in Data Structures 4
Terminology
• Root No parent (Level 0)
• Leaf No Child
• Interior Non-leaf
• Height Distance from root to leaf
Root Node A
Internal Node B C D
Leaf Nodes E F G
Figure 3: Terminology
Trees in Data Structures 5
Binary Tree (BT)
• Binary tree is also finite set of data
items. A
• Binary tree is a tree having
maximum of 2 children. B C
• Each node can have either 0 or 1 or
2 child only. E D F
• Also known as Decision Making
Tree. Figure 4: Binary Tree
• It is helpful in designing routing
protocols and other applications.
Trees in Data Structures 6
• Strict Binary Tree (SBT)– A binary tree in which every node has
either zero or two nodes.
• It is also known as Full Binary Tree, Proper Binary Tree or 2-Tree.
• 2-tree states that a node either can have 0 or 2 child only.
A A A A
B C D B C B C B C
E F G
E D F E D E D F
Tree Binary Tree SBT CBT
Figure 5: Trees
Trees in Data Structures 7
Complete Binary Tree (CBT)
• Complete Binary Tree (CBT)– A binary tree in which every
level, except possibly the last, is completely filled, and all nodes
in the last level are as far left as possible.
A
B C
E D F C
Trees in Data Structures 8
Binary Search Tree (BST)
• Binary Search Tree is a binary tree
which is either empty or satisfies A
A>B
following rules: A<C
• Value of key on left is smaller than B C
root
• Value of key on right is greater than 5
or equal to root
• All the sub-trees of the left and right 3 8
children follow the above two rules.
• It was invented by P.F. Windley, A.D.
Booth, A.J.T. Colin, and T.N. 1 4 6 9
Hibbard in 1960.
Figure 6: BST Example
Trees in Data Structures 9
Difference Between BT and BST
• Binary Tree is simply a tree in which each node can have at most two
children.
• Binary Search Tree is a binary tree in which the nodes are assigned
values, with the following restrictions :
• No duplicate values.
• The left subtree of a node can only have values less than
the node.
• The right subtree of a node can only have values greater
than the node and recursively defined.
• The left subtree of a node is a binary search tree.
• The right subtree of a node is a binary search tree
Trees in Data Structures 10
Binary Search Tree (BST) Operations
• Four basic operations are performed on BST
• Search
• Insertion
• Deletion
• Traversal
Trees in Data Structures 11
Binary Tree Search
• Searching a node K in a BST follow the rules:
• Compare the key with root node, if root X is empty or equal to key K then
return X
• If key K is smaller than root X , then search again on left subtree of root X.
• If key is matched than return the node.
• Algorithm to search key
• TREE-SEARCH(x,k)
If x==NIL or k==x.key
return x
If k < x.key
return TREE-SEARCH(x.left,k)
else
return TREE-SEARCH(x.right,k)
Trees in Data Structures 12
Binary Search Tree Insertion
5 3 1 4 8 6 9
3 8
1 4 6 9
Trees in Data Structures 13
BST Deletion
• Case 1: Element X has no children, then simply delete X and update
location of X in parent node P(X) by null pointer.
• X has exactly one child, then delete X and replace location of X in
P(X) by location of single child.
• Delete the element 4, 8 from the given tree
5 5
5
Delete 4
3 8 Delete 8 3 6
3 8
1 4 6 1
1 6
Trees in Data Structures 14
Binary Search Tree Traversal
• Traversal is one of the most common operation on tree
data structure in which each node in the tree is visited
exactly once in a systematic manner.
Root Root Root
Left Left Right Left Right
Right
Sub- Sub- Sub- Sub- Sub-
Sub-
Tree Tree Tree Tree Tree
Tree
Inorder traversal Preorder traversal Postorder traversal
Trees in Data Structures 15
Inorder Traversal
• Inorder Traversal –
• Traverse left subtree in Inorder (L)
• Visit the root node (N)
• Traverse right subtree in Inorder (R)
5 5
3 8 Left Root Right 3 8
1 4 6 9 1 4 6 9
1 3 4 5 6 8 9
Trees in Data Structures 16
Preorder Traversal
• Preorder Traversal –
• Visit the root node (N)
• Traverse left subtree in Preorder (L)
• Traverse right subtree in Preorder (R)
5 5
3 8 Root Left Right 3 8
1 4 6 9 1 4 6 9
5 3 1 4 8 6 9
Trees in Data Structures 17
Postorder Traversal
• Postorder Traversal –
• Traverse left subtree in Postorder (L)
• Traverse right subtree in Postorder (R)
• Visit the root node (N)
5 5
3 8 Left Right Root 3 8
1 4 6 9 1 4 6 9
1 4 3 6 9 8 5
Trees in Data Structures 18
Advantages of BST
• Cost for N nodes BST is O(log n) for the operations Search(),
Insert(), Delete() as comparing to Binary tree having O(n).
Trees in Data Structures 19
Disadvantages of BST
• If the element which is inserted to be next is greater than previous
item then we will get right skewed tree.
• If the element which is inserted to be next is smaller than previous
item then we will get left skewed tree.
1 2 3 4 5 5 4 3 2 1
1 5
2 4
3 3
4
Right Skewed Tree 2 Left Skewed Tree
5
1
Trees in Data Structures 20
Complexity in BST
Operation Average Case Worst Case Best Case
Search O(Log n) O(n) O(1)
Insertion O(Log n) O(n) O(1)
Deletion O(Log n) O(n) O(1)
Trees in Data Structures 21
Applications of Binary Tree
• Used in many search applications where data is constantly entering/leaving,
such as map and set objects in many language’s libraries.
• Binary Trees – Used in almost every high bandwidth router for storing routing
tables.
• Hash Trees – Used in P2P programs in which hash needs to be verified.
• Heaps – Used in implementing efficient priority queues.
• Huffman Coding – Used in compression algorithms such as used by .jpeg,
.mp3 file format.
• Syntax Tree – Constructed by compilers and (implicitly) calculators to parse
expressions.
• T-tree – Most databases used some form of B-Tree to store data on the drive
Trees in Data Structures 22
Types of BST
• AVL Tree
• Red Black Tree
• Splay Tree
Trees in Data Structures 23
AVL Tree
• To overcome skewness problem in BST, AVL tree concept came into
existence in 1962 invented by Adelson Velsky and Evgenii Landis.
• AVL tree is a self-balancing Binary Search Tree (BST)
where the difference between heights of left and right
subtrees cannot be more than one for all nodes.
• Balancing Factor (BF)
• BF ranges - (-1,0,1)
• BF = Height of left subtree - Height of right subtree
• Time Complexity: O(Log n)
• AVL tree mainly faces four unbalancing issues:
• LL (left-left) Issue
• RR (right-right) Issue
• LR (left-right) Issue
• RL (right-left) Issue
Trees in Data Structures 24
AVL Tree
• LL problem: Occur due to insertion on left of left subtree
• When a new node is inserted, calculate BF of all nodes on path from
root to newly inserted node
• Consider the node as pivot node whose BF is 2 or -2 and rebalance it by
rotating pivot node on right of its left child.
2
3 0
2
Rebalance Tree
2 1
0 1 3 0
1 0
Trees in Data Structures 25
AVL Tree
• LR problem: Occur due to insertion on right of left subtree
• When a new node is inserted, calculate BF of all nodes on path from
root to newly inserted node
• Consider the node as pivot node whose BF is 2 or -2.
• To rebalance it first change in LL problem then balance the tree.
2
3 2
3 0
2
First change to LL
1 -1 Rebalance Tree
2 1 0 1 3 0
0 2
1 0
Trees in Data Structures 26
AVL Tree
Elements to insert
1 2 3 4 5
BF of one node is
-2 not correct, need
0 -1 1 to rebalance
1 1 0 -1
2 2 0
3
Insert 1
Insert 2 Insert 3
Trees in Data Structures 27
AVL Tree
Elements to insert
1 2 3 4 5
-2 BF of one node is not 0
1 -1 correct, need to rebalance Insert 4
2
2 0 0 0
3 1 3
Trees in Data Structures 28
AVL Tree
Elements to insert
1 2 3 4 5
BF of node 2,3,4 are
-2
-1 2 more than one, so
2 0 rebalance the tree
0 Insert 5 -2
-1 1 3
1 3
-1 RR Issue
0 4
4
0
5
Trees in Data Structures 29
AVL Tree
Elements to insert
1 2 3 4 5
-2 -1
2 BF of node 2,3,4 are
0 2
more than one, so
1 -2 0
3 rebalance the tree 1 0 4
-1 0
4
RR Issue 0 3 5
0
5
Trees in Data Structures 30
Red Black Tree
• Every node has a color either red or black.
• Root of tree is always black.
• There are no two adjacent red nodes (A red node cannot have a red
parent or red child).
• Every path from root to a NULL node has same number of black
nodes.
• Time Complexity: O(Log n)
Trees in Data Structures 31
Splay Tree
• Automatically moves frequently accessed elements nearer to
the root for quick to access.
• Search operation in Splay tree does the standard BST search,
in addition to search, it also splays (move a node to the root).
• Time Complexity – O(log n)
• Splay trees are used in Windows NT (in the virtual memory,
networking, and file system code)
Trees in Data Structures 32
References
1. Seymour Lipschutz, Data Structures with C, Tata McGraw-Hill Pvt.
Ltd., 2011.
2. Sartaj Sahni, Data Structure, Algorithms and Applications 2nd Edition,
Universities Press Pvt. Ltd., 2005.
3. Debasis, Samanta. Classic Data Structures 2nd Edition, PHI Learning
Pvt. Ltd., 2009.
Trees in Data Structures
33
