ELCE 305

Data Structures and Algorithms

LECTURE 7
BINARY SEARCH TREES
• Dynamic-set Operations • Chapter 12
Recap
• Dynamic data structures that use pointers:
• Stack
• PUSH(S, x): 𝑂𝑂(1)
• POP(S): 𝑂𝑂(1)
• STACK-EMPTY(S): 𝑂𝑂(1)
• Queue
• ENQUEUE(Q, x): 𝑂𝑂(1)
• DEQUEUE(Q): 𝑂𝑂(1)
• Linked List
• LIST-SEARCH(L, k): 𝑂𝑂(𝑛𝑛)
• LIST-INSERT(L, x): 𝑂𝑂(1)
• LIST-DELETE(L, x): 𝑂𝑂(𝑛𝑛)
• Rooted Tree
2
Introduction (1)
• The search tree data structure supports many dynamic-set operations, including
SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, and DELETE.
• Thus, we can use a search tree both as a dictionary and as a priority queue.
• What is a binary search tree (BST)?
• A BST is organized in a binary tree, where each node carries:
• A key,
• Attributes left, right, and p that point to the nodes corresponding to its left child, its right child,
and its parent, respectively.
• If a child or the parent is missing, the appropriate attribute contains the value NIL.
• The root node is the only node in the tree whose parent is NIL.
• Basic operations on a binary search tree take time proportional to the height of the
tree.
3
Introduction (2)

(a)

(b)
• For any node 𝑥𝑥, the keys in the left subtree of 𝑥𝑥 are at most 𝑥𝑥. 𝑘𝑘𝑘𝑘𝑘𝑘, and the keys in the right subtree of 𝑥𝑥 are at
least 𝑥𝑥. 𝑘𝑘𝑘𝑘𝑘𝑘.
• Different binary search trees can represent the same set of values. The worst-case running time for most
search-tree operations is proportional to the height of the tree.
• (a) A binary search tree on 6 nodes with height 2. (b) A less efficient binary search tree with height 4 that
contains the same keys.
4
Introduction (3)
• The keys in a binary search tree are always stored in such a way as to satisfy
the binary-search-tree property:

• The binary-search-tree property allows us to print out all the keys in a

binary search tree in sorted order by a simple recursive algorithm, called an
inorder tree walk.
• This algorithm is so named because it prints the key of the root of a subtree
between printing the values in its left subtree and printing those in its right
subtree.
5
Introduction (4)
• Exercise: What is preorder tree walk and postorder tree walk?

• The inorder tree walk prints the keys in each of the two BSTs on Slide 4 in
the order 2, 5, 5, 6, 7, 8.
• It takes Θ(𝑛𝑛) time to walk an 𝑛𝑛-node binary search tree, since after the
initial call, the procedure calls itself recursively exactly twice for each node
in the tree—once for its left child and once for its right child.

6
Querying a BST (1)
• We often need to search for a key stored in a BST.
• Besides the SEARCH operation, BSTs can support queries such as
MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR.
• We shall now examine these operations and show how to support each one
in time 𝑂𝑂(ℎ) on any BST of height ℎ.

• Searching:
• Given a pointer to the root of the tree and a key 𝑘𝑘, the TREE-SEARCH
procedure returns a pointer to a node with key 𝑘𝑘 if one exists;
otherwise, it returns NIL.

7
Querying a BST (2)

• To search for the key 13 in the tree, we follow the path 15 ⟶ 6 ⟶ 7 ⟶ 13 from the
root.

8
Querying a BST (3)
• Can we make the TREE-SEARCH procedure more effective?
• By rewriting the procedure in an iterative fashion by “unrolling” the
recursion into a while loop.

• On most computers, the iterative version is more efficient.

9
Querying a BST (4)
• Minimum and Maximum:
• We can always find an element in a BST whose key is a minimum by
following left child pointers from the root until we encounter a NIL.
• Both of these procedures run in 𝑂𝑂(ℎ) time.

• The minimum key in the tree is 2, which is found by following left pointers from the root.
• The maximum key 20 is found by following right pointers from the root.
10
Querying a BST (5)
• Successor and Predecessor:
• Given a node in a BST, sometimes we
need to find its successor in the sorted
order determined by an inorder tree
walk.
• If all keys are distinct, the successor of
a node 𝑥𝑥 is the node with the smallest
key greater than 𝑥𝑥. 𝑘𝑘𝑘𝑘𝑘𝑘.
• The structure of a BST allows us to
determine the successor of a node
without ever comparing keys. The running time of TREE-SUCCESSOR
on a tree of height ℎ is 𝑂𝑂 ℎ .
11
Querying a BST (6)

• The successor of the node with key 15 is the node with key 17, since it is the minimum
key in the right subtree of 15.
• The node with key 13 has no right subtree, and thus its successor is its lowest
ancestor whose left child is also an ancestor. In this case, the node with key 15 is its
successor.

• Exercise: Write the pseudocode for the TREE-PREDECESSOR procedure. 12

Insertion & Deletion (1)
• The operations of insertion and deletion cause the BST to change.
• But the changes are made in such a way that the BST property continues to
hold.
• Inserting a new element is relatively straightforward, but handling deletion
is somewhat more intricate.

• Insertion:
• To insert a new value into a BST 𝑇𝑇, we use the procedure TREE-INSERT.
• The procedure takes a node 𝑧𝑧 for which 𝑧𝑧. 𝑘𝑘𝑘𝑘𝑘𝑘 = 𝑣𝑣, 𝑧𝑧. 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 = NIL, and
𝑧𝑧. 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 = NIL.
• It modifies 𝑇𝑇 and some of the attributes of 𝑧𝑧 in such a way that it inserts 𝑧𝑧
into an appropriate position in the tree. 13
Insertion & Deletion (2)

• Inserting an item with key 13 into a

binary search tree.
• Lightly shaded nodes indicate the simple
path from the root down to the position
where the item is inserted.
• The dashed line indicates the link in the
tree that is added to insert the item.
14
Insertion & Deletion (3)
• Deletion:
• The overall strategy for deleting a node 𝑧𝑧 from a BST 𝑇𝑇 has three basic
cases but, as we shall see, one of the cases is a bit tricky.
• If 𝑧𝑧 has no children, then we simply remove it by modifying its parent to
replace 𝑧𝑧 with NIL as its child.
• If 𝑧𝑧 has just one child, then we elevate that child to take 𝑧𝑧’s position in the
tree by modifying 𝑧𝑧’s parent to replace 𝑧𝑧 by 𝑧𝑧’s child.
• If 𝑧𝑧 has two children, then we find 𝑧𝑧’s successor 𝑦𝑦—which must be in 𝑧𝑧’s
right subtree—and have 𝑦𝑦 take 𝑧𝑧’s position in the tree. The rest of 𝑧𝑧’s
original right subtree becomes 𝑦𝑦’s new right subtree, and 𝑧𝑧’s left subtree
becomes 𝑦𝑦’s new left subtree. This case is the tricky one because, as we
shall see, it matters whether 𝑦𝑦 is 𝑧𝑧’s right child.
15
Insertion & Deletion (4)
• The procedure for deleting a given node 𝑧𝑧 from a BST 𝑇𝑇 takes as arguments
pointers to 𝑇𝑇 and 𝑧𝑧.
• If 𝑧𝑧 has no left child, then we replace 𝑧𝑧 by its
right child, which may or may not be NIL.
• When 𝑧𝑧’s right child is NIL, this case deals with
the situation in which 𝑧𝑧 has no children.
• When 𝑧𝑧’s right child is non-NIL, this case
handles the situation in which 𝑧𝑧 has just one
child, which is its right child.

• If 𝑧𝑧 has just one child, which is its left child,

then we replace 𝑧𝑧 by its left child.
16
Insertion & Deletion (5)
• Otherwise, 𝑧𝑧 has both a left and a right child. We find 𝑧𝑧’s successor 𝑦𝑦, which
lies in 𝑧𝑧’s right subtree and has no left child.
• We want to splice 𝑦𝑦 out of its current location & have it replace 𝑧𝑧 in the tree.
• If 𝑦𝑦 is 𝑧𝑧’s right child, then we replace 𝑧𝑧
by 𝑦𝑦, leaving 𝑦𝑦’s right child alone.

• Otherwise, 𝑦𝑦 lies within 𝑧𝑧’s right

subtree but is not 𝑧𝑧’s right child.
• In this case, we first replace 𝑦𝑦 by
its own right child, and then we
replace 𝑧𝑧 by 𝑦𝑦.
17
Insertion & Deletion (6)
• In order to move subtrees around within
the BST, we define a subroutine
TRANSPLANT, which replaces one subtree
as a child of its parent with another
subtree.

• When TRANSPLANT replaces the subtree

rooted at node 𝑢𝑢 with the subtree rooted
at node 𝑣𝑣, node 𝑢𝑢’s parent becomes
node 𝑣𝑣’s parent, and 𝑢𝑢’s parent ends up
having 𝑣𝑣 as its child.

18
Insertion & Deletion (7)
• With the TRANSPLANT procedure in hand, here is the procedure that deletes
node 𝑧𝑧 from binary search tree 𝑇𝑇:

• Each line of TREE-DELETE, including the calls to

TRANSPLANT, takes constant time, except for the
call to TREE-MINIMUM in line 5.

• Thus, TREE-DELETE runs in 𝑂𝑂(ℎ) time on a tree of

height ℎ.

19