Transcript if - Read

GRIFFITH
COLLEGE
DUBLIN
Data Structures, Algorithms &
Complexity
Insertion and Deletion in BST
Lecture 9
1
Introduction




Insertion and Deletion from a binary search tree
cause the dynamic set to change
The data structure must be modified to reflect this
while maintaining the search tree property
Insertion proves to be a relatively straightforward
operation
Deletion as we will see is slightly more complicated
Lecture 9
2
Insertion

Take the following tree ask how would we insert a node with
key 13 into the tree?
12
5
2
18
9
15
19
17
Lecture 9
3
Insertion

The easiest way is to start at the root and travel down the tree
until you find a leaf position at which the insertion takes place
12
5
2
18
15
9
13
19
17
Lecture 9
4
Insertion Algorithm
Tree-Insert(T, z)
y = nil
x = root[T]
while x <> nil do
y=x
if key[z] < key[x] then
else
x = right[x]
endwhile
parent[z] = y
if y = nil then
root[T] = z
else
if key[z] < key[y] then
else
right[y] = z
endif
endalg
Lecture 9
x = left[x]
left[y] = z
5
Discussion





The variable x is used to trace the path down the
tree
The variable y always holds a reference to the parent
of x
This is needed to splice x in at the correct position in
the tree
Tree insert will at worst have to travel to the furthest
leaf on the tree, i.e. the height of the tree
Therefore, tree insert runs in O(h) time
Lecture 9
6
Deletion

The procedure for deleting a given node z from a
binary search tree will take as an argument a
reference to a node (z)

The procedure needs to consider three cases

If z has no children simply remove it


If the node has only a single child, we “splice out” z
by making a new link between its child and its parent
If the node has two children, we splice out z’s
successor y, which has at most one child, and then
replace the contents of z with the contents of y
Lecture 9
7
Deletion of a leaf

If z has no children, simply delete it
15
15
5
3
5
16
12
3
20
z
10
13
18
12
10
23
16
20
18
23
6
6
7
7
Lecture 9
8
Deletion where z has one child
15
z
5
3
16
20
13
20
5
12
10
15
18
3
23
12
10
6
18
23
13
6
7
7
Lecture 9
9
Deletion where z has two children
15
z
z
5
3
y
16
6
12
10
15
20
13
18
3
23
12
10
6
16
20
13
18
23
7
7
Lecture 9
10
Algorithm
Tree-Delete(T, z)
1
if left[z] = nil or right[z] = nil then y = z
2
else y = Tree-Successor(z)
3
if left[y] <> nil then x = left[y]
4
else x = right[y]
5
if x <> nil then parent[x] = parent[y]
6
if parent[y] = nil then
7
root[T] = x
8
else if y = left[parent[y]] then
9
left[parent[y]] = x
10
else right[p[y]] = x
11
if y <> z then key[z] = key[y]
12
(if y has other fields, copy them also)
13
return y
endalg
Lecture 9
11
Discussion





In lines 1 – 2 the algorithm dermines a node y to
splice out.
This is either the input node z, if z has at most 1
child, or the successor of z, if z has two children
In lines 3-4, x is set ot the non-nil child of y, or to nil
if y has no children
In lines 5-10 the node y is spliced out by modifying
the references parent[y] and x
Here the boundary conditions when x = nil or when y
is the root need to be dealt with
Lecture 9
12
Discussion




In lines 11-12 if the successor of z was the node
spliced out, the contents of z are moved from y to z,
overwriting the previous contents
The node y is returned in line 13 for use in the calling
routine
The procedure runs in O(h) time on a tree of height h
The deletion algorithm requires the Tree-Successor
algorithm
Lecture 9
13
Tree-Successor



In a BST, if all keys are distinct, the successor of a
node x is the node with the smallest key greater than
key[x]
The structure of a binary search tree allows us to
determine the successor of a node without ever
comparing keys
The following algorithm returns the successor of a
node x in a BST if it exists and nil if x has the largest
key in the tree
Lecture 9
14
Tree-Successor
Tree-Successor(x)
if right[x] <> nil then
return Tree-Minimum(right[x])
endif
y = parent[x]
while y <> nil and x = right[y] do
x=y
y = parent[y]
endwhile
return y
endalg
Lecture 9
15
Discussion




The code is broken into two cases
If the right subtree of node x is nonempty, then the
successor of x is just the left-most node in the right
subtree, which found by calling Tree-Minimum(right)
If the right subtree of x is empty and x has a
successor y, then y is the lowest ancestor of x whose
left child is also an ancestor of x, or if x is the left
child of its parent, then the parent is the successor
To find y we simply go up the tree from x until we
encounter a node that is the left child of its parent
Lecture 9
16
Tree Successor

Here successor of 13 is 15, 12 is the successor of 10
and 10 is the successor of 7
15
5
3
16
12
10
20
13
18
23
6
7
Lecture 9
17
Balancing





Binary Search Trees can be seen to be very efficient
data structures
However, ifhte tree is changed by a series of
insertions and deletions then we can end up with an
unbalanced tree
The efficiency of such a tree may be no better than
that of a linked list
There are a number of ways we can modify BSTs to
maintain efficiency by maintaining balance
In the next lecture we will look at one of these
Lecture 9
18
Summary




Insertion into and deletion from Binary Search trees must
maintain the Binary Search Tree property
 i.e. Let x be a node in a binary search tree. If y is a node in
the left subtree of x, then key[y]  key[x]. If y is node in
the right subtree of x, then key[x]  key[y]
Insertion involves travelling down the tree until we find the
position to splice the new node into
Deletion is more complex and involves finding a successor node
Insertion and deletion can cause the BST to become unbalanced
so leading to a decrease in efficiency
Lecture 9
19