Transcript Binary Search Tree

Binary Search Tree
Chapter 10
What is BST?
binary search tree is a binary tree T such that
each internal node v of T stores an entry (k,x)
such that:
• Keys stored at nodes in the left subtree of v are
less than or equal to k.
• Keys stored at nodes in the right subtree of v are
greater than or equal to k.

Searching
Given a search key k and a node v of T.
TreeSearch, returns a node (position) w of the
subtree T(v) of T rooted at v, such that one of
the following occurs:
• w is an internal node and w's entry has key
equal to k.
• w is an external node representing k's proper
place in an inorder traversal of T(v), but k is
not a key contained in T(v).

(a) A binary search tree T representing a
dictionary D with integer keys;

(b) nodes of T visited when executing operations
find(76) (successful) and find(25) (unsuccessful) on D
O(h) – height
of tree
Analysis of BST
Update Operation
Insertion
 By the BST ordering property, a new node
is always inserted as a leaf node.

6
5
6
2
1
4
3
5
8
7
9
2
1
3
7
5
2
8
4
6
6
9
1
4
3
2
8
7
9
1
8
4
3
7
5
9

Insertion of an entry with key 78 into the
search tree. Finding the position to insert is
shown in (a),

The resulting tree is shown in (b).
Removal
 There are three cases:
1. The node to be deleted is a leaf node.
2. The node to be deleted has one non-empty child.
3. The node to be deleted has two non-empty children.
CASE 1: DELETING A LEAF NODE
Example: Delete 5 in the tree below:

7
7
Delete 5
2
1
2
15
4
3
8
6
5
40
9
1
15
4
3
8
6
40
9

CASE 2:THE NODE TO BE DELETED HAS ONE NON-EMPTY
CHILD
(a) The right subtree of the node x to be deleted
is empty.

Example:
20
target
Delete 10
10
temp
5
3
6
35
22
8
target
5
40
25
20
3
35
8
6
22
40
25
(b) The left subtree of the node x to be
deleted is empty.
7
7
2
1
target
4
3
8
6
5
15
40
12
9
2
Delete 8
temp
14
1
15
target
4
3
12
6
5
9
40
14
CASE 3: DELETING A NODE THAT HAS TWO NON-EMPTY CHILDREN
DELETION BY COPYING: METHOD#1
Copy the minimum key in the right subtree of x
to the node x, then delete the one-child or leafnode with this minimum key.
Delete 7
7
8
2
1
2
15
4
3
8
6
5
40
9
1
15
4
3
9
6
5
40
Case 3: DELETING A NODE THAT HAS TWO NON-EMPTY CHILDREN
DELETION BY COPYING: METHOD#2
Copy the maximum key in the left subtree of x to the node x,
then delete the one-child or leaf-node with this maximum key.

Example:
Delete 7
7
6
2
1
2
15
4
3
8
6
5
40
9
1
15
4
3
8
5
40
9
Removal from the binary search tree where the entry to remove (with key
32) is stored at a node (w) with an external child: (a) before the removal; (b)
after the removal.

Removal from the binary search tree of where the entry to
remove (with key 65) is stored at a node (w) whose children are
both internal: (a) before the removal; (b) after the removal.
BST Performance?
BSTs provide good logarithmic time performance in the best and
average cases.
 Average case complexities of using linear data structures
compared to BSTs:

Data Structure
Retrieval
Insertion
Deletion
BST
O(log n)
FAST
O(log n)
FAST
O(log n)
FAST
Sorted Array
O(log n)
FAST*
O(n)
SLOW
O(n)
SLOW
Sorted Linked List
O(n)
SLOW
O(n)
SLOW
O(n)
SLOW
*using binary search