| Assignment • FAQ • Development Guide • Code • Checklist • |
Question:
Okay, so I really don't understand pointer in parent. We don't have a parent pointer this time, so how are we supposed to get the pointer to the parent node?
Answer:
PointerInParent is not a pointer TO the parent node, but a pointer field IN
the parent node. It is a reference to
the pointer in the parent TNode
We do not need a parent field this time, becuase we can rely on recursion
to traverse back up the tree when setting height and balance.
We have to pass this parameter becuase removing a node or restructuring a tree often requires the pointer in the parent node to point to another node.
Question:
I am really confused about the replaceAndRemoveMin function. Could you please explain it again?
Answer:
When the TNode we wish to delete has two children, the structure of the tree must not be changed after deleting the data.
We therefore find the successor node and replace the data of the node we wish to delete with the data from the predecessor,
and delete the successor node.
The net result is that the data in the target Node is deleted,
and the binary tree has retained it's property of being correctly structured.
The successor node can be thought of as either the node directly after the current node in the alphabetical ordering of the tree,
or the minimum node in the right subtree of the current node.
The targetTNode parameter is a reference to the TNode
The PointerInParentBox parameter is used to connect the Tree as it
is restructured when as the recursion completes.
This value will need to be set to either:
1) "right" // when you've found the immediate successor.
2) "this" or unchanged // otherwise
Since both reference parameters are being updated in this
method, these are output parameters.
Question:
Why do we need PointerInParentBox?
Answer:
Because there was no passing by reference in Java, to have an output paramemeter, you would need an object that is stored in the Heap. Since it is an output parameter, you would pass it in to your recursive calls, inside it you update the left and right and store it in the pointerInParentBox. Finally, when you come back from recursion, you open the box by doing left = leftBox.pointer or right = rightBox.pointer to make use of the output parameter.
Question:
Please explain the parameters to Remove, and how I call this function. Thanks.
Answer:
The following information will help you to understand the
parameters to TNode's Remove function.
"element" is an input parameter. It's an
input parameter used to know how to search down the Tree.
The PointerInParent parameter is used to connect to the
parent when the Tree as the recursion completes. Additionally,
Remove passes this parameter to setHeightAndBalance.
pointerInParentBox is an output parameter.
This value will set to either:
1) "left" or "right" // when the target TNode
// is being deleted has only one child
2) "this" or unchanged // otherwise
The fromSHB parameter tracks whether or not Remove was called
from setHeightAndBalance. If Remove was called from
setHeightAndBalance, you don't want to again call
setHeightAndBalance since the updating will occur upon
reinserting the removed data.
The return result of Remove is the Whatever element removed, or null if element does not exist.
Question:
I am not sure why we need the pointerToParentBox parameter for setHeightAndBalance function. We didn't need that before. Please explain.
Answer:
The PointerInParent parameter for setHeightAndBalance is used to
pass to Remove and to Insert as the way to restructure the Tree if
the balance goes beyond the threshold. You'll need to
store the removed data in a working RTS TNode
| Assignment • FAQ • Development Guide • Code • Checklist • |