Data Structures & Algorithms
Binary Search Trees (BST)
Binary Search Trees
▪ When we store ordered data in an array, we have a
very efficient search algorithm, the binary search
▪ However, we have very inefficient insertion and
deletion algorithms that require shifting data in the
array
2
Binary Search Trees
▪ To provide for efficient insertions and deletions, we
developed the linked list
▪ The problem with linked lists, however, is that their
search algorithms are sequential searches, which are
very inefficient
▪ Can’t we get the best of both worlds (i.e.,
efficient search, insertion, and deletion
algorithms)?
3
Binary Search Trees
▪ The binary search tree is a binary tree with the
following properties:
► All items (keys) in the left subtree are less than the
root’s key
► All items (keys) in the right subtree are greater than
the root’s key
► Each subtree is, itself, a binary search tree
4
Binary Search Trees
Here you can see the
basic structure of a
binary search tree
5
Binary Search Trees vs Binary Trees
A binary search tree
6 6
2 8 2 8
1 4 1 4
3 3 7
Not a binary search tree,
but a binary tree
6
Examples - Non Binary Search Trees
a) 22 > 17
Here we see more examples of b) 11 < 17
binary trees that are not binary
search trees … why? c) 11 > 6
d) 22 > 17
7
Representation of BSTs
▪ BST can be represented by a linked data structure
where each node is an object
► In addition to a key field, each node contains fields
left, and right, that correspond to its left child and
right child
► If a child or parent is missing, the appropriate field
contains the value NULL
► The root is only node in the tree, whose parent field
is NULL
8
Binary Search Trees
▪ Note: we have written this definition in a way that
ensures that no two entries in a binary search tree can
have equal keys
▪ Although it is possible to modify the definition to allow
entries with duplicate keys, it makes the algorithms
somewhat more complicated
▪ If duplicates need to be accounted for, they can be
stored in another data structure (e.g., list)
9
Search Tree Property:Duplicate Keys
▪ The duplicate keys can all be kept in the left subtree, or
all in the right subtree. It doesn’t matter which we
choose, but it matters that the choice is the same for
the whole implementation.
▪ Another issue: with duplicate keys, it is important to
have extra operations in the interface: getAll, and
removeAll
10
Binary Search Trees
▪ Operations
► Insertion
► Search
► Traversal
► Deletion
11
Inserting a value into a BST
▪ The first value inserted goes at the root
▪ Every node inserted becomes a leaf
▪ Descend left or right depending on value
12
Inserting Item 5 to the Tree
t
6 Tree root node
t
2 8 NULL NULL
t
1 NULL NULL 4 NUL
L
3 NULL NULL 5 NULL NULL
New Node
13
Searching the tree
▪ Start at the root
▪ Is target = value at current node?
► We’re done
▪ Is target < value at current node?
► Yes: search left subtree
► No: search right subtree
14
Tree Search uses Sub-trees
Search Starts from the Root
15
Deleting from a BST
▪ If a node z has no children, we modify its parent to
replace z with NULL as child
▪ If node z has one child, we splice out z by making a
new link between its child and its parent
▪ If node z has two children, we splice out z’s successor
y, which has no left child and replace the contents of z
with the contents of y
16
remove in a binary search tree
Three cases for
remove(x):
Case 1: x occurs at a leaf
Simply remove the node containing x
25 40
15
5 20 45 25
15 40
18
removeElement(45)
-------------> 5 20
18
17
remove in a binary search tree
Case 2: x occurs at a node with one child v
Remove the node containing x and make v a direct child
of
x’s parent (if any)
25
15 40
5 20 45
removeElement(20) 25
18
>
15 40
5 18 45
18
remove in a binary search tree
Case 3: x occurs at a node with two children
First replace x with smallest value in right subtree of x.
This value occurs at a node with no left child. So we can
delete this node using one of the two previous cases
25
15 40
45 25
5 20
18 40
18
removeElement(15) 45
5 20
>
18
<--- Now remove
this 19
Deleting a node with two children
6 6
2 8 3 8
1 5 1 5
3 3
4 Deletion of node 2 4
20
Minimum Function
▪ The minimum element of BST is the left most node of left
sub tree
▪ Therefore the minimum can always be found by tracking
the left child pointers until an empty sub tree is reached
▪ If there is no left sub tree then minimum key is at root
(i.e. key[ x])
Tree-Minimum(tree)
{
while( tree->left != NULL)
tree = tree->left;
return tree
}
21
Maximum Function
▪ The maximum element of BST is the right most node of
right sub tree
▪ Therefore the maximum can always be found by
tracking the right child pointers until an empty sub tree
is reached
Tree-Maximum( tree)
{
while( tree->right!= NULL) tree =
tree->right;
return tree
22
Successor Function
▪ The successor of a node x, is node y, that has the
smallest key greater than that of x
► If x has a right subtree, then successor(x) is the
left most element in that sub tree
► If x has no right sub tree, then successor(x) is the
lowest ancestor of x (above x on the path to the
root) that has x in its left sub tree
23
Examples - Successor Function
▪ The successor of node with key 15 is node with key 17
▪ The successor of node with key 7 is node with key 9
▪ The successor of node with key 13 is node with key 15
24
Predecessor Function
▪ The predecessor is the node that has the largest key
smaller than that of x
► If x has a left sub tree, then the predecessor must
be the right most element of the left sub tree
► If x has no left subtree, then predecessor (x) is the
lowest ancestor of x (above x on the path to the
root) that has x in its right subtree
25
Examples - Predecessor Function
▪ The predecessor of node with key 6 is node with key 4
▪ The predecessor of node with key 15 is node with key 13
▪ The predecessor of node with key 17 is node with key 15
26
Data Structures: A Pseudocode
Approach with C, Second 27
Edition
Data Structures: A Pseudocode
Approach with C, Second 28
Edition
