32BinarySearchTrees.txt

Algorithms

ROBERT SEDGEWICK  |  KEVIN WAYNE

3.2  BINARY SEARCH TREES
 BSTs 
 ordered operations
 deletion

http://algs4.cs.princeton.edu

ROBERT SEDGEWICK  |  KEVIN WAYNEFOURTH EDITIONAlgorithms3.2  BINARY SEARCH TREES
 BSTs
 ordered operations
 deletion

http://algs4.cs.princeton.edu

ROBERT SEDGEWICK  |  KEVIN WAYNEAlgorithmsBinary search trees

Definition.  A BST is a binary tree in symmetric order.

A binary tree is either:

(cid:638)Empty.(cid:638)Two disjoint binary trees (left and right).

Symmetric order.  Each node has a key,
and every nodes key is:

(cid:638)Larger than all keys in its left subtree.
(cid:638)Smaller than all keys in its right subtree.

root

a left link

a subtree

right child

of root

null links

Anatomy of a binary tree

parent of A and R

left link

of E

E

key

S

X

A

C

R

9

H

value

associated

with R

keys smaller than E

keys larger than E

Anatomy of a binary search tree

3

Binary search tree demo

Search.  If less, go left; if greater, go right; if equal, search hit.

successful search for H

S

E

X

A

R

C

H

M

4

Binary search tree demo

Insert.  If less, go left; if greater, go right; if null, insert.

insert G

S

E

X

A

R

C

H

G

M

5

BST representation in Java

Java definition.  A BST is a reference to a root Node.

A Node is composed of four fields:

(cid:638)A Key and a Value.
(cid:638)A reference to the left and right subtree.

smaller keys

larger keys

private class Node
{
   private Key key;
   private Value val;
   private Node left, right;
   public Node(Key key, Value val)
   {
      this.key = key;
      this.val = val;
   }
}

Key and Value are generic types; Key is Comparable

BST

Node

key

val

left

right

BST with smaller keys

BST with larger keys

Binary search tree

6

BST implementation (skeleton)

root of BST

7

public class BST<Key extends Comparable<Key>, Value>{    private Node root;   private class Node   {  /* see previous slide */  }    public void put(Key key, Value val)    {  /* see next slides */  }   public Value get(Key key)   {  /* see next slides */  }   public void delete(Key key)   {  /* see next slides */  }   public Iterable<Key> iterator()   {  /* see next slides */  }}BST search:  Java implementation

Get.  Return value corresponding to given key, or null if no such key.

 public Value get(Key key)
 {
    Node x = root;
    while (x != null)
    {
       int cmp = key.compareTo(x.key);
       if      (cmp  < 0) x = x.left;
       else if (cmp  > 0) x = x.right;
       else if (cmp == 0) return x.val;
    }
    return null;
 }

Cost.  Number of compares is equal to 1 + depth of node.

8

BST insert

Put.  Associate value with key.

inserting L

Search for key, then two cases:

(cid:638)Key in tree    reset value.
(cid:638)Key not in tree   add new node.

S

X

R

E

A

C

H

M

P

search for L ends
at this null link 

S

X

S

X

R

R

E

A

C

H

create new node 

L

M

P

E

A

C

H

reset links

on the way up 

M

L

P

Insertion into a BST

9

BST insert:  Java implementation

Put.  Associate value with key. 

 public void put(Key key, Value val)
 {  root = put(root, key, val);  }

 private Node put(Node x, Key key, Value val)
 {
    if (x == null) return new Node(key, val);
    int cmp = key.compareTo(x.key);
    if      (cmp  < 0)
       x.left  = put(x.left,  key, val);
    else if (cmp  > 0)
       x.right = put(x.right, key, val);
    else if (cmp == 0)
       x.val = val;
    return x;
 }

Cost.  Number of compares is equal to 1 + depth of node.

10

concise, but tricky, recursive code;read carefully!Tree shape
(cid:638)Many BSTs correspond to same set of keys.
(cid:638)Number of compares for search/insert is equal to 1 + depth of node.

typical case

best case

X

R

A

E

H

S

X

best case

H

C

S

A

E

R

X

typical case

E

A

R

C

H

S

X

C

S

A

E

R

X

typical case

A

A

S

X

E

R

C

H

worst case

C

E

H

R

S

H

C

S

E

A

A

R

C

H

C

E

worst case

H

R

S

X

BST possibilities

Bottom line.  Tree shape depends on order of insertion.

worst case

A

X

C

E

H

R

BST possibilities

11

BST insertion:  random order visualization

Ex.  Insert keys in random order.

12

Sorting with a binary heap

Q.  What is this sorting algorithm?

0. Shuffle the array of keys.

1. Insert all keys into a BST.

2. Do an inorder traversal of BST.

A.  It's not a sorting algorithm (if there are duplicate keys)!

Q.  OK, so what if there are no duplicate keys?
Q.  What are its properties?

13

Correspondence between BSTs and quicksort partitioning

P

H

T

D

O

S

U

A

E

I

Y

C

M

L

Remark.  Correspondence is 11 if array has no duplicate keys.

14

BSTs:  mathematical analysis

Proposition.  If N distinct keys are inserted into a BST in random order,
the expected number of compares for a search/insert is ~ 2 ln N.
Pf.  11 correspondence with quicksort partitioning.

Proposition.  [Reed, 2003]  If N distinct keys are inserted in random order,
expected height of tree is ~ 4.311 ln N.

How  Tall  is a  Tree? 

How  Tall  is a  Tree? 

Bruce Reed 

CNRS, Paris, France 

reed@moka.ccr.jussieu.fr 

Bruce Reed 

CNRS, Paris, France 

reed@moka.ccr.jussieu.fr 

ABSTRACT 
Let  H~  be the  height  of a  random binary search  tree  on  n 
nodes.  We show that  there  exists constants a  =  4.31107... 
and/3  =  1.95...  such  that  E(H~)  =  c~logn -/31oglogn + 
O(1),  We also show that  Var(H~)  =  O(1). 
Categories and Subject Descriptors 
But...   Worst-case height is N.
E.2  [Data  Structures]:  Trees 
1.  THE RESULTS 
[ exponentially small chance when keys are inserted in random order ]
A  binary search tree  is a  binary tree  to each node of which 
we have associated  a  key;  these  keys  axe  drawn from  some 
totally ordered  set  and the  key at  v  cannot be  larger  than 
the key at  its right child nor smaller than the key at  its left 
child.  Given a  binary search  tree  T  and  a  new  key  k,  we 

ABSTRACT 
Let  H~  be the  height  of a  random binary search  tree  on  n 
nodes.  We show that  there  exists constants a  =  4.31107... 
and/3  =  1.95...  such  that  E(H~)  =  c~logn -/31oglogn + 
O(1),  We also show that  Var(H~)  =  O(1). 
Categories and Subject Descriptors 
E.2  [Data  Structures]:  Trees 
1.  THE RESULTS 
A  binary search tree  is a  binary tree  to each node of which 
we have associated  a  key;  these  keys  axe  drawn from  some 
totally ordered  set  and the  key at  v  cannot be  larger  than 
the key at  its right child nor smaller than the key at  its left 

THEOREM  1.  E(H~)  =  ~logn  -/31oglogn +  O(1)  and 

Var(Hn) =  O(1)  . 
Remark  By the  definition of a, 
3~ 
7"g~"  The first defi- 
nition given is more suggestive of why this  value is correct, 
as we will see. 
For  more  information on  random  binary search  trees,  one 
may consult [6],[7], [1], [2], [9], [4], and  [8]. 
Remark  After I announced these results, Drmota(unpublished) 
developed an alternative proof of the  fact  that  Var(Hn)  = 
O(1)  using  completely  different  techniques.  As  our  two 
proofs  illuminate different aspects  of the  problem, we have 
decided to  submit the journal versions to  the  same journal 

Var(Hn) =  O(1)  . 
Remark  By the  definition of a, 
nition given is more suggestive of why this  value is correct, 
/3 = 
as we will see. 
For  more  information on  random  binary search  trees,  one 
may consult [6],[7], [1], [2], [9], [4], and  [8]. 
Remark  After I announced these results, Drmota(unpublished) 
developed an alternative proof of the  fact  that  Var(Hn)  = 
O(1)  using  completely  different  techniques.  As  our  two 
proofs  illuminate different aspects  of the  problem, we have 
decided to  submit the journal versions to  the  same journal 
and asked that  they be published side by side. 

purpose  of this  note  to  prove  that  for  /3  --  12 +  ~ ,
3 
have: 

purpose  of this  note  to  prove  that  for  /3  --  12 +  ~ ,
have: 

THEOREM  1.  E(H~)  =  ~logn  -/31oglogn +  O(1)  and 

15

ST implementations:  summary

implementation
implementation

sequential search
(unordered list)

binary search
(ordered array)

BST

guarantee
guarantee

average case
average case

search

insert

search hit

insert

12 N

lg N

N

12 N

N

lg N

N

N

N

N

operations
operations

on keys
on keys

equals()

compareTo()

1.39 lg N

1.39 lg N

compareTo()

Why not shuffle to ensure a (probabilistic) guarantee of 4.311 ln N?

16

3.2  BINARY SEARCH TREES
 BSTs
 ordered operations
 deletion

http://algs4.cs.princeton.edu

ROBERT SEDGEWICK  |  KEVIN WAYNEAlgorithmsMinimum and maximum

Minimum.  Smallest key in table.
Maximum.  Largest key in table.

min()

min

E

S

max()max

X

A

C

H

R

M

Examples of BST order queries

Q.  How to find the min / max?  

18

Floor and ceiling

Floor.  Largest key  a given key.
Ceiling.  Smallest key  a given key.

floor(G)

min()

A

S

max()

X

ceiling(Q)

E

C

H

R

M

floor(D)

Examples of BST order queries

Q.  How to find the floor / ceiling?

19

Computing the floor

Case 1.  [k equals the key in the node]
The floor of k is k.

Case 2.  [k is less than the key in the node]
The floor of k is in the left subtree.

Case 3.  [k is greater than the key in the node]
The floor of k is in the right subtree
(if there is any key  k in right subtree);
otherwise it is the key in the node.

finding floor(G)
finding floor(G)
finding floor(G)

A
A
A

A
A
A

E
E
E

C
C
C

H
H
H

E
E
E

C
C
C

H
H
H

G is greater than E so 
G is greater than E so 
G is greater than E so 
floor(G) could be
floor(G) could be
floor(G) could be

on the right 
on the right 
on the right 
E
E
E

A
A
A

C
C
C

H
H
H

floor(G)in left
floor(G)in left
floor(G)in left
subtree is null
subtree is null
subtree is null

E
E
E

A
A
A

result
result
result

H
H
H

C
C
C

S
S
S

X
X
X

R
R
R

M
M
M

G is less than S so 
G is less than S so 
G is less than S so 
floor(G) must be
floor(G) must be
floor(G) must be

on the left
on the left
on the left

S
S
S

X
X
X

S
S
S

X
X
X

S
S
S

X
X
X

R
R
R

R
R
R

R
R
R

M
M
M

M
M
M

M
M
M

Computing the floor function
Computing the floor function
Computing the floor function

20

Computing the floor

public Key floor(Key key)
{  
   Node x = floor(root, key);
   if (x == null) return null;
   return x.key;
}
private Node floor(Node x, Key key)
{  
   if (x == null) return null;
   int cmp = key.compareTo(x.key);

   if (cmp == 0) return x;

   if (cmp < 0)  return floor(x.left, key);

   Node t = floor(x.right, key);
   if (t != null) return t;
   else           return x;

} 

finding floor(G)

A

A

E

C

H

E

C

H

G is greater than E so 
floor(G) could be

on the right 
E

A

C

H

floor(G)in left
subtree is null

E

A

result

H

C

S

X

R

M

G is less than S so 
floor(G) must be

on the left

S

X

S

X

S

X

R

R

R

M

M

M

Computing the floor function

21

Rank and select

Q.  How to implement rank() and select() efficiently? 

A.  In each node, we store the number of nodes in the subtree rooted at 
that node; to implement size(), return the count at the root.

8
S

1
X

3
R

node count

6
E

2
A

1
C

2
H

1
M

22

BST implementation:  subtree counts

private class Node
{
   private Key key;
   private Value val;
   private Node left;
   private Node right;
   private int count;
}

  public int size()
  {  return size(root);  }

  private int size(Node x)
  {
     if (x == null) return 0;
     return x.count;
  }

ok to call

when x is null

number of  nodes in subtree

initialize subtree

count to 1

 private Node put(Node x, Key key, Value val)
 {
    if (x == null) return new Node(key, val, 1);
    int cmp = key.compareTo(x.key);
    if      (cmp  < 0) x.left  = put(x.left,  key, val);
    else if (cmp  > 0) x.right = put(x.right, key, val);
    else if (cmp == 0) x.val = val;
    x.count = 1 + size(x.left) + size(x.right);
    return x;
 }

23

Rank

Rank.  How many keys < k ?

Easy recursive algorithm (3 cases!)

8
S

1
X

3
R

node count

6
E

2
A

1
C

2
H

1
M

public int rank(Key key) 
{  return rank(key, root);  } 

private int rank(Key key, Node x) 
{ 
   if (x == null) return 0; 
   int cmp = key.compareTo(x.key);
   if      (cmp  < 0) return rank(key, x.left); 
   else if (cmp  > 0) return 1 + size(x.left) + rank(key, x.right); 
   else if (cmp == 0) return size(x.left); 
} 

24

Inorder traversal
(cid:638)Traverse left subtree.
(cid:638)Enqueue key.
(cid:638)Traverse right subtree.

public Iterable<Key> keys() 
{ 
    Queue<Key> q = new Queue<Key>(); 
    inorder(root, q); 
    return q;
}

private void inorder(Node x, Queue<Key> q) 
{ 
   if (x == null) return; 
   inorder(x.left, q); 
   q.enqueue(x.key); 
   inorder(x.right, q); 
} 

BST

key

val

left

right

BST with smaller keys

BST with larger keys

smaller keys, in order

key

larger keys, in order

all keys, in order

Property.  Inorder traversal of a BST yields keys in ascending order.

25

BST:  ordered symbol table operations summary

sequential

search

N

N

N

N

N

N

search

insert

min / max

floor / ceiling

rank

select

ordered iteration

N log N

binary
search

lg N

N

1

lg N

lg N

1

N

BST

h

h

h

h

h

h

N

order of growth of running time of ordered symbol table operations

h = height of BST

(proportional to log N

if keys inserted in random order)

26

3.2  BINARY SEARCH TREES
 BSTs
 ordered operations
 deletion

http://algs4.cs.princeton.edu

ROBERT SEDGEWICK  |  KEVIN WAYNEAlgorithmsST implementations:  summary

implementation
implementation

guarantee
guarantee
guarantee

average case
average case
average case

search

insert

delete

search hit

insert

delete

ordered
ordered

ops?
ops?

operations
operations

on keys
on keys

sequential search

(linked list)

binary search
(ordered array)

BST

N

lg N

N

N

N

N

N

N

N

12 N

lg N

N

12 N

12 N

12 N

1.39 lg N

1.39 lg N

? ? ?

equals()





compareTo()

compareTo()

Next.  Deletion in BSTs.

28

BST deletion:  lazy approach

To remove a node with a given key:

(cid:638)Set its value to null.
(cid:638)Leave key in tree to guide search (but don't consider it equal in search).

A

C

E

H

S

R

I

N

E

A

S

delete I

C



tombstone

H

R

N

Cost.  ~ 2 ln N' per insert, search, and delete (if keys in random order),
where N' is the number of key-value pairs ever inserted in the BST.

Unsatisfactory solution.  Tombstone (memory) overload.

29

Deleting the minimum

To delete the minimum key:

(cid:638)Go left until finding a node with a null left link.
(cid:638)Replace that node by its right link.
(cid:638)Update subtree counts.

 public void deleteMin()
 {  root = deleteMin(root);  }

 private Node deleteMin(Node x)
 {
    if (x.left == null) return x.right;
    x.left = deleteMin(x.left);
    x.count = 1 + size(x.left) + size(x.right);
    return x;
 }

go left until
reaching null

left link
A

E

C

H

return that

nodes right link

E

A

C

H

available for

garbage collection

M

M

update links and node counts

after recursive calls

5
E

C

H

M

S

X

S

X

7
S

X

R

R

R

Deleting the minimum in a BST

30

Hibbard deletion

To delete a node with key k:  search for node t containing key k.

Case 0.  [0 children]  Delete t by setting parent link to null.

deleting C

S

X

E

A

C

H

node to delete

R

M

E

A

replace with

null link

R

H

M

available for

garbage
collection

C

update counts after

recursive calls

S

X

5
E

1
A

R

H

M

7
S

X

31

Hibbard deletion

To delete a node with key k:  search for node t containing key k.

Case 1.  [1 child]  Delete t by replacing parent link.

deleting R

E

A

C

H

S

X

R

node to delete

M

update counts after

recursive calls

S

X

5
E

7
S

X

A

C

H

M

E

A

C

H

M

replace with
child link

available for

garbage
collection

R

32

Hibbard deletion

deleting E

node to delete

To delete a node with key k:  search for node t containing key k.

E

X

A

R

C

H

search for key E

Case 2.  [2 children]

(cid:638)Find successor x of t.
(cid:638)Delete the minimum in t's right subtree.
(cid:638)Put x in t's spot.

A

t

deleting E

E
x

C

H

x has no left child

but don't garbage collect x
X

still a BST

successor

 min(t.right)

S

S

R

M

M

go right, then
go left until
reaching null

left link

search for key E

t.left

S

X

deleteMin(t.right)

x

E

H

node to delete

A

A

E

C

H

t

E
x

C

H

M

M

S

X

R

S

X

R

successor

 min(t.right)

go right, then
go left until
reaching null

left link

x

E

H

t.left

S

X

deleteMin(t.right)

A

A

C

M

5
H

C

M

R

R

7
S

X

update links and
node counts after

recursive calls

Deletion in a BST

33

Hibbard deletion:  Java implementation

 public void delete(Key key)
 {  root = delete(root, key);  }

 private Node delete(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if      (cmp < 0) x.left  = delete(x.left,  key);
    else if (cmp > 0) x.right = delete(x.right, key);
    else { 
       if (x.right == null) return x.left;
       if (x.left  == null) return x.right;

       Node t = x;
       x = min(t.right);
       x.right = deleteMin(t.right);
       x.left = t.left;
    } 
    x.count = size(x.left) + size(x.right) + 1;
    return x;
 } 

search for key

no right child

no left child

replace with 
successor

update subtree 

counts

34

Hibbard deletion:  analysis

Unsatisfactory solution.  Not symmetric.

Surprising consequence.  Trees not random (!)     N per op.
Longstanding open problem.  Simple and efficient delete for BSTs.

35

ST implementations:  summary

implementation
implementation

guarantee
guarantee
guarantee

average case
average case
average case

search

insert

delete

search hit

insert

delete

ordered
ordered

ops?
ops?

operations
operations

on keys
on keys

sequential search

(linked list)

binary search
(ordered array)

BST

N

lg N

N

N

N

N

N

N

N

12 N

lg N

N

12 N

1.39 lg N

1.39 lg N

12 N

12 N

 N

equals()





compareTo()

compareTo()

other operations also become N

if deletions allowed

Next lecture.  Guarantee logarithmic performance for all operations.

36