Chapter 3:Data structures
Trees
Trees
⚫ A tree is a collection of nodes.
⚫ The collection can be empty.
⚫ If not empty, a tree consists of a distinguished node r (the root), and
zero or more nonempty sub-trees T1,T2, ...., Tk, each of whose roots
are connected by an edge from r
2
Some Terminologies
Child and parent
Every node except the root has one parent (J is a parent of P
and Q)
A node can have an arbitrary number of children (A has 6
while D has 1)
Leaves/External Nodes
Nodes with no children (B, C, H, I, P, Q, K, L, M, N)
Sibling
nodes with same parent (P and Q)
Internal node
A node with at least one child (A,D,E,F,G,J)
3
Some Terminologies…
Path
is a sequence of nodes from root to a node (arbitrary node in
the tree).
Length
Number of edges on the path from node x to node y
Depth of a node
Number of edges from the root to that node (Depth of C =1)
The depth of a tree is equal to the depth of the deepest
leaf (=3)
4
Some Terminologies…
Height of a node
length of the longest path from that node to a leaf (E=2)
all leaves are at height 0
The height of a tree is equal to the height of the root
Ancestor and descendant
The ancestors of a node are all the nodes along the path from the root to the
node.
5 Descendant node reachable by repeated proceeding from parent to child.
A Tree Representation
⚫ A node is represented by an object
storing
⚫⚫Element
Parent node B
⚫ Sequence of children nodes
A D F
C E
6
Binary Tree
⚫ A binary tree is a tree with the following
properties: Applications:
⚫ Each internal node has at most two arithmetic
children (degree of two) expressions
⚫ The children of a node are an ordered pair decision processes
searching
⚫ We call the children of an internal node left
A
child and right child
⚫ Alternative recursive definition: a binary
B C
tree is either
⚫ a tree consisting of a single node, OR D E F G
⚫ a tree whose root has an ordered pair of
H I
children, each of which is a binary
10 tree
Binary Tree ADT
⚫ The Binary Tree ADT extends ⚫ Update methods may be
defined by data structures
the Tree ADT, i.e., it inherits
implementing the Binary
all the methods of the Tree Tree ADT
ADT
⚫ Additional methods:
⚫position leftChild(p)
⚫position rightChild(p)
⚫position sibling(p)
8
Data Structure for Binary Trees
⚫ A node is represented
B
by an object storing
⚫Element A D
⚫Parent node
⚫Left child node C E
⚫Right child node
9
Examp
le
Struct Node{
Int data;
Node *
parent; Node
*Lchiled;
Node *
Rchiled;
}Node
*root=NULL;
10
Example: Expression Trees
⚫ One of the application of binary is representing arthematic exression
⚫ Leaves are operands (constants or variables)
⚫ The other nodes (internal nodes) contain operators
⚫ Will not be a binary tree if some operators are not binary
11
Tree traversal
⚫ Used to print out the data in a tree in a certain order
⚫ Pre-order traversal
⚫ Print the data at the root
⚫ Recursively print out all data in the left subtree
⚫ Recursively print out all data in the right subtree
12
Preorder, Postorder and Inorder
⚫ Preorder traversal
⚫node, left, right
⚫prefix expression
⚫ ++a*bc*+*defg
13
Preorder, Postorder and
Inorder
⚫ Postorder traversal
⚫left, right, node
⚫postfix expression
⚫abc*+de*f+g*
+
⚫ Inorder traversal
⚫left, node, right.
⚫infix expression
⚫a+b*c+d*e+f*
14
g
Preorder, Postorder and
Inorder
18
Binary Search
Trees
⚫ Stores keys in the nodes in a way so that searching, insertion and deletion
can be done efficiently.
Binary search tree property
⚫ For every node X, all the keys in its left subtree are smaller than the key
value in X, and all the keys in its right subtree are larger than the key
value in X
16
Binary Search
Trees…
A binary search Not a binary search tree
tree
17
Binary search
trees…
Two binary search trees representing the same set:
⚫ Average depth of a node is O(log N); maximum depth
of a node is O(N)
18
Implementation of
BSTStruc node
{
Int num;
Node *
parent
Node*left;
Node *
right;
}
Node
19 *root=NULL;
Inserting node in
BST
⚫ When a new node is inserted the definition of BST should
be preserved.
⚫ There are two cases to consider
⚫There is no data in the tree (root=null)
⚫Root=newnode;
⚫There is data
⚫Search the appropriate position
⚫Insert the node in that position.
20
Example- insert
node
Proceed down the tree as you would with a find
If newnode is found, do nothing (or update something)
Otherwise, insert newnode at the last spot on the path
traversed
Time complexity = O(height of the
tree)
21
Searching
BST
⚫ If we are searching for 15, then we are done.
⚫ If we are searching for a key < 15, then we should search in
the left subtree.
⚫ If we are searching for a key > 15, then we should search in
the right subtree.
22
23
Searching
(Find)
Find X: return a pointer to the node that has key X, or NULL if there is no such
node
Node *searchBST(node *root, int x)
{
If(root==NULL | | root->num==x)
Return (root)
Else if(root->num>x)
Return (searchBST(root->left, x)
Else
Return (searchBST(root->right, x))
}
Time complexity
O(height of the tree)
24
findMi
⚫nReturn the node containing the smallest element in the tree
⚫ Start at the root and go left as long as there is a left child. The stopping
point is
the smallest element
Node*findMin(node*root)
{
If(root==NULL)
Return Null;
Ellse if(root->left==Null)
Return root
Else
Return(findMin(root->left)
}
⚫ Similarly for findMax
⚫ Time complexity = O(height of the tree)
25
findMa
x⚫ Finds the maximum element in BST
⚫ Start at the root and go right as long as there is a right child. The stopping
point
is the largest element
Node*findMin(node*root)
{
If(root==NULL
) Return
Null;
Ellse if(root-
>right==Null)
Return root
Else
Return(findMin(
26
root->right)
delet
eWhen we delete a node, we need to consider how we take
⚫
care of the children of the deleted node.
⚫When a node is deleted the definition of a BST should
be maintained.
⚫ When a node is deleted four cases should be considered
⚫Case1: Deleting a leaf node (a node with no chiled )
⚫Case2: Deleting a node having only one child
⚫Case3: Deleting a node having two child
⚫Case4: Deleting a root node
27
delet
eThree cases:
(1) the node is a leaf
⚫ Delete it immediately
(2) the node has one
child
⚫ Adjust a pointer
from the parent to
bypass that node
⚫ Example delete
node 4, make
node 2 pointer
point to node 3
28
delet
e(3) the node has 2 children
Copy the node containing the largest element in the left( or the smallest element
in
the right)to the node to be deleted
Delete the copied node
The picture below shows deleting node2
Time complexity = O(height of the
tree)
29
Delete the
root
⚫ If BST has only one node, make root to point to nothing
⚫ Root=NULL
Otherwise,
copy the node containing the largest element in the left( or
the smallest element in the right)to the node to be deleted
Delete the copied node
30
