DOC PREVIEW
WSU CPTS 223 - Homework

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Homework 3 (Cpt S 223)Due Date:October 8, 2010Total points:471. (3 points)Give the expression tree for (a+ ( b-c)*(d*e)-f)*(g+h-i).2. (10 points)ABCF IGH KJL MD EFor the above shown tree, answer the following:a) Height of the tree = ?b) Depth of node J = ?c) Height of node J = ?d) Redraw the tree by the First-child, Next-Sibling method.e) Give the post-o r der, pre-order and in-order traversals of the tree.13. (6 points)Just given the pre-order and in-o r der traversals of a tree, one can reconstruct thetree. To illustrate this capability, draw the tree by reconstructing it from the followingtraversals:Pre-order traversal is: a, f, e, d, g, h, c; andIn-order traversal is: e, f, g, d, h, a, c.(Note: nodes are labeled by alphabets.)4. (7 points)a) Draw the final BSTs that result from the following two different insertion sequencesof the same set of elements:a) Insertion sequence: 8 7 1 6 2 3 5 4b) Insertion sequence: 5 7 3 2 8 6 4 1For both cases, start with an empty tree.b) Briefly state what is so markedly different between these two resulting BSTs con-structed over the same set of elements but with just different insertion sequences.5. (5 points)Starting with an empty tree T0, show the set of BSTs T0⇒ T1⇒ T2⇒ . . . resultingfrom performing the following sequence of operations (in that order): Insert(5), In-sert(10), Insert(2), Insert(7), Insert(8), Remove(5).PS: you need to show the tree resulting after each insertion or removal operation.6. (8 points)Starting with an empty tree T0, show the set of AVL trees T0⇒ T1⇒ T2⇒ . . . re-sulting from performing the f ollowing sequence of operations (in that order): Insert(7),Insert(5), Insert(2), Insert(4), Insert(3), Insert(1). If at any step you need to rebalancethe tree using rotation, then clearly identify: i) the node that has the imbalance, and2ii) the corresponding rotation “case” that applies there (i.e., case 1 or 2 or 3 or 4).7. (8 points)Exercise 4.19. (Weiss, page 177). Follow t he same instructions a s outlined for


View Full Document

WSU CPTS 223 - Homework

Download Homework
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?