Question

(a) Estimate the asymptotic running time of searching in a skewed BST and a balanced BST. Fill the following table with the big-O running times of each case.

	skewed tree	balanced tree
search

(b) Explain each of the running times in the table applying the rules of counting seen in class. Specify which method(s) of the BST class you will use, if we have covered them already in class, directly refer to the running times of those methods. (Partial credit if you do not explain both running times. No points for ambiguous or incomplete explanations.)

/**
* Exception class for access in empty containers
* such as stacks, queues, and priority queues.
* @author Mark Allen Weiss
*/
public class UnderflowException extends RuntimeException
{
}

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// boolean contains( x ) --> Return true if x is present
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as appropriate

/**
* Implements an unbalanced binary search tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>
{
/**
* Construct the tree.
*/
public BinarySearchTree( )
{
root = null;
}

/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( AnyType x )
{
root = insert( x, root );
}

/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove( AnyType x )
{
root = remove( x, root );
}

/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public AnyType findMin( )
{
if( isEmpty( ) )
throw new UnderflowException( );
return findMin( root ).element;
}

/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public AnyType findMax( )
{
if( isEmpty( ) )
throw new UnderflowException( );
return findMax( root ).element;
}

/**
* Find an item in the tree.
* @param x the item to search for.
* @return true if not found.
*/
public boolean contains( AnyType x )
{
return contains( x, root );
}

/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}

/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}

/**
* Print the tree contents in sorted order.
*/
public void printTree( )
{
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}

/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return new BinaryNode<AnyType>( x, null, null );
  
int compareResult = x.compareTo( t.element );
  
if( compareResult < 0 )
t.left = insert( x, t.left );
else if( compareResult > 0 )
t.right = insert( x, t.right );
else
; // Duplicate; do nothing
return t;
}

/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return t; // Item not found; do nothing
  
int compareResult = x.compareTo( t.element );
  
if( compareResult < 0 )
t.left = remove( x, t.left );
else if( compareResult > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = remove( t.element, t.right );
}
else
t = ( t.left != null ) ? t.left : t.right;
return t;
}

/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the smallest item.
*/
private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
{
if( t == null )
return null;
else if( t.left == null )
return t;
return findMin( t.left );
}

/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the largest item.
*/
private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
{
if( t != null )
while( t.right != null )
t = t.right;

return t;
}

/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the subtree.
* @return node containing the matched item.
*/
private boolean contains( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return false;
  
int compareResult = x.compareTo( t.element );
  
if( compareResult < 0 )
return contains( x, t.left );
else if( compareResult > 0 )
return contains( x, t.right );
else
return true; // Match
}

/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the subtree.
*/
private void printTree( BinaryNode<AnyType> t )
{
if( t != null )
{
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}

/**
* Internal method to compute height of a subtree.
* @param t the node that roots the subtree.
*/
private int height( BinaryNode<AnyType> t )
{
if( t == null )
return -1;
else
return 1 + Math.max( height( t.left ), height( t.right ) );
}
  
// Basic node stored in unbalanced binary search trees
private static class BinaryNode<AnyType>
{
// Constructors
BinaryNode( AnyType theElement )
{
this( theElement, null, null );
}

BinaryNode( AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt )
{
element = theElement;
left = lt;
right = rt;
}

AnyType element; // The data in the node
BinaryNode<AnyType> left; // Left child
BinaryNode<AnyType> right; // Right child
}

/** The tree root. */
private BinaryNode<AnyType> root;

// Test program
public static void main( String [ ] args )
{
BinarySearchTree<Integer> t = new BinarySearchTree<Integer>( );
final int NUMS = 4000;
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( i );

for( int i = 1; i < NUMS; i+= 2 )
t.remove( i );

if( NUMS < 40 )
t.printTree( );
if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
System.out.println( "FindMin or FindMax error!" );

for( int i = 2; i < NUMS; i+=2 )
if( !t.contains( i ) )
System.out.println( "Find error1!" );

for( int i = 1; i < NUMS; i+=2 )
{
if( t.contains( i ) )
System.out.println( "Find error2!" );
}
}
}

Answer 1

Skewed Binary Tree is a tree which has either one child or no child. The structure is similar to the Linked-List data structure.

Balanced Binary Search Tree is a tree whose height is balanced at each node. This is similar to AVL tree. The depth difference in two sides of a node in not more than 1 in Balanced BST.

Since Skewed Binary tree is similar to Linked-list, it follows same time complexity as linked-list. Hence It's Searching time complexities are:
Best case: O(1).
Average case: O(n).
Worst case: O(n)

Now, since Balanced BST is similar to AVL, while searching, at any instance, one of the two subtree of a node is traversed skipping the other subtree of nearly same size. Hence, it's time complexity is:
Best case: O(1).
Average case: O(log₂n).
Worst case: O(log₂n)

NOTE: Copy only the average case time complexity in the solution please. No need to copy other time complexity. It is for your knowledge only.

Henceforth, Searching in Balanced BST is far more better than that in Skewed Binary Tree.

Hope it helps.