Chapter 12 - Binary Search Trees

Document last modified:

Overview

Binary tree - recursively defined on a finite set of nodes that either

contains no nodes

is composed of three disjoint sets of nodes:

root node

binary tree called the left subtree

binary tree called the right subtree

Examples

(a)

(b)

(c)
(d)         2
            /
          3
       /
     4
    /
   6
    /
   7

(e)                  4
                    /    \
                  2       7
                   \      /
                    3 6     (f)     2
          \
           3
             \
              4
                \
                 7
                /
              6

(g)                  4
                    /    \
                  2       6
                /   \    / \
              1     3 5   7 (h)                  4
                    /    \
                  2       6
                /
              1

Question 12.1

Are each of the trees binary?

Are each in sorted order? What does that mean?

What is the height of (d)? (e)?

For full binary trees, decision trees, and heaps we made and proved general claims that the height h of a binary tree is related to the number of nodes. Why was that useful?

What are some of the relationships between the height of an arbitrary binary tree such as those above and the number of nodes?
A few:

For height h there are at least h+1 nodes (see d).

For height h there are at most 2^h+1-1 nodes (see g).

For n nodes the height is at least ëlg nû (see g).

Binary search trees are an important data structure for dynamic-sets.

• Recall that a dictionary is a dynamic-set with delete, insert or search operations.

• Accomplish many dynamic-set operations in O(h) time, where h = height of tree.

Uses

To implement a concept (component) that permits the following:

search on a key value

dynamic insertions and deletions

updates of satellite data associated with a key value

locating predecessors and successors to a particular key value

maintain data in sorted order

locate minimum and maximum

Question 12.2

Can the minimum and maximum be found in the tree at right in O(h) time?

Can the minimum and maximum be found in the heap at right in O(h) time?

Which of the above operations can a hash table efficiently support, O(n) time?

Which of the above operations can a sorted array efficiently support, O(n) time?

Representation

• Represent a binary tree by a linked data structure in which each node is an object.

• T.root points to the root of tree T

• Each node contains the fields:

key: element (and possibly other satellite data).

left: points to left child.

right: points to right child.

p: points to parent.

T.root.p = NIL

Binary-tree-search property

• Stored keys must satisfy the binary-search-tree property.

If l is any node in the left subtree of x,

       then l .key ≤ x.key

If r is any node in the right subtree of x,

       then x.key < r.key

Question 12.3 - Does the tree at right satisfy the binary-search-tree property?

Cormen Implementation

class Node_Rep;
typedef Node_Rep * Node;

class Node_Rep {
public:
    Item key;    // element
    Node p;       // parent
    Node left;    // left child
    Node right; // right child
};

Node root;

Note: the satellite data associated with the key is generally ignored in our discussion.

Java OO implementation

class Node {
     Node p, left, right;
     int key;

     Node (int key, Node p, Node left, Node right) {
                  this.key=key;    this.p = p;
                  this.left = left;   this.right = right;
     }

     void Inorder() {               // Traverse inorder
          if( left != null) left.Inorder( );
          System.out.println( key );
          if( right != null) right.Inorder( );
     }

     void Insert( int key ) {    // Insert new node
           if( key <= this.key)
                  if( left != null ) left.Insert( key );
                  else left = new Node(key, this, null, null);
           else
                  if( right != null ) right.Insert( key );
                  else right = new Node(key, this, null, null);
      }
}

public class NodeFun {
     public static void main(String a[]) {
           Node root = new Node( 4, null, null, null);
           root.Insert( 3 );
           root.Insert( 1 );
           root.Insert( 2 );
           root.Insert( 6 );
           root.Insert( 5 );

           root.Inorder();
     }
}

Question 12.4

Diagram the tree constructed by:

Node root = new Node( 4, null, null, null);

root.Insert( 3 );
root.Insert( 1 );
root.Insert( 2 );
root.Insert( 6 );
root.Insert( 5 );

Where in the code is the parent node p assigned?

From the trees (a) and (b) below:
What is printed by root.Inorder()?

What is the best case for Insert(6)?

What is the worst case for Insert(6)?

What is the complexity of Inorder()?

Binary-search-tree property

Let x be a Node in a binary search tree.

If l is any node in the left subtree of x,

then l.key ≤ x.key

If r is any node in the right subtree of x,

then x.key < r.key

Question 12.5

Do both of the above trees satisfy the binary-search-tree property?

What is the implication of having non-unique keys?

Inorder Traversal

void Inorder_Tree_Walk ( Node x)
    if x ¹ NIL
        Inorder_Tree_Walk ( x.left )
        print x.key
        Inorder_Tree_Walk ( x.right )

Q(n) Performance:

If Inorder_Tree_Walk is called with the root of an n-node tree, then Inorder_Tree_Walk takes Q(n) time.

The recurrence is:

T(0) = c Empty tree

T(n) = T(k) + T(n - k - 1) + d k left subnodes, n - k - 1 right subnodes
d recursion/print cost

where

d = cost to recurse, not the time spent in the recursion down a branch

c = cost of test for empty subtree

n = # of nodes from the subtree root (11 at the tree root)

k = # nodes in the left subtree (7 at the tree root)

n - k - 1 = # nodes in the right subtree ( 11 - 7 - 1 = 3 at the tree root)

T( k ) = cost to recurse on k nodes

T( n-k-1 ) = cost to recurse on n-k-1 nodes

Example at root

T(n) = T(k) + T(n - k - 1) + d

T(11) = T(7) + T(11-7-1) + d = T(7) + T(3) + d

Theorem T(n) = Q(n)

Given (closed-end equation from the text)

T(n) = (c + d) n + c

(c + d) n = (time to test for NIL and recurse) n times

c = time to test for NIL

           æ T(0) = c
T(n) = í
           è T(k) + T(n - k - 1) + d

Proof: T(n) = (c + d) n + c by substitution using text provided closed-end equation

Base T(0) = (c + d) 0 + c = c

Substitution T(n) = T(k) + T(n - k - 1) + d

= (c+d)k + c + (c+d)(n-k-1)+c + d

= ck+dk+c + cn-ck-c+dn-dk-d+c

= (c+ d)n + c -(c+d) + (c+d)

= (c+ d)n + c

Proof:  T(n) = (c + d) n + c = Q(n) of upper and lower bound

b₁n ≤ (c + d) n + c ≤ b₂n

b₁ ≤ (c + d) + c/n ≤ b₂

(c + d) + c/n maximum at n₀= 1 since limit c/n ® 0 as n ® ¥

(c + d) + c/1 = 2c + d

0 ≤ b₁ ≤ 2c + d      for n ³ n₀        W(n)

0 ≤ 2c + d ≤ b₂ for n ³ n₀        O(n)

Question 12.6

Are c and d > 0?

Can we pick any b₁ as long as we satisfy 0 ≤ b₁ ≤ 2c + d?

Does picking 0 ≤ b₁ ≤ 2c + d satisfy the relation?

Have we proven T(n) = Q(n)?

Give the pre, post and in-order traversal of the tree at right.

What is the maximum memory use for the tree (number of activation records) during in-order traversal?

Is it better, worse or the same for pre and post order?

What is the upper-bound of memory use of in-order traversal?

Search

Node Tree_Search ( Node x, Item& k)

    if x = NIL or k = x.key
        return x
    else
        if k < x.key
            return Tree_Search ( x.left, k)
        else
            return Tree_Search ( x.right, k)

Question 12.7

What are the preconditions? postconditions?

Keep track of the activation records while tracing the nodes searched for 9. For 8.

Does the tree need to be balanced?

Balanced binary trees (AVL) subtrees of every node never differ in height by more than one. The tree above is not balanced because the left subtree of node 15 has height 4 and the right height 2.

What is the number of activation records required for search of the trees below?

What is the tree height?

What is an upper-bound performance in terms of height?

What is a lower-bound?

Can you as easily state a reasonably accurate average performance for an arbitrary search tree? The text discusses in section 12.4

Which of the following have the better search performance and why? What was the approximate order that data was inserted into each?

(a)                  4
                    /    \
                  2       7
                   \      /
                     3 6     (b)     2
          \
           3
             \
              4
                \
                 7
                /
              6

Convert Tail Recursive operation to an Iterative Operation

A tail-recursive operation, i.e., that last statement that gets executed when not at the base case is a recursive call.
To convert to a while loop:
- change the if to a while
- change the test in the while so that it is the not of the test used in the if
- change the recursive call into an assignment statement which modifies the value stored in the variable that is used to control the while loop

Iterative

Node Tree_Search (Node x, Item& k)

    while x ¹ NIL and k ¹ x.key
        if k < x.key
            x ¬ x.left
        else
            x ¬ x.right
    return x

Recursive

Node Tree_Search (Node x, Item& k)

    if x = NIL or k = x.key
        return x
    else
        if k < x.key
            return Tree_Search (x.left, k)
        else
            return Tree_Search (x.right, k)

    while not base case
        iterate closer to base case
    return base or iterative result

if base case return base result
else return recurse closer to base case

O(h) Performance:

If Tree_Search is called with the root of an n-node tree, then Tree_Search takes O(h) time, where h is the height of the tree.

Question 12.8.1

Trace below tree using iterative search, the nodes searched for 9. For 8.

What is the best case for size n?

What is the worst case for size n?

What is to be gained by this conversion from recursive to iterative?

If the tree is full, én/2ù nodes at bottom, can we state a tighter upper-bound performance in terms of n?

Question 12.8.2

Is the following tail-recursive?

void Inorder_Tree_Walk ( Node x)
    if x ¹ NIL
        Inorder_Tree_Walk ( x.left )
        print x.key
        Inorder_Tree_Walk ( x.right )

Successor

If all keys are distinct, the successor of node x is the node with the smallest key greater than x.key

Example: The successor of node with key 4 is the node with key 6.

Tree_Successor (Node 4 ) returns Node 6

O(h) Performance: Tree_Successor takes O(h) time, where h is the height of the tree.

Predecessor

If all keys are distinct, the predecessor of node x is the node with with the greatest key less than x.key.

Example: The predecessor of node with key 6 is the node with key 4.

Question 12.9

What is the successor of 7, 15, 13, 20?

Trace Tree_Minimum starting at 15. Starting at 7.

What is the predecessor of 7, 15, 9, 2?

What does y ¬ x.p do at x=4?

*Trace Tree_Successor starting at 15, 7, and 13.

What is the precondition for Tree_Minimum?

Convert Tree_Minimum to a tail-recursive algorithm.

Give Tree_Maximum.

Give a tail-recursive Tree_Successor.

Node Tree_Successor ( Node x )

    if x.right ¹ NIL
        return Tree_Minimum ( x.right)
    else                        -- Successor is direct ancestor
        y ¬ x.p
        while y ¹ NIL && x = y.right
            x ¬ y
            y ¬ y.p
        return y

Node Tree_Minimum ( Node x )

    while x.left ¹ NIL
        x ¬ x.left
    return x

Insertion and Deletion

Insertion and Deletion must maintain the binary-search-tree property.

Tree is a pointer to some data type that represents an entire tree. At a minimum it stores address to the root node of the tree.
The caller must allocate a Node_Rep's worth of storage prior to calling Tree_Insert, load this new node with the key and then pass this new node's address to Tree_Insert through parameter z.
New nodes get added at the leaf.

Insertion

Tree_Insert ( T, new Node ( left=NIL, right=NIL, parent=NIL, element) )

void Tree_Insert (Tree T, Node z)
-- pre: z ¹ NIL, T ¹ NIL, z.key not in T
-- post: z inserted into T maintaining binary-tree-search property

    variable Node x, y;

    y ¬ NIL
    x ¬ T.root
    while x ¹ NIL                  -- traverse to a leaf node
        y ¬ x                            -- y is parent of x
        if z.key < x.key
            x ¬ x.left
       else
            x ¬ x.right

z.p ¬ y -- parent of z to be y

    if y = NIL                          -- inserting into empty tree
        T.root ¬ z                     -- make z root
    else                                  -- otherwise make z a leaf
        if z.key < y.key
            y.left ¬ z                  -- left of parent
        else
            y.right ¬ z                -- right of parent

Question 12.10

Trace inserting 13, 8, 11, 2, 5 into tree at right.

What happened in the attempt to insert a key that was already in the tree?

Do insertions occur at internal nodes?

What is the worst-case number of key comparisons for the tree at right after inserting 13? Give an example.

What is the best case? In what cases?

Insert 1, 2, 3, 4, 5, 6, 7, 8, 9 into an empty binary search tree. Give two different trees and the search upper-bound of each.

O(h) Performance:

Tree_Insert takes O(h) time, where h is the height of the tree.

Deletion - Must maintain binary-search-tree property.

Example: (a) Delete a node z with 0 children - 13

Node Tree_Delete (Tree T, Node z)

variable Node x, y; -- initially NIL

y ¬ z -- (a) 0 children

x ¬ y.right -- on right NIL

    if y = y.p.left                            -- y is left child of parent
        y.p.left ¬ x                            --   x precedes parent
    else                                           -- y is right child of parent
        y.p.right ¬ x                          --   x succeeds parent

return y

Example: (b) Delete a node z with 1 child - 16

Node Tree_Delete (Tree T, Node z)

variable Node x, y; -- initially NIL

y ¬ z -- (b) 1 child

x ¬ y.right -- on right node 20

if x ¹ NIL -- x is a child
x.p ¬ y.p -- x & y have parent node 15

if y = y.p.left                                 -- y is left child of parent
        y.p.left ¬ x                               --   x precedes parent
else                                                -- y is right child of parent
        y.p.right ¬ x                             --   x succeeds parent

return y

Example: (c) Delete a node z with 2 children - 5

Note the y, Node 6, was successor of Node 5.

The 6 was copied to Node 5, original Node 6 returned.

Node Tree_Delete (Tree T, Node z)
-- pre: z ¹ NIL, T ¹ NIL
-- post: z deleted from T maintaining binary-tree-search property
-- return pointer to node deleted for recycling memory

variable Node x, y; -- initially NIL

if z.left = NIL or z.right = NIL
    y ¬ z                                           -- (a) 0 or (b) 1 child
else
    y ¬ Tree_Successor (z)                -- (c) 2 children

if y.left ¹ NIL                                  -- locate child node of y
    x ¬ y.left                                     --   on left
else
    x ¬ y.right                                   --   on right

if x ¹ NIL -- x is a child (b) or (c)
x.p ¬ y.p -- x & y common parent

if y.p = NIL                                    -- deleting root
    T.root ¬ x                                   -- make x root even if NIL
else                                               -- (b)
    if y = y.p.left                             -- y is left child of parent
        y.p.left ¬ x                             --   x precedes parent
    else                                            -- y is right child of parent
        y.p.right ¬ x                          --   x succeeds parent
if y ¹ z                                           -- (c) y is successor of z
    z.key ¬ y.key                             --   z keeps position in tree
    copy y's satellite data into z         --   (same parent & children)
                                                      --   but copy y key and data
return y

When Tree_Delete is called, the caller has already called Tree_Search with key k to get the pointer to the node that is to be deleted. The pointer returned by Tree_Search is then passed to Tree_Delete.
There are three cases:
1. z has no children; Figure (a) delete 13
2. z has 1 child; Figure (b) delete 16
3. z has 2 children; Figure (c) delete 5
Question 12.11 - From Figure (a)
1. Trace deleting 7.
2. Trace deleting 10.
3. Trace deleting 15.

O(h) Performance:

Tree_Delete takes O(h) time, where h is the height of the tree,

because it calls Tree_Successor for case (c), and Tree_Successor runs in O(h) time.

Question

Give an algorithm to count the number of nodes in a binary tree. What is the order of the algorithm?
Give an algorithm to count the number of leaf nodes in a tree. What is the order of the algorithm?
Give an algorithm to determine the height of a tree. What is the order of the algorithm?

(a)	(b)
(c)	(d) 2 / 3 / 4 / 6 / 7
(e) 4 / \ 2 7 \ / 3 6	(f) 2 \ 3 \ 4 \ 7 / 6
(g) 4 / \ 2 6 / \ / \ 1 3 5 7	(h) 4 / \ 2 6 / 1

T(0) = c	Empty tree
T(n) = T(k) + T(n - k - 1) + d	k left subnodes, n - k - 1 right subnodes d recursion/print cost

Base	T(0)	= (c + d) 0 + c = c
Substitution	T(n)	= T(k) + T(n - k - 1) + d
		= (c+d)k + c + (c+d)(n-k-1)+c + d
		= ck+dk+c + cn-ck-c+dn-dk-d+c
		= (c+ d)n + c -(c+d) + (c+d)
		= (c+ d)n + c