Week 7 Objectives

KNOW:

• the definition for a binary tree
• the three common traversal methods for binary trees
• the definition for a binary search tree
• why a binary search tree is a useful data structure
• how to search for an item in a binary search tree
• how to insert an item into a binary search tree
• how to remove an item from a binary search tree
• the bitwise operators in C: &, |, ^, <<, >>, ~
• that a mask is used in conjunction with the AND operator to hide some bits while selecting others
• that bit operations are used to operate on bits of a data word for applications such as device controllers
• The purpose of a hash function
• The properties of a good hash function
• How to initialize a hash table that uses open addressing
• How to resolve a collision in a hash table by using linear probing
• The big-O results for searching an open address hash table that resolves collisions by using linear probing

BE ABLE TO:

• list the order in which nodes will be visited in a binary tree, using preorder, inorder, and postorder traversals
• draw "before" and "after" pictures of a binary search tree into which a particular value has been inserted
• draw "before" and "after" pictures of a binary search treee from which a particular value has been removed
• manipulate int's using #defines and bitwise operators
• determine the value of a specific bit in a word
• set specific bits in a word without affecting the other bits in the word
• extract specific bits from a word
• Show the contents of an open address hash table after several insertions and removals have occurred, given the hash function for the table

Sample Quiz Questions:

1. A binary tree contains these values:

         root  -->  15
                   /  \
                 23    16
                  \   /  \
                  9  17   63
                    /       \
                   5         12
                    \
                     37                 
   

   List the order in which the nodes would be visited if the tree was traversed using a postorder traversal.

2. Write a function called Pack that satisfies the following pre- and post-conditions:

   PRE:  char1 and char2 are characters
   POST: the function returns an unsigned short (i.e. 16-bit unsigned integer) with char1 packed into the
         high-order 8 bits and char2 packed into the low-order 8 bits
   

   You should use the shift and OR bit operations to accomplish the packing.

3. Draw a hash table with open addressing and a size of 9. Use the hash function "key%9". Insert the keys: 5, 29, 20, 0, 27 and 18 into your table (in that order).