SUNY Geneseo Department of Computer Science

Tree Search and Insertion

Return to List of Lectures

Questions?

Tree lab?

• Yes
• Next week: linked implementation for experiment on height
• Will talk about trees in arrays -> heaps/priority queues -> heap sort

Building and Searching Trees

Sections 13.3.3 and 13.3.4

• Constructing ordered trees
• Searching and construction are similar
  • Search for value by comparing to root, then recursively search left or right subtree according to whether value is greater or less than root until you find your value.
  • Insert a value by doing search until you find an empty tree, compare value to empty tree's parent and add as left or right child of parent according to whether value less than or greater than parent value.
• Proofs that algorithms are correct by induction on height of tree
• Can modify algorithms to deal with duplicates
• Examples

Our own examples

• Build an ordered binary tree from 4, 2, 3, 1, 5, 3

• Search the above tree for 3, 0

Code

    class OrderedBinaryTree {                     // tree of ints
        private int root;                         // == -1 for empty tree
        private OrderedBinaryTree left, right;

    boolean isEmpty() {
        ...
    }

    int countOccurrences( int x ) {
        if ( ! this.isEmpty() ) {
            if ( x < root ) {
                return left.countOccurrences( x );
            }
            else if ( x == root ) {
                return right.countOccurrences( x ) + 1; }
            else {                                // x > root
                return right.countOccurrences( x );
            }
        }
        else {
            return 0;
        }
    }
	
    OrderedBinaryTree insert( int x ) {
        if ( ! this.isEmpty() ) {
            if ( x < root ) {
                left = left.insert( x );
                return this;
            }
            else {                                // x >= root
                right = right.insert( x )
                return this;
            }
        }
        else {
            return new OrderedBinaryTree( x );
        }
    }

Next

Efficiency of binary tree algorithms

Read Section 13.3.5