Trees
Module 3
Introduction
Finite set of one or more nodes such that:
There is a specially designated node called root
The remaining nodes are partitioned into n>=0 disjoints sets
T1, T2, … Tn, where each set is a tree called subtrees of the
root.
2 Module 3. Trees Saturday, February 15, 2020
Introduction cont…
Terminology:
Parent: immediate root of a node
Siblings: children of the same parent
Ancestors of a node: all nodes along the path from the root to that node
Descendants of a node: all nodes of the subtrees of a node
Degree of a node: number of subtrees of a node
Root node: no parents or ancestors
Leaf/terminal node: no children or descendants node with a degree = 0
Nonleaf/nonterminal node: has at least one child or descendant node with
degree <> 0
Degree of a tree = max[degree of nodes]
Level/generation of a node: 1 + length of its path from the root
Height/depth of a tree: total number of levels
Weight of a tree: number of leaf nodes
Forest: set of disjoint trees
3 Module 3. Trees Saturday, February 15, 2020
Binary Tree
An ADT that is hierarchical in nature
Collection of nodes which are either empty or consists of a root
and two disjoint binary trees called the left and the right subtrees
4 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
Level of a node - distance of the node from the root
Height or depth of a tree - level of the bottommost nodes; length of
the longest path from the root to any leaf
External node - node w/o children; internal otherwise
Proper binary tree - binary tree that has either zero or two children
5 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
Examples
6 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
Properties
For a (proper) binary tree of depth k,
The maximum number of nodes at level i is 2i , i ≥ 0
The number of nodes is at least 2k + 1 and at most 2k+1 – 1
The number of external nodes is at least h+1 and at most 2k
The number of internal nodes is at least h and at most 2k – 1
If no is the number of terminal nodes and n2 is the number of
nodes of degree 2 in a binary tree, then no = n2 + 1
7 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
Types
right (left) skewed binary tree - tree in which every node has no
left (right) subtrees; tree with the greatest depth
8 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
strictly binary tree - tree in which every node has either
two subtrees or none at all
9 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
full binary tree - strictly binary tree in which all terminal
nodes lie at the bottom-most level; has the maximum
number of nodes for a given depth
10 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
complete binary tree - tree which results when zero or
more nodes are deleted from a full binary tree in reverse
level order.
11 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
Representations
Using Arrays - static/sequential representation
Array
Module size
3. Treesneeded will be 2k-1, k is the height of a given tree
Saturday, February 15, 2020
12
Binary Tree cont…
Using linked lists
13 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
Traversals
A procedure that visits the nodes of the binary tree in a linear
fashion such that each node is visited exactly once, visit a
node means performing computations local to the node
Preorder
Inorder
Postorder
14 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
Preorder traversal – NLR
traversal
If the binary tree is empty, do
nothing (traversal done)
Otherwise:
Visit the root.
Traverse the left subtree in
preorder.
Traverse the right subtree in
preorder.
15 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
Inorder traversal – LNR traversal
If the binary tree is empty, do nothing
(traversal done) Otherwise:
Traverse the left subtree in inorder.
Visit the root.
Traverse the right subtree in inorder.
16 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
Postorder traversal – LRN
traversal
If the binary tree is empty, do
nothing (traversal done)
Otherwise:
Traverse the left subtree in
postorder.
Traverse the right subtree in
postorder.
Visit the root.
17 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
Examples. Give the preorder, inorder and postorder
traversals:
18 Module 3. Trees Saturday, February 15, 2020
Binary Tree cont…
Counting Trees
Create the corresponding counting trees with the
following traversals:
1. Pre: IAMHEDBCFL
Post: EHDMALFCBI
In: AHEMDICFLB
2. Pre: ABDGCEHIF
In: DGBAHEICF
3. Post: CBFEGDA
In: CBAEFDG
4. Post: FABG/+CD - ^*
In: F/AGB*+^C-D
19 Module 3. Trees Saturday, February 15, 2020
Binary Search Trees
A binary tree that satisfies the
BST property - the value of
each node in the tree is
greater than the value of the
node in its left and it is less
than the value in its right
child.
20 Module 3. Trees Saturday, February 15, 2020
Binary Search Trees cont…
Operations
Algorithm: Insertion
If the tree is empty, then insert the new item in the
tree’s root node.
If the root’s key matches the new item’s key then
skip insertion.
If the new item’s key is smaller than the root’s key,
then insert the new item in the root’s left subtree. Otherwise
insert the new item in the root’s right subtree.
21 Module 3. Trees Saturday, February 15, 2020
Binary Search Trees cont…
Algorithm: Searching
If the tree is empty, then the target key is not in the tree.
If the target key is found in the root item then the target key is
found in the root item.
If the target key is smaller than the root’s key then search the
left subtree, otherwise search the right subtree.
22 Module 3. Trees Saturday, February 15, 2020
Binary Search Trees cont…
Algorithm: Deletion
First, we find the deletion node p (= the node that we want to
delete)
Find the successor node of p
Replace the content of node p with the content of the successor
node
Delete the successor node
23 Module 3. Trees Saturday, February 15, 2020
Balanced BST
To ensure that searching takes O(log2n), balance has to be
maintained in a BST
balance of a node - height of a node's left subtree minus
the height of its right subtree
AVL Tree
Most commonly used balanced BST
Created by G. Adel’son-Vel’skii and E. Landis
Height-balanced tree wherein the the height difference between
the subtrees of a node, for every node in the tree, is at most 1
O(log2n) time complexity for searching, insertion and deletion
24 Module 3. Trees Saturday, February 15, 2020
Balanced BST cont…
25 Module 3. Trees Saturday, February 15, 2020
Balanced BST cont…
Tree Rotations
Simple Right Rotation (SRR) - used when the new item C is
in the left subtree of the left child B of the nearest ancestor A
with balance factor +2
26 Module 3. Trees Saturday, February 15, 2020
Balanced BST cont…
Simple Left Rotation (SLR) - used when the new item C is in
the right subtree of the right child B of the nearest ancestor A
with balance factor -2
27 Module 3. Trees Saturday, February 15, 2020
Balanced BST cont…
Left-Right Rotation (LRR) - used when the new item C is in
the right subtree of the left child B of the nearest ancestor A
with balance factor +2
28 Module 3. Trees Saturday, February 15, 2020
Balanced BST cont…
Right-Left Rotation (RLR) - used when the new item C is in
the left subtree of the right child B of the nearest ancestor A
with balance factor
-2
29 Module 3. Trees Saturday, February 15, 2020
Balanced BST cont…
Operations
Algorithm: Insertion
1. Insert the node at the proper point.
2. Starting from the point of insertion, take the first node whose
subtree heights differ by more than one level as A.
3. If the new node is inserted in the left subtree of A, take the left
child of A as B; if inserted in the right subtree of A, take the right
child of A as B.
4. If the new node is inserted in the left subtree of B, take the left
child of B as C; if inserted in the right subtree of B, take the right
child of B as C.
5. Take the inorder traversal of A, B, and C.
6. Take the middle node as the parent of the two other nodes.
7. Adjust other nodes if necessary.
30 Module 3. Trees Saturday, February 15, 2020
Balanced BST cont…
Algorithm: Deletion
1. Delete the node.
2. If the deleted node is a non-terminal node, the immediate predecessor
(immediate successor) replaces the deleted node.
3. Starting from the deepest level, take the first node whose subtree heights
differ by more than one level as A.
4. Take the right child of A as B if it has more descendants than the left
child; otherwise, take the left child of A as B.
5. Take the right child of B as C if it has more descendants than the left
child; otherwise, take the left child of B as C. If equal prioritize LL over
LR or RR over RL.
6. Take the inorder traversal of A, B, and C.
7. Take the middle node as the parent of the two other nodes.
8. Adjust other nodes.
9. Rebalance if needed
31 Module 3. Trees Saturday, February 15, 2020
Balanced BST cont…
Examples. Create AVL trees with the following insertion
and deletion operations. Each number is independent of the
other numbers.
1. Ins: M, T, O, Q, S, R, W, V,Y, U, C, G, E, X
2. Ins: 10, 20, 30, 40, 50, 60, 70
3. Ins: 13, 20, 15, 17, 19, 18, 23, 22, 25, 21, 8, 5, 6, 4, 3, 2
Del: 13, 22, 19, 6, 18
4. Ins: 15, 20, 25, 10, 30, 35, 23, 28, 27, 22, 29, 33
Del: 10
Ins: 24, 21, 26
Del: 22, 23, 21, 28, 27, 20, 25, 26
32 Module 3. Trees Saturday, February 15, 2020
Balanced BST cont…
Del: 35, 14, 5, 11, 15, 17, 20
Ins: 14, 10, 13, 28
Del: 1, 67, 9
Ins: 35, 15, 20
33 Module 3. Trees Saturday, February 15, 2020
M-Way Search Trees
#keys values in a given file = # of nodes that will be needed
by an AVL tree
1M records = 1M nodes are needed
Solution: To lessen the number of nodes, is by allowing the
nodes to store more than one key value. This leads to shorter
in height and smaller number of comparisons.
M-way or Multiway Search Trees: A kind of search tree in
which each node can store 1 to M-1 values 1 to M links to
subtrees.
34 Module 3. Trees Saturday, February 15, 2020
M-Way Search Trees cont…
Types:
B-Tree
Bayer, McCreight and Kaufman in 1972
Balanced M-Way search tree in which all leaf nodes are at
the same level
Properties
An interior or nonleaf node with N values should contain N+1 links
Root node contains at least 1 value and at most M-1 values
All non-root contain at least ⎡M/2⎤ - 1 values and at most M-1 values
35 Module 3. Trees Saturday, February 15, 2020
M-Way Search Trees cont…
Algorithm: Insertion
Insert the value in the leaf node where it should belong.
If the number of values in any node exceeds the maximum, that
is, the node overflows, the middle value is extracted and is
moved to the parent node (if not existing, create one with a
new label) and among the remaining values, the lower half will
remain in the node and the upper half will be stored in a new
node with a new label. In case there are two middle values,
extract the smaller value. Labeling new nodes is done from left
to right from the lowest level going up.
Split the other nodes if necessary
36 Module 3. Trees Saturday, February 15, 2020
M-Way Search Trees cont…
Algorithm: Deletion
Delete the value.
If deletion was made from a nonterminal node, the
immediate predecessor replaces the deleted value. The
immediate predecessor of a node is the largest value in the
node’s left subtree while the immediate successor of a node is
the smallest value in the node’s right subtree.
For each node that underflows, that is, a node where the
number of values is less than the minimum do:
If the nearest right sibling has more than the minimum number
of values then
37 Module 3. Trees Saturday, February 15, 2020
M-Way Search Trees cont…
Move the parent value into the underflowing node and move the smallest
value in the nearest right sibling into the parent node.
Adjust other nodes if necessary
Else
if the nearest left sibling has more than the minimum number of values
then,
Move the parent value into the underflowing node and move the
largest value in the nearest left sibling into the parent node.
Adjust other nodes if necessary
Else
Merge the values of the underflowing node, the values of the nearest right
sibling (if non-existent, nearest left sibling), and their parent node into
the leftmost node.
Adjust node if necessary
38 Module 3. Trees Saturday, February 15, 2020
The End!!!
