Fundamentals of Information Structures
Tree
Dr. Jianbing Ni
Department of Electrical & Computer Engineering
Queen’s University at Kingston
ELEC 278
Outline
• Tree
• Binary Trees
• Tree Traversals
– Depth-first traversal
– Breadth-first traversal
• Search trees
– Searching
– Implementation
• AVL Trees 2
3Tree
• A hierarchical data structure consisting of a
collection of nodes such that each node of the
tree stores a value and a list of references to
other nodes
4Tree
• Used to represent or manipulate hierarchical
data structures
Child, Parent, Siblings
• A tree consists of elements called nodes that emanate from
a single source, called the root
• Each root ri of subtree Ti of tree T is called a child of r.
• The term grandchild is defined in a similar manner.
• The root node r of tree T is the parent of all the roots ri of
the subtrees Ti, 1 < i ≤ n.
• The term grandparent is defined in a similar manner.
• Two roots ri and rj of distinct subtrees Ti and Tj of tree T
are called siblings.
A
B DC
E F
r
r1 rnri…
…T1 Ti
Tn
5
subtree
Tree Terminology
• Root: node without parent (A)
• Internal node: node with at
least one child (A, B, C, F)
• Leaf node without children (E,
I, J, K, G, H, D)
A
B DC
G HE F
I J K
Subtree: tree consisting
of a node and its
descendants
6
Tree—Definition
A tree T is a finite, non-empty set of nodes,
T = {r} ∪ T1 ∪ T2 ∪ ·· · ∪ Tn,
with the following properties:
1. A designated node of the set, r, is called
the root of the tree; and
2. The remaining nodes are partitioned into
n ≥ 0 subsets, T1, T2, . . . , Tn, each of
which is a tree.
For convenience, we shall use the notation
T = {r, T1, T2, . . . , Tn} to denote the tree T.
A
B DC
E F
r
r1 rnri…
…T1 Ti
Tn
7
Examples of trees.
Ta = {A}
Tb = {B, {C}}
Tc = {D, {E, {F}}, {G, {H, {I}}, {J, {K}, {L}}, {M}}}
Degree
• Consider a tree T = {r, T1, T2, . . . , Tn},
n ≥ 0.
– The degree of a node is the number
of subtrees associated with that
node. E.g., the degree of tree T is n.
– A node of degree zero has no
subtrees. Such a node is called a
leaf.
A
B DC
E F
r
r1 rnri…
…T1 Ti
Tn
9
Path and Path Length
Given a tree T containing the set of nodes
R, a path in T is defined as a non-empty
sequence of nodes
P = {r1, r2, . . . , rk},
where ri ∈ R, for 1 ≤ i ≤ k such that the ith
node in the sequence, ri, is the parent of
the (i + 1)th node in the sequence ri+1.
The length of path P is k − 1.
A
B C
F GD E
H I
P={A, B, E, H}
10
Ancestor
• Consider two nodes ri and rj in a tree T.
The node ri is an ancestor of the node rj
if there exists a path in T from ri to rj.
Notice that ri and rj may be the same
node. i.e., a node is its own ancestor.
• The node ri is a proper ancestor if there
exists a path p in T from ri to rj such that
the length of the path p is non-zero.
11
A
B C
F GD E
H I
P={A, B, E, H}
P={H}
Decendant
• Similarly, node rj is a descendant
of the node ri if there exists a path
in T from ri to rj. Since ri and rj
may be the same node, a node is its
own descendant.
• The node rj is a proper descendant
if there exists a path p in T from ri
to rj such that the length of the
path p is non-zero.
12
A
B C
F GD E
H I
P={A, B, E, H}
P={H}
Depth and Height
Consider a tree T containing the set of nodes R.
• The level or depth of a node ri ∈ R in a
tree T is the length of the unique path
in T from its root r to the node ri. E.g.,the
root of T is a level zero, and the roots of
the subtrees of T are at level one.
• The height of a node ri ∈ R in a tree T is
the length of the longest path from node
ri to a leaf. Therefore, the leaves are all
at height zero.
• The height of a tree T is the height of its
root node r.
A
B C
F GD E
H I
Level 0
Level 1
Level 2
Level 3
[0][0]
[1]
[0][0]
[1][0]
[2]
[3]
13
N-ary Tree—Definition
An N-ary tree T is a finite set of nodes with the following properties:
1. Either the set is empty, T = ∅ ; or
2. The set consists of a root, R, and can have exactly N distinct N-ary trees,
i.e., the remaining nodes are partitioned into N ≥ 0 subsets, T0, T1, . . . , TN−1,
each of which is an N-ary tree such that T = {R, T0, T1, . . . , TN−1}.
14
N-ary Tree—Definition
An N-ary tree T is a tree in which each node has no more than N children.
A binary tree is the special case where m = 2 that limits its children to two.
and a ternary tree is another case with m = 3 that limits its children to three
15
Observations
• The degree of each node of an N-ary tree is no more
than N
• A Full N-ary Tree is an N-ary tree that allows each
node to have either 0 or N children.
• The empty tree, T = ∅, is a tree.
• It is inappropriate to use null to represent an empty
tree, since a null refers to nothing at all!
16
External Nodes vs. Internal Nodes
• The empty trees are called external nodes
– they have no subtrees
– they appear at the extremities of the tree
• The non-empty trees are called internal nodes
• External node: the node that does not have child nodes, also
called outer node, leaf node, or terminal node
• Internal node: the node of a tree that has child nodes, also
called inner node, inode, or branch node
17
Examples of N-ary trees.
Ta = {A, ∅, ∅, ∅},
Tb = {B, {C, ∅, ∅, ∅}, ∅, ∅},
Tc = {D, {E, {F, ∅, ∅, ∅}, ∅, ∅},
{G, {H, {I, ∅, ∅, ∅}, ∅, ∅},
{J, {K, ∅, ∅, ∅}, {L, ∅, ∅, ∅}, ∅},
{M, ∅, ∅, ∅}}, ∅}.
Two distinct binary trees.
Outline
• Tree
• Binary Trees
• Tree Traversals
– Depth-first traversal
– Breadth-first traversal
• Search trees
– Searching
– Implementation
• AVL Trees 20
Binary Trees—Definition
A binary tree T is a finite set of nodes
with the following properties:
1.Either the set is empty, T = ∅ ; or
2.The set consists of a root, r, and
exactly two distinct binary trees
TL and TR, T = {r, TL, TR}.
The tree TL is called the left subtree of
T, and the tree TR is called the right
subtree of T.
r
L1 R1
R2 R3L2 L3
L4 L5
TL TR
Left Subtree
Right Subtree
21
Representing binary trees.
Relations between height, h, and the number
of nodes, n
• A binary tree of height h ≥ 0 has at most 2h+1 − 1 nodes
• The height of a binary tree with n nodes is at least
2log 1 1n + −
23
Relation between height, h, and the
number leaves, l
• a binary tree of height h ≥ 0 has at most 2h leaves
• The height of a binary tree with l leaves is at least
2log l
24
Binary Tree Node
• Each node of the tree contains two references
to the subtrees of that node, left and right
• We explicitly represent the empty trees
• an empty tree contains neither root nor
subtrees
struct BinaryTreeNode {
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
}
Data at Tree Node
• Can be anything
• Lab 3 uses:
– Key
– (pointer to) string
• Often the case – some data provides identification (key)
and some data provides actual data.
26
Create a Binary Tree Node
// a helper function to create a new binary tree node from the
given data
struct BinaryTreeNode* newNode(int data)
{
struct BinaryTreeNode *node = (struct BinaryTreeNode *)malloc(sizeof( struct BinaryTreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
27
Example: Building a Tree
Use BinaryTreeNode to build the four-node tree of
integer values pictured as follows
10
20 30
40
root
p r
q
Example: Building a Tree
build the four-node binary tree of integer values
pictured as follows
10
20 30
40
root
p r
q
struct BinaryTreeNode *q, *r, *p, *root;
q=newNode(40);
r = newNode(30);
r->left = q;
p= newNode(20);
root= newNode(10);
root->left = p;
root->right = r;
Tree Functions
• IsEmpty()
• Isfull() – only if an array is used to implement tree
• Find() – locate a particular node by key (to get other data)
• Find_parent() – node that points to particular node
• Add_node() – some criteria for where to put nodes
• Insert_node() – insert a node at a particular place
• Delete_node() – remove a node
• Withdraw_node() – like delete_node() but actual node not free()ed –
may be inserted elsewhere
• Tree_height()
• Print_tree()
• Traverse_tree() – generalize version of print – apply some function to
every node
• And more, depending on application.
30
Outline
• Tree
• Binary Trees
• Tree Traversals
– Depth-first traversal
– Breadth-first traversal
• Search trees
– Searching
– Implementation
• AVL Trees 31
Tree Traversals
• Systematically visit all the nodes in the tree
• Perform some computation at each node in the tree
• Two main traversal methods:
– depth-first traversal
• preorder, inorder and postorder
– breadth-first traversal
32
A Sample Tree.
Recursive steps: at each node, we perform three tasks:
N: perform some actions on the node
L: select the root of the left subtree of the node
R: select the root of the right subtree of the node
Stopping conditions: get into an empty tree
Inorder Traversal of a Binary Tree
• To do an inorder traversal of a binary tree:
1. Lx:Select the left child and descend into the left
subtree
2. Nx: Output the value of X
3. Rx: Select the right child and descend into the right
subtree
34
A Sample Tree.
Preorder Traversal of a Binary Tree
To do a preorder traversal of a binary tree:
1. Nx: Visit the root first; and then
2. Lx: traverse the left subtree; and then
3. Rx: traverse the right subtree.
36
A Sample Tree.
Postorder Traversal of a Binary Tree
To do a postorder traversal of a binary tree:
1. Lx: Traverse the left subtree; and then
2. Rx: traverse the right subtree; and then
3. Nx: visit the root.
38
A Sample Tree.
Algorithm for Binary Tree InOrder
Traversal
ReturnType scanMethod(struct BinaryTreeNode *t)
{ // check of empty tree (stopping condition)
if (t.key==null)
< return information for an empty tree>
else
{
// descend to left subtree and record return information
valueLeft=scanMethod(t.left)
//visit the node

//descend to right subtree and record return information
valueRight = scanMethod(t.right);
}
return
}
40
struct BinaryTreeNode {
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
}
Algorithm for Binary Tree InOrder
Traversal
ReturnType scanMethod(struct BinaryTreeNode *t)
{ // check of empty tree (stopping condition)
if (t==NULL)
< return information for an empty tree>
else
{
// descend to left subtree and record return information
valueLeft=scanMethod(t.left)
//visit the node

//descend to right subtree and record return information
valueRight = scanMethod(t.right);
}
return
}
41
struct BinaryTreeNode {
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
}
Algorithm for Binary Tree InOrder
Traversal
ReturnType scanMethod(struct BinaryTreeNode *t)
{ // check of empty tree (stopping condition)
if (t==NULL)
< return information for an empty tree>
else
{
ReturnType valueLeft; valueRight;
// descend to left subtree and record return information
valueLeft=scanMethod(t->left)
//visit the node

//descend to right subtree and record return information
valueRight = scanMethod(t.right);
}
return
}
42
struct BinaryTreeNode {
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
}
Algorithm for Binary Tree InOrder
Traversal
ReturnType scanMethod(struct BinaryTreeNode *t)
{ // check of empty tree (stopping condition)
if (t==NULL)
< return information for an empty tree>
else
{
ReturnType valueLeft; valueRight;
// descend to left subtree and record return information
valueLeft=scanMethod(t->left)
//visit the node

//descend to right subtree and record return information
valueRight = scanMethod(t.right);
}
return
}
43
struct BinaryTreeNode {
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
}
Algorithm for Binary Tree InOrder
Traversal
ReturnType scanMethod(struct BinaryTreeNode *t)
{ // check of empty tree (stopping condition)
if (t==NULL)
< return information for an empty tree>
else
{
ReturnType valueLeft; valueRight;
// descend to left subtree and record return information
valueLeft=scanMethod(t->left)
//visit the node

//descend to right subtree and record return information
valueRight = scanMethod(t->right);
}
return
}
44
struct BinaryTreeNode {
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
}
Preorder Design Pattern

valueLeft = scanMethod(t->left);
valueRight = scanMethod(t->right);
45
Postorder Design Pattern
valueLeft = scanMethod(t->left);
valueRight = scanMethod(t->right);

46
Example: outputs the value of the node
to the console
//list the nodes of a binary tree using inorder traversal
void inorderOutput(struct BinaryTreeNode *t)
{
// the recursive scan terminates on an empty subtree
if (t.key!=null)
{
inorderOutput(t.left); //descend to left
System.out.print(t.key + “ “);
inorderOutput(t.right); //descend to right
}
}
47
Example: outputs the value of the node
to the console
//list the nodes of a binary tree using inorder traversal
ReturnType scanMethod(struct BinaryTreeNode *t)
{ // check of empty tree (stopping condition)
if (t==NULL)
< return information for an empty tree>
else
{
ReturnType valueLeft; valueRight;
// descend to left subtree and record return information
valueLeft=scanMethod(t->left)
//visit the node

//descend to right subtree and record return information
valueRight = scanMethod(t->right);
}
return
}
48
Example: outputs the value of the node
to the console
//list the nodes of a binary tree using inorder traversal
void inorderOutput(struct BinaryTreeNode *t)
{
// the recursive scan terminates on an empty subtree
if (t!=NULL)
{
inorderOutput(t->left); //descend to left
printf(“%d \n”, t->data)
inorderOutput(t->right); //descend to right
}
}
49
Height of a Binary Tree






+
−
=
nonemptyisTifTheightTheight
emptyisTif
Theight
RL ))(),(max(1
1
)(
• The height of a tree is the length of longest path
from the root to leaves
A
B C
F GD E
H I
[0][0]
[1]
[0][0]
[1][0]
[2]
[3]
int getHeight(struct BinaryTreeNode *t)
{
int heightLeft, heightRight, heightval;
51
int getHeight(struct BinaryTreeNode *t)
{
int heightLeft, heightRight, heightval;
if (t == null)
return heightval = -1;
else
{
heightLeft = height(t.left);
heightRight = height(t.right);
heightval = 1 + ((heightLeft > heightRight)?
heightLeft : heightRight);
}
return heightval;
}
52
int getHeight(struct BinaryTreeNode *t)
{
int heightLeft, heightRight, heightval;
if (t == null)
return heightval = -1;
else
{
heightLeft = getHeight(t->left);
heightRight = getHeight(t->right);
heightval = 1 + ((heightLeft > heightRight)?
heightLeft : heightRight);
}
return heightval;
}
53
int getHeight(struct BinaryTreeNode *t)
{
int heightLeft, heightRight, heightval;
if (t == null)
return heightval = -1;
else
{
heightLeft = getHeight(t ->left);
heightRight = getHeight(t->right);
heightval = 1 + ((heightLeft > heightRight)?
heightLeft : heightRight);
}
return heightval;
}
54
Breadth-First Traversal
• A breadth-first traversal visits
the nodes in the order of their
depth in the tree.
• At each depth, the nodes are
visited from left to right.
55
Queue contents during the breadth-first traversal of the
tree
Queue contents during the breadth-first traversal of the
tree
Queue contents during the breadth-first traversal of the
tree
Queue contents during the breadth-first traversal of the
tree
Queue contents during the breadth-first traversal of the
tree
Queue contents during the breadth-first traversal of the
tree
Queue contents during the breadth-first traversal of the
tree
Queue contents during the breadth-first traversal of the
tree
Queue contents during the breadth-first traversal of the
tree
Queue contents during the breadth-first traversal of the
tree
Queue contents during the breadth-first traversal of the
tree
Implementing Breadth-First Traversal
Use a queue as follows:
First, enqueue the root node of the given tree, provided it is not the
empty tree.
Then, repeat the following steps until the queue is empty:
1. Remove the node at the head of the queue and call it
head.
2. Visit the tree node contained in head.
3. Enqueue in order each non-empty subtree of head.
67
68
bool isEmpty (void)
{
return (count == 0);
}
bool dequeue (int *n)
{
struct item *temp = front;
if (count == 0) return
false;
*n = &(front->value);
front = front->next;
free (temp);
count--;
return true;
}
struct item {
struct item *next;
int value;
}
typdef struct item Queue;
struct item *front = NULL, *end = NULL;
int count = 0;
void enqueue (int n)
{
struct item *pnew = malloc (sizeof(struct item));
pnew -> value = n;
pnew -> next = NULL;
// update current end node (if there is one)
if (end != NULL)
end -> next = pnew;
end = pnew;
// if queue was empty, new node is also front node
if (front == NULL)
front = pnew;
count++;
}
Linked List
Implementation of
Queue – final version
69
bool isEmpty (void)
{
return (count == 0);
}
bool dequeue (struct
BinaryTreeNode **n)
{
struct item *temp = front;
if (count == 0) return false;
*n = front->value;
front = front->next;
free (temp);
count--;
return true;
}
struct item {
struct item *next;
struct BinaryTreeNode *value;
}
typdef struct item Queue;
struct item *front = NULL, *end = NULL;
int count = 0;
void enqueue (struct BinaryTreeNode *n)
{
struct item *pnew = malloc (sizeof(struct item));
pnew -> value = n;
pnew -> next = NULL;
// update current end node (if there is one)
if (end != NULL)
end -> next = pnew;
end = pnew;
// if queue was empty, new node is also front node
if (front == NULL)
front = pnew;
count++;
}
Linked List
Implementation of
Queue – final version
breadthFirstTraversal function.
1.void breadthFirstTraversal (BinaryTreeNode *node)
2. {
3. Queue *queue;
4.//inserting the node in the queue
5. if (node!=null)
6. enqueue(node);
7.//continue the iterative process until the queue is empty
8. while(!isEmpty() )
9. {
10. // dequeue a node, and output the value
11. struct BinaryTreeNode *r;
12. dequeue(&r);
13. printf(“%d, “, r->data);
14.
15. if (r->left !=null) //if a left child exists, insert it in the queue
16. enqueue(r->left);
17. if (r->right != null) // if a right child exists, insert it in the
//queue
18. enqueue(r->right);
19. }
20. }
breadthFirstTraversal function.
1.void breadthFirstTraversal (BinaryTreeNode *node)
2. {
3. Queue *queue;
4.//inserting the node in the queue
5. if (node!=null)
6. enqueue(node);
7.//continue the iterative process until the queue is empty
8. while(!isEmpty() )
9. {
10. // dequeue a node, and output the value
11. struct BinaryTreeNode *r;
12. dequeue(&r);
13. printf(“%d, “, r->data);
14.
15. if (r->left !=null) //if a left child exists, insert it in the queue
16. enqueue(r->left);
17. if (r->right != null) // if a right child exists, insert it in the
//queue
18. enqueue(r->right);
19. }
20. }
breadthFirstTraversal function.
1.void breadthFirstTraversal (BinaryTreeNode *node)
2. {
3. Queue *queue;
4.//inserting the node in the queue
5. if (node!=null)
6. enqueue(node);
7.//continue the iterative process until the queue is empty
8. while(!isEmpty() )
9. {
10. // dequeue a node, and output the value
11. struct BinaryTreeNode *r;
12. dequeue(&r);
13. printf(“%d, “, r->data);
14.
15. if (r->left !=null) //if a left child exists, insert it in the queue
16. enqueue(r->left);
17. if (r->right != null) // if a right child exists, insert it in the
//queue
18. enqueue(r->right);
19. }
20. }
breadthFirstTraversal function.
1.void breadthFirstTraversal (BinaryTreeNode *node)
2. {
3. Queue *queue;
4.//inserting the node in the queue
5. if (node!=null)
6. enqueue(node);
7.//continue the iterative process until the queue is empty
8. while(!isEmpty() )
9. {
10. // dequeue a node, and output the value
11. struct BinaryTreeNode *r;
12. dequeue(&r);
13. printf(“%d, “, r->data);
14.
15. if (r->left !=null) //if a left child exists, insert it in the queue
16. enqueue(r->left);
17. if (r->right != null) // if a right child exists, insert it in the
//queue
18. enqueue(r->right);
19. }
20. }
Outline
• Tree
• Binary Trees
• Tree Traversals
– Depth-first traversal
– Breadth-first traversal
• Search trees
– Searching
– Implementation
• AVL Trees 74
Motivation
• Array and LinkedLists are list collections that store elements
by position
– Require n times for scanning n elements
• Many computer applications store data by value instead of
position
– a registrar’s database stores grade record using students’ SIN as a
key
– Credit check using credit card number as a key
• A special form of binary trees, called binary search tree, is
designed as search engines
– Access and update operations on n elements with log2n times at the
worst case
75
Binary Search Trees
• A binary search tree is a binary tree in which each
element resides on a unique path from the root
• The tree can store data elements that have a natural
order
– Two data elements satisfy a comparison relation
• < (less than)
• == (equal to)
• > (greater than)
76
Search Tree Ordering
A binary search tree T is a finite set of nodes.
• Either the set is empty, T = ∅ ; or
• The set consists of a root r and exactly two binary
search trees TL and TR, T = {r, TL, TR}, such that the
following properties are satisfied:
1. All the values of the nodes contained in left subtree,
TL, are less than r, i.e., ∀k ∈ TL : k < r.
2. All the values of the nodes contained in the right
subtree, TR, are greater than r, i.e., ∀k ∈ TR : k > r.
77
78
Examples of search trees.
A binary search tree.
Implementing Search Trees
• a search tree is a Binary Tree
• a search tree includes the functions:
– findMin and findMax
– find, isMember, insert, and withdraw
81
BinaryTreeNode structure.
struct BinaryTreeNode {
int data;
BinaryTreeNode *left;
Binary TreeNode *right;
}
findMin Function
• To find the minimum start at the root and follow the
chain of left subtrees until you get to the node that has
an empty left subtree
• The worst case running time of findMin is searching n
elements
• The average case is searching log2 n elements
83
BinaryTreeNode* FindMin(BinaryTreeNode *node)
{
if(node==NULL)
{
/* There is no element in the tree */
return NULL;
}
if(node->left!=null ) /* Go to the left sub tree to find the min
element */
return FindMin(node->left);
else
return node;
}
84
BinaryTreeNode* FindMin(BinaryTreeNode *node)
{
if(node==NULL)
{
/* There is no element in the tree */
return NULL;
}
else if(node->left!=null ) /* Go to the left sub tree to find the min
element */
return FindMin(node->left);
else
return node;
}
85
BinaryTreeNode* FindMin(BinaryTreeNode *node)
{
if(node==NULL)
{
/* There is no element in the tree */
return NULL;
}
else if(node->left!=null ) /* Go to the left sub tree to find the min
element */
return FindMin(node->left);
else
return node;
}
86
BinaryTreeNode* FindMin(BinaryTreeNode *node)
{
if(node==NULL)
{
/* There is no element in the tree */
return NULL;
}
else if(node->left!=null ) /* Go to the left sub tree to find the min
element */
return FindMin(node->left);
else
return node;
}
87
BinaryTreeNode* FindMax(BinaryTreeNode *node)
{
if(node==NULL)
{
/* There is no element in the tree */
return NULL;
}
else if(node->right!=null ) /* Go to the left sub tree to find the min
element */
return FindMax(node->right);
else
return node;
}
88
Implementing Finding the Node with the Maximum Value
BinaryTreeNode* FindMax(BinaryTreeNode *node)
{
if(node==NULL)
{
/* There is no element in the tree */
return NULL;
}
else if(node->right!=null ) /* Go to the left sub tree to find the min
element */
return FindMax(node->right);
else
return node;
}
89
Searching a Binary Tree
• The search begins at the root node of the tree.
• If the value of the search, x, matches the value in the
root r, the search terminates successfully.
• Of x is less than r, the left subtree is searched
• Otherwise, x must be greater than r, in which case the
right subtree is searched.
90
Example:
• Find 32
• Find 60
• Find 12
91
find Method
• recursive function
• each recursive call descends one level in the tree
• each call does at most one data comparison
92
BinaryTreeNode * find(BinaryTreeNode *node, int data)
{
if(node==NULL)
return NULL; /* Element is not found */
if(data > node->data)
return Find(node->right, data); /* Search in the right sub tree. */
else if(data < node->data)
return Find(node->left, data); /* Search in the left sub tree. */
else
return node; /* Element Found */
}
93
BinaryTreeNode * find(BinaryTreeNode *node, int data)
{
if(node==NULL)
return NULL; /* Element is not found */
if(data > node->data)
return Find(node->right, data); /* Search in the right sub tree. */
else if(data < node->data)
return Find(node->left, data); /* Search in the left sub tree. */
else
return node; /* Element Found */
}
94
BinaryTreeNode * find(BinaryTreeNode *node, int data)
{
if(node==NULL)
return NULL; /* Element is not found */
if(data > node->data)
return find(node->right, data); /* Search in the right sub tree. */
else if(data < node->data)
return Find(node->left, data); /* Search in the left sub tree. */
else
return node; /* Element Found */
}
95
BinaryTreeNode * find(BinaryTreeNode *node, int data)
{
if(node==NULL)
return NULL; /* Element is not found */
if(data > node->data)
return find(node->right, data); /* Search in the right sub tree. */
else if(data < node->data)
return find(node->left, data); /* Search in the left sub tree. */
else
return node; /* Element Found */
}
96
BinaryTreeNode * find(BinaryTreeNode *node, int data)
{
if(node==NULL)
return NULL; /* Element is not found */
if(data > node->data)
return Find(node->right, data); /* Search in the right sub tree. */
else if(data < node->data)
return Find(node->left, data); /* Search in the left sub tree. */
else
return node; /* Element Found */
}
97
Example for Inserting a new value into
a binary search tree
• Building a binary search tree by adding integer values
from the sequence {35, 18, 25, 48, 25, 20}
98
Building Binary Search Tree
• Elements are inserted into a binary tree using a strategy
that maintains the ordering among the subtrees
– The first element becomes the root node
– All subsequent elements are added as leaf nodes at the end of a
unique path
• Identifying the path is a recursive process that begins at
the root
– Each step involves comparing the value of the new element,
called item, with the value in the current node on the path
99
Insertion Strategy
• If the value of the new element is equal to the value of the
current node
– Perform no action
• If the value of the new element is less than the value of the
current node proceed to the left subtree of the node
– If the left subtree is not empty, repeat the insertion
strategy by comparing item with the root of the subtree
– Otherwise, the left subtree is empty, and we reach the
location for the new element at the end of the “insertion”
path
• Allocate a new node with item as its value
• Attach the node to the tree as the left child
100
Insertion Strategy (con’t)
• If the value of the new element is greater than the value of
the current node proceed to the right subtree of the node
– If the right subtree is not empty, repeat the insertion strategy by
comparing item with root of the subtree
– Otherwise, the right subtree is empty
• Allocate a new node with item as its value
• Attach the node to the tree as the right child
101
BinaryTreeNode * Insert(BinaryTreeNode *node, int data)
{
if(node==NULL)
{
BinaryTreeNode));
temp -> data = data;
temp -> left = temp -> right = NULL;
return temp;
}
if(data >(node->data))
{
node->right = Insert(node->right, data);
}
else if(data < (node->data))
{
node->left = Insert(node->left, data);
}
/* Else there is nothing to do as the data is already in the tree. */
return node;
} 102
BinaryTreeNode * Insert(BinaryTreeNode *node, int data)
{
if(node==NULL)
{
BinaryTreeNode *temp;
temp = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
temp -> data = data;
temp -> left = temp -> right = NULL;
return temp;
}
if(data >(node->data))
{
node->right = Insert(node->right, data);
}
else if(data < (node->data))
{
node->left = Insert(node->left, data);
}
/* Else there is nothing to do as the data is already in the tree. */
return node;
}
103
BinaryTreeNode * Insert(BinaryTreeNode *node, int data)
{
if(node==NULL)
{
BinaryTreeNode *temp;
temp = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
temp -> data = data;
temp -> left = temp -> right = NULL;
return temp;
}
if(data >(node->data))
{
node->right = Insert(node->right, data);
}
ielse if(data < (node->data))
{
node->left = Insert(node->left, data);
}
/* Else there is nothing to do as the data is already in the tree. */
return node;
f(
} 104
BinaryTreeNode * Insert(BinaryTreeNode *node, int data)
{
if(node==NULL)
{
BinaryTreeNode *temp;
temp = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
temp -> data = data;
temp -> left = temp -> right = NULL;
return temp;
}
if(data >(node->data))
{
node->right = Insert(node->right, data);
}
else if(data < (node->data))
{
node->left = Insert(node->left, data);
}
/* Else there is nothing to do as the data is already in the tree. */
return node;
f(
} 105
BinaryTreeNode * Insert(BinaryTreeNode *node, int data)
{
if(node==NULL)
{
BinaryTreeNode *temp;
temp = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
temp -> data = data;
temp -> left = temp -> right = NULL;
return temp;
}
if(data >(node->data))
{
node->right = Insert(node->right, data);
}
ielse if(data < (node->data))
{
node->left = Insert(node->left, data);
}
/* Else there is nothing to do as the data is already in the tree. */
return node;
} 106
Removing a leaf node from a binary search tree.
25
65
108
Removing Items from a Binary Search
Tree
• Locate the node that needs to be removed
• removing a node (with none or one child) is easy
• remove a non-leaf node (with both left and right
subtrees), swap it with the value of the node with the
smallest value of the node in the right subtree or with
the largest one in the left subtree
– after the swap, delete the node with the smallest value in the
right subtree or with the largest one in the left subtree
109
Removing a non-leaf node from a binary search tree.
BinaryTreeNode * Delete(BinaryTreeNode *node, int data)
{
BinaryTreeNode *temp;
if(node==NULL)
return NULL;
else if(data < node->data)
node->left = Delete(node->left, data);
else if(data > node->data)
node->right = Delete(node->right, data);
else
{
/* Now We can delete this node and replace with either minimum element
in the right sub tree or maximum element in the left subtree */
if(node->right && node->left)
{
/* Here we will replace with minimum element in the right sub tree */
temp = FindMin(node->right);
node -> data = temp->data;
/* As we replaced it with some other node, we have to delete that node */
node -> right = Delete(node->right, temp->data);
}
BinaryTreeNode * Delete(BinaryTreeNode *node, int data)
{
BinaryTreeNode *temp;
if(node==NULL)
return NULL;
else if(data < node->data)
node->left = Delete(node->left, data);
else if(data > node->data)
node->right = Delete(node->right, data);
else
{
/* Now We can delete this node and replace with either minimum element
in the right sub tree or maximum element in the left subtree */
if(node->right && node->left)
{
/* Here we will replace with minimum element in the right sub tree */
temp = FindMin(node->right);
node -> data = temp->data;
/* As we replaced it with some other node, we have to delete that node */
node -> right = Delete(node->right, temp->data);
}
25
BinaryTreeNode * Delete(BinaryTreeNode *node, int data)
{
BinaryTreeNode *temp;
if(node==NULL)
return NULL;
else if(data < node->data)
node->left = Delete(node->left, data);
else if(data > node->data)
node->right = Delete(node->right, data);
else
{
/* Now We can delete this node and replace with either minimum element
in the right sub tree or maximum element in the left subtree */
if(node->right && node->left)
{
/* Here we will replace with minimum element in the right sub tree */
temp = FindMin(node->right);
node -> data = temp->data;
/* As we replaced it with some other node, we have to delete that node */
node -> right = Delete(node->right, temp->data);
}
25
BinaryTreeNode * Delete(BinaryTreeNode *node, int data)
{
BinaryTreeNode *temp;
if(node==NULL)
return NULL;
else if(data < node->data)
node->left = Delete(node->left, data);
else if(data > node->data)
node->right = Delete(node->right, data);
else
{
/* Now We can delete this node and replace with either minimum element
in the right sub tree or maximum element in the left subtree */
if(node->right && node->left)
{
/* Here we will replace with minimum element in the right sub tree */
temp = FindMin(node->right);
node -> data = temp->data;
/* As we replaced it with some other node, we have to delete that node */
node -> right = Delete(node->right, temp->data);
}
30
else
{
/* If there is only one or zero children then we can directly
remove it from the tree and connect its parent to its child */
temp = node;
if(node->left == NULL)
node = node->right;
else if(node->right == NULL)
node = node->left;
free(temp); /* temp is no longer required */
}
}
return node;
}
30
else
{
/* If there is only one or zero children then we can directly
remove it from the tree and connect its parent to its child */
temp = node;
if(node->left == NULL)
node = node->right;
else if(node->right == NULL)
node = node->left;
free(temp); /* temp is no longer required */
}
}
return node;
}
Delete 10
25
Example:
• Delete 10
• Delete 50
• Delete 62
117
Outline
• Tree
• Binary Trees
• Tree Traversals
– Depth-first traversal
– Breadth-first traversal
• Search trees
– Searching
– Implementation
• AVL Trees 118
AVL Trees
• Problem with Binary Search Trees (BSTs) is that the worst
case running times case for search, insertion, and
withdrawal are all O(n) even though the average is O(log n)
• The problem is that a BST can become unbalanced
• A balanced binary tree: a binary tree in which the height of
the left and right subtree of any node differ by not more
than 1.
• If we could ensure that the BST remains balanced, then we
might be able to improve the worst-case performance
119
120
AVL Search Trees
AVL Trees
121
• An AVL tree: a self-balancing
binary search tree.
• The heights of the two child subtrees
of any node differ by at most one
• If at any time they differ by more
than one, rebalancing is done to
restore this property.
• If height of AVL tree is h, maximum
number of nodes can be 2h+1 – 1.
• The complexity of searching,
inserting and deletion in AVL tree is
O(log n).
Characteristics of a Good Balance
Condition
1. A good balance condition ensures that the height of a
tree with n nodes is O(log2 n).
2. A good balance condition can be maintained
efficiently. i.e., the additional work necessary to
balance the tree when an item is inserted or deleted is
O(1).
122
The AVL Balance Condition
An empty binary search tree is AVL balanced.
A non-empty binary search tree, T = {r, TL, TR}, is AVL
balanced
if both TL and TR are AVL balanced and
|hL − hR| ≤ 1,
where hL is the height of TL and hR is the height of TR.
balanceFactor = height(left subtree) − height (right
subtree)
123
balanceFactor
124
AVLTree Node Structure
typedef struct AVLTreeNode
{
int data;
struct AVLTreeNode *left;
struct AVLTreeNode *right;
int height;
}node;
AVLTree functions
node *insert(node *,int);
node *delete(node *,int);
void preorder(node *);
void inorder(node *);
int getHeight( node *);
node *rotateRight(node *);
node *rotateLeft(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int balanceFactor(node *);
int balanceFactor(node *tree)
{
int lh, rh;
if(tree==NULL)
return(-1);
if(tree->left==NULL)
lh=-1;
else
lh=1+tree->left->height;
if(tree->right==NULL)
rh=-1;
else
rh=1+tree->right->height;
return lh-rh;
}






+
−
=
nonemptyisTifTheightTheight
emptyisTif
Theight
RL ))(),(max(1
1
)(
int balanceFactor(node *tree)
{
int lh, rh;
if(tree==NULL)
return(0);
if(tree->left==NULL)
lh=-1;
else
lh=1+tree->left->height;
if(tree->right==NULL)
rh=-1;
else
rh=1+tree->right->height;
return lh-rh;
}






+
−
=
nonemptyisTifTheightTheight
emptyisTif
Theight
RL ))(),(max(1
1
)(
int balanceFactor(node *tree)
{
int lh, rh;
if(tree==NULL)
return(0);
if(tree->left==NULL)
lh=-1;
else
lh=tree->left->height;
if(tree->right==NULL)
rh=-1;
else
rh=1+tree->right->height;
return lh-rh;
}






+
−
=
nonemptyisTifTheightTheight
emptyisTif
Theight
RL ))(),(max(1
1
)(
int balanceFactor(node *tree)
{
int lh, rh;
if(tree==NULL)
return(0);
if(tree->left==NULL)
lh=-1;
else
lh=tree->left->height;
if(tree->right==NULL)
rh=-1;
else
rh=tree->right->height;
return lh-rh;
}






+
−
=
nonemptyisTifTheightTheight
emptyisTif
Theight
RL ))(),(max(1
1
)(
Inserting Items into an AVL Tree
• when an item is inserted, the heights of the nodes
along the insertion path may increase by one
• when the height of a node increases, an imbalance
may result
• The imbalanced condition is:
– balanceFactor is 2 or -2
• an imbalance in an AVL tree can be fixed by doing
a rotation
• two kinds of rotations—single and double
131
132
133
75
134
(-2)
(-2)
(-1)
(-1)
AVLTree Node Structure
typedef struct AVLTreeNode
{
int data;
struct AVLTreeNode *left;
struct AVLTreeNode *right;
int height;
}node;
RR
R
L
136
LL
L
R
137
Single Left Rotation
R
R
138
node * rotateLeft(node *p)
{
node *rc;
rc=p->right;
p->right=rc->left;
rc->left = p;
p->height=getHeight(p);
rc->height=getHeight(rc);
return rc;
}
R
R
Single Right Rotation
L
L
node * rotateRight(node *p)
{
node *lc;
lc = p->left
p->left = lc->right
lc->right = p;
p->height=getHeight(p);
lc->height=getHeight(lc);
return lc;
}
L
L
AVLTree functions
node *insert(node *,int);
node *delete(node *,int);
void preorder(node *);
void inorder(node *);
int getHeight( node *);
node *rotateRight(node *);
node *rotateLeft(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int balanceFactor(node *);
node * RR(node *p)
{
return rotateLeft(p);
} R
R
node * LL(node *p)
{
return rotateRight(p);
}
L
L
Double Rotation
R
L
145
node * LR(node *p)
{
node *lc = p->left
p->left=rotateLeft(lc);
return rotateRight(p);
}
L
R
146
Double Rotation
L
R
node * RL(node *p) {
node *rc = p->right;
p->right=rotateRight(rc);
return rotateLeft(p);
}
147
Double Rotations
• a double rotation is just two single rotations
• double rotations have the same properties as single
rotations:
– the result is a valid search tree
– the result is AVL-balanced
– the height of the result is the same as that of the
initial tree
148
Example
• We build an AVL tree with elements from the integer
array {24, 12, 5, 30, 20, 45, 11, 13, 9, 16}
149
BinaryTreeNode * Insert(BinaryTreeNode *node, int data)
{
if(node==NULL)
{
BinaryTreeNode *temp;
temp = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
temp -> data = data;
temp -> left = temp -> right = NULL;
return temp;
}
if(data >(node->data))
{
node->right = Insert(node->right, data);
}
else if(data < (node->data))
{
node->left = Insert(node->left, data);
}
/* Else there is nothing to do as the data is already in the tree. */
return node;
} 150
BinaryTreeNode * Insert(BinaryTreeNode *node, int data)
{
if(node==NULL)
{
BinaryTreeNode *temp;
temp = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
temp -> data = data;
temp -> left = temp -> right = NULL;
return temp;
}
if(data >(node->data))
{
node->right = Insert(node->right, data);
}
else if(data < (node->data))
{
node->left = Insert(node->left, data);
}
/* Else there is nothing to do as the data is already in the tree. */
/* Insert Code for Checking Tree Balance */
return node;
} 151
/* Get the balance factor to check whether this node became
unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced, then
// there are 4 cases
// Left Left Case
if (balance > 1 && data < node->left->data)
return LL(node);
// Right Right Case
if (balance < -1 && data > node->right->data)
return RR(node);
// Left Right Case
if (balance > 1 && data > node->left->data)
return LR(node);
// Right Left Case
if (balance < -1 && data < node->right->data)
return RL(node);
}
The Remarkable Thing About AVL
Trees
• When an AVL tree becomes unbalanced after an
insertion, exactly one single or double rotation is
required to balance the tree.
• the cost of a single or double rotation is O(1)
• the height of an AVL tree is O(log n) in the worst
therefore search, insertion and withdrawal are each
O(log n) int the worst case
153

学霸联盟