Binary search tree

Binary Search Tree

Property:
• Binary Search tree is a binary tree in which each internal node x stores an
element such that the element stored in the left sub-tree of x are less
than or equal to x and elements stored in the right sub-tree of x are
greater than or equal to x.
• The basic idea behind this data structure is to have such a storing
repository that provides the efficient way of data sorting, searching and
retrieving.
• The basic operations on a binary search tree take time proportional to
the height of the tree.
 Binary Search Algorithm
• Its only be used on a sorted array/ list.
• Uses divide and conquer technique to search list eliminating one half of the
elements after each comparison.
• Locate the middle of the array, compare the value at that location with
the search key,
• If they are equal - done!
• Otherwise, decide which half of the array contains the search key.
• Repeat the search on that half of the array and ignore the other half.
• The search continues until the key is matched or no elements remain to be
searched.
 Binary Search Trees
• Examples
5 10
10
2 45 5 45
5 30
30
2 25 45 2 25 30
10
25
Binary Not a binary
search trees search tree
 Example Binary Searches
• Find ( root, 2 )
root
10 5
10 > 2, left 5 > 2, left
5 30 2 45
5 > 2, left 2 = 2, found
2 25 45 2 = 2, found 30
10
25
 Example Binary Searches
• Find (root, 25 ) 10 5
10 < 25, right 5 < 25, right
5 30 30 > 25, left 2 45 45 > 25, left
25 = 25, found 30 > 25, left
2 25 45 30
10 < 25, right
10 25 = 25, found

25
 BST Construction
• How to build & maintain binary trees?
• Insertion
• Deletion
• Maintain key property (invariant)
• Smaller values in left sub-tree
• Larger values in right sub-tree
 Binary Search Tree – Insertion
• Algorithm
1. Perform search for value X
2. Search will end at node Y (if X not in tree)
3. If X < Y, insert new leaf X as new left sub-tree for Y
4. If X > Y, insert new leaf X as new right sub-tree for Y
• Observations
• O( log(n) ) operation for balanced tree
• Insertions may unbalance tree
 Insertion Example
• Insert ( 20 ) 10 10 < 20, right
30 > 20, left
5 30
25 > 20, left
2 25 45 Insert 20 on left

20
 Binary Search Tree – Deletion
• Algorithm
1. Perform search for value X
2. If X is a leaf, delete X
3. Else // must delete internal node
a) Replace with largest value Y on left sub-tree
OR smallest value Z on right sub-tree
b) Delete replacement value (Y or Z) from sub-tree
o Observation
• Deletions may unbalance tree
 Example Deletion (Leaf)
• Delete ( 25 )
10 10
10 < 25, right
5 30 30 > 25, left 5 30
25 = 25, delete
2 25 45 2 45
 Example Deletion (Internal Node)
• Delete ( 10 ) 10 5 5

5 30 5 30 2 30

2 25 45 2 25 45 2 25 45

Replacing 10 Replacing 5 Deleting leaf

with largest with largest
value in left value in left
subtree subtree
 Efficiency of Binary Search
• The binary search algorithm is extremely fast compared
to an algorithm that tries all array elements in order.
• About half the array is eliminated from consideration right at
the start
• Then a quarter of the array, then an eighth of the array, and so
forth
 Binary Search – Sorted Array

• Example: sorted array of integer keys. Target=7.

[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53
 Binary Search
• Example: sorted array of integer keys. Target=7
[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Find approximate midpoint

 Binary Search
• Example: sorted array of integer keys. Target=7.
[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Is 7 = midpoint key? NO.

 Binary Search
• Example: sorted array of integer keys. Target=7.
[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Is 7 < midpoint key? YES.

 Binary Search
• Example: sorted array of integer keys. Target=7.
[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Search for the target in the area before midpoint.

 Binary Search
• Example: sorted array of integer keys. Target=7
[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Find approximate midpoint

 Binary Search
• Example: sorted array of integer keys. Target=7.
[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Target = key of midpoint? NO.

 Binary Search
• Example: sorted array of integer keys. Target=7.
[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Target < key of midpoint? NO.

 Binary Search
• Example: sorted array of integer keys. Target=7
[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Target > key of midpoint? YES.

 Binary Search
• Example: sorted array of integer keys. Target=7
[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Search for the target in the area after midpoint.

 Binary Search
• Example: sorted array of integer keys. Target=7.
[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Find approximate midpoint.

Is target = midpoint key? YES.
 Relation to Binary Search Tree
• Array of previous example: 3 6 7 11 32 33 53

• Corresponding complete binary search tree

 Search for target = 7
• Find midpoint: 3 6 7 11 32 33 53

• Start at root:
11
6 33

3 7 32 53
 Search for target = 7

• Search left subarray: 3 6 7 11 32 33 53

• Search left subtree:

11
6 33

3 7 32 53
 Search for target = 7
• Find approximate midpoint of sub-array:
3 6 7 11 32 33 53

• Visit root of sub-tree: 11

6 33

3 7 32 53
 Search for target = 7
• Search right subarray: 3 6 7 11 32 33 53

• Search right subtree:

11
6 33

3 7 32 53
Any Questions..??