CSCI 3333.3
Data Structures
Spring 2013
Homework #7

Due Date: April 17th (Wednesday)

The total score is 120%, with 20% bonus credit.

Exercises:

(1) (10%) Show the final BST after the sequential insertions of the following records to an initially empty tree: 5, 20, 18, 37, 22, 16, 9, 13, 47, 90. 12, 17, 1

(2) (15%) Show the evolution of the BST [[7 10 [12 13 []]] 15 [[[] 27 29] 30 [[] 60 90]]] after the sequential deletions of the nodes 15, 13, 60 and 29. If the node of the key to be deleted have two children, use the method of replacing the key by its immediate successor.

(3) (35%) Provide the body of the following algorithm.

Algorithm RangeSearch(p: BST, low, high: integer);
Input:
    p: root of an integer binary search tree.
    [low, high]: the range of node values to be included the result.
Output:
    result: an integer array containing all integers in the BST
            with values in the range [low, high] in order.
    size: number of integers in the array result.

The algorithm with put the integer in the BST p that are within the range of [low, high] into the array result and set its size.

For example, for the BST p =  [[7 10 [12 13 []] 15 [[[] 27 29] 30 [[] 60 90]], low = 10 and high = 60, calling the algorithm will produce:

result = [10, 12, 13, 15, 27, 28, 30, 60].

You may use a helper algorithm.

Program:

Consider the binary search tree implementation from Java tips: http://www.java-tips.org/java-se-tips/java.lang/binary-search-tree-implementation-in-java.html. This appears to be written by the author of our textbook, Dr. Weiss. Study the code.

(1) (10%) How does the author implement the deletion of a node with two children.

(2) (20%) Add two methods to the class BinarySearchTree:

size(): return the size of the BST.
printBST(): print the elements in the BST in order and with proper identation.

You may alter the class BinaryNode to assist your effort. Furthermore, you may consult with homework #6 as a BST is a binary tree.

(3) (30%) Add the method to the class BinarySearchTree:

void printRange(Comparable low, Comparable high)

It prints all nodes with values in the range [low, high] in order one element per line.

To illustrate the action of the methods, the main program is modified (changes highlighted in bold):

    // Test program
    public static void main( String [ ] args ) {
        BinarySearchTree t = new BinarySearchTree( );
        final int NUMS =   50;
        final int GAP  =   37;
       
        System.out.println( "Checking... (no more output means success)" );
       
        for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            t.insert( new Integer( i ) );
       
        System.out.println("After insertions. Size = " + t.size());
        t.printBST();
       
        System.out.println("Elements between 9 and 21");
        t.printRange(new Integer(9), new Integer(21));

      
        for( int i = 1; i < NUMS; i+= 2 )
            t.remove( new Integer( i ) );
           
        System.out.println("After deletions. Size = " + t.size());
        t.printBST();
       
        System.out.println("Elements between 9 and 21");
        t.printRange(new Integer(9), new Integer(21));

      
        if( ((Integer)(t.findMin( ))).intValue( ) != 2 ||
                ((Integer)(t.findMax( ))).intValue( ) != NUMS - 2 )
            System.out.println( "FindMin or FindMax error!" );
       
        for( int i = 2; i < NUMS; i+=2 )
            if( ((Integer)(t.find( new Integer( i ) ))).intValue( ) != i )
                System.out.println( "Find error1!" );
       
        for( int i = 1; i < NUMS; i+=2 ) {
            if( t.find( new Integer( i ) ) != null )
                System.out.println( "Find error2!" );
        }
    }

 

Running the program produces the following output:

Checking... (no more output means succes
After insertions. Size = 49
                            1
                                2
                        3
                            4
                    5
                        6
                7
                    8
            9
                10
        11
                                12
                                    13
                            14
                                15
                        16
                            17
                    18
                        19
                20
                    21
            22
                23
    24
                            25
                                26
                        27
                            28
                    29
                        30
                31
                    32
            33
                34
        35
            36
37
                        38
                            39
                    40
                        41
                42
                    43
            44
                45
        46
            47
    48
        49
Elements between 9 and 21
9
10
11
12
13
14
15
16
17
18
19
20
21
After deletions. Size = 24
                            2
                        4
                    6
                8
            10
        12
                            14
                        16
                    18
                20
            22
    24
                            26
                        28
                    30
                32
            34
        36
38
                    40
                42
            44
        46
    48
Elements between 9 and 21
10
12
14
16
18
20

 

For this programming assignment, turn in:

As usual, email everything to the TA.