Erik's answers to the 331 Review questions

Granted, some questions are missing, mainly because I'd rather leave stuff out than pass on false information. Anyway, this is the better part of the answers to page 5. My appologies for the incompleteness, but I'm also quite busy.

65.

How do you find the smallest element in a binary tree?
Travel to the left-most node of the tree.

66.

What is the worst case running time to search a binary tree?
If the items were added randomly, its O( lg n ), otherwise, if they were added in order, we're looking at O( n ).

67.

What is a balanced tree?
A binary tree such that the height of the left subtree is the same as the right subtree.

68.

Describe algorithms for depth-first and breath-first graph traversal
Depth first:
dfs( node i ):
  visited[ i ] = true;
  print i
  foreach neighbor of i
     if( !visited[neighbor] ) dfs( neighbor );
Breadth first:
bfs( node i ):
  visited[i] = true;
  print i
  foreach neighbor of i
     if( !visited[ neighbor ] ) print neighbor
  foreach neighbor of i
     if( !visited[ neighbor ] ) bfs( i );

69.

What properties does an AVL tree have?

70.

What is the worst-case running time of a search in an AVL tree?
Searches are always lg n

71.

How do you perform an LL rotation in an AVL tree? When is such a rotation appropriate?
An LL rotation is performed when the balance factor becomes +2 n the root. This means that the node was added on the left child of the root's left child. In the proceeding example, node 'e' caused the balance factor to become +2:
The first thing we do is find node d (because this is an LL rotation, D is the left child of the root's left). We know that e < d < b because of their relative positions, so we can rearange the subtree to be like this:
Now, bot b and d are less than a, so either can be the left child of a:

72.

Question 71 for RR LR and RL.
RR is a mirror image of LL. LR and RL are a bit more involved, but the idea's the same. See page 560-562 in the text.

73.

Give some pseudo-code to do an RR rotation, don't worry about updating balance factors
Its acutally pretty easy:
Node *a = root;
Node *b = root->right;
Node *bl = b->left;
root = b;
root->left = a;
a->right = bl;

74.

When you insert a key x into an AVL tree, and this causes the tree to become unbalanced, on which node do you perform the rotation?
In a nutshell, on of the root node's grand children.

75.

What's the difference between hashing and searching?
Hashing is the process of running input through a function to generate a (hopefully) unique ID with which to associate it. Searching is the process of looking through a list of a given key.
How does Heapsort work?
See the textbook
page 4 | page 6