| Assignment • FAQ • Development Guide • Code • Checklist |
Question:
I understand the logic behind height and balance, but I do not know how to best implement them. Could you offer me some advice?
Answer:
You should set height and balance by moving back up the tree using the parent pointers in the last section of your insert code before you return from your function.
One suggestion is to have two local variables that each represent the height of the current TNode's children. You'd initialize these heights to be -1, assuming that each child doesn't exist.
You need logic in your code to independently check if there really is a left TNode or a right TNode from the current TNode. If so, then you'd reset each of these local variables accordingly. These checks both need to be done. This is not an if-then-else-if-else situation...you need an independent check for the left child, and an independent check for the right child.
Once the above is implemented, you have two local variables containing the heights of the left child and right child, even if such children don't even exist. You don't have to deal with null pointers any longer...since you already dealt with them when setting your two local variables.
You now have the components necessary to compute height and balance of the current TNode.
Question:
Could you offer a few suggestions as to how to implemente a loop based insert?
Answer:
1. Use the "parent" pointer to the TNode, pointing "up" the Tree. This way, you have a path to go up should you need to do so.
2. Have a "stack" of visited TNodes. Each time that you advance "current", you'd push the previous value of "current" on your Stack. When you need to go back up your Tree, you'd have a loop of popping from your stack until the stack was empty. This is really what happens on the RTS when you use recursion (which is not allowed for insert, lookup or remove in hw5).
There are probably other ways, too. These are optional suggestions. Choose one with which you are most comfortable.
Question:
Will we be marked off if we author our own private methods to avoid code redundency?
Like, for example, one method to do the searching similar to homework 6, that can be used in both remove and lookup? Or maybe a method for updating the heights/balances so we don't have to potentially type out that code twice in insert due to both sides of the tree?
Answer:
You can feel free to add methods to the TNode class.
Question:
How we should deal with deleted nodes when it comes to calculating the height and balance at nodes. Technically deleted nodes are still there maintaining the structure of the tree, so are we supposed to include deleted nodes when considering height and balance? Or are we supposed to find a way to make them not count when we calculate height and balance?
Answer:
You are to include deleted TNodes when calculating height and balance since they are still there as part of the tree.
Question:
If we try calling lookup in remove, and lookup returns the data, is there a way to access the hasBeenDeleted flag in the same TNode?
Answer:
Lookup returns the *data* that is contained by the target Node. It does not return the Node itself. Therefore, no, there is no way to use lookup to flag the removed node.
The alternative is to program a Locate method similar to what you had in hw6. This would return a pointer to the Node containing the data in question (or null if not present), which would then allow you to just flip the hasBeenDeleted flag or return the node's data as applicable for lookup/remove methods.
Question:
Could you rephrase "You may not give public access to non-static data fields for public classes"?
Answer:
If you add another field to Tree or UCSDStudent, such fields should br private. We don't want to give direct access to data fields.
Question:
Where can I learn more about generics?
Answer:
http://docs.oracle.com/javase/tutorial/extra/generics/index.html
| Assignment • FAQ • Development Guide • Code • Checklist |