To receive credit for this homework, your assignment must be available in class on Monday, 29 April.  If for some reason you cannot come to class, you must turn in your work before class time.

This is something suggested by a piece of e-mail from Steve Simmons, but somewhat modified.

Get several blank pieces of paper — you're going to generate four binary search trees, each with 26 nodes.  If you wish, you can use the worksheet available through this link.  It is a word-processor file that prints a grid — 26 by 13.  You can then just put a dot into a cell to represent a node with that card's value, then draw the left and right lines to values that turn up as the left and right subtrees in the BST.  If you don't have something that will deal with .RTF format, here are links to (not terribly pretty) graphical images:  BlackBST.jpeg  RedBST.jpeg.

Obtain a standard deck of playing cards (52 cards).  For each pair of BSTs, shuffle the deck.  Then go through the deck one card at a time, inserting nodes into two initially empty BSTs (one for red, the other for black) according to the following rules:

1. Red card:  determine the value by the following rules, and then insert that value into the RED BST:
• If the card is a heart, add its value to 100.  Thus the ace of hearts is 101, up to the king as 113.
• If the card is a diamond, add its value to 200.  Ace of diamonds is 201, up to the king as 213.
2. Black card:  determine the value by the following rules, and then insert that value into the BLACK BST:
• If the card is a club, add its value to 100.  Thus the ace of clubs is 101, up to the king as 113.
• If the card is a spade, add its value to 200.  Ace of spaces is 201, up to the king as 213.

If you use the worksheets, there's a way to check for a valid  BST:  there should never be a line crossing below a node in the tree — that would mean that upstream somewhere the traversal took a wrong turn on an insertion.

Then on your worksheet, write the height of the generated BST, the sum of the depths of all of the nodes, and the average depth (that sum divided by 26).

These are the quantities that we will need in class.

Bring the resulting BSTs to class.  In class we will use them to experimentally determine the average height and the average of the average depth.

If you don't have access to a deck of playing cards, you can use the following program (link provided) to deal out the 52-card deck into four hands of 13 cards:
          DealCards.cpp    Source code, should you want to compile your own
          DealCards.exe     Directly runnable executable

For those who prefer not to deal with playing cards in any form, here is a program that will generate random vectors of the numbers 101,102,...,112,113,201,202,...,212,213:
          RndChart.bas       Source code (in QBasic/QuickBasic)
          RndChart.exe       Directly runnable executable (compiled with Microsoft QB45)