![]() |
.. (לתיקייה המכילה) | |
Last Updated: 25.1.2012
- 19.1: Added 1,2.
- 22.1: Added 3,4.
- 25.1: Added 5,6.
- 19.1: Added 1,2.
- 22.1: Added 3,4.
- 25.1: Added 5,6.
1: In Question 3 - AverageAround(x) - do you mean the log(n) plants after x or before x or both? | |
Neither. The average is over the log(n) plants closest to x in either direction. That is, if log(n)=2, we want the 2 plants closest to x; this may be the 2 plants just before x, 1 just before x and 1 just after x, or 2 just after x. Notice that "the log(n) closest" might be ill-defined: for example, if log(n)=2 and we have plants in locations: 10, x=12, 13, 14, the 2 closest might be the plants in locations (10 and 13) or (13 and 14). In such a case - if the log(n)-farthest is either before or after x - pick the plant before x as farthest among these log(n) plants. In our case, the log(n)=2 closest would therefore be (10 and 13). |
2: In Question 1b: Is the expression log(n/log(log(n))) or log(n)/log(log(n))? | |
log(n)/log(log(n)). In words: log(n) divided by log(log(n)). |
3: In question 1b, what are the exact parameters to the function? | |
T - a 2-3 tree. v - a pointer to a node (and the index of the key to change, in case the node is an internal node with several keys). x - the new value to be written as the key. The function should change the key of the node pointed to by v to x, in such a way that T remains a legal 2-3 tree. |
4: In question 5, if we have several components with the same weight, what is their relative order? | |
In such a case, the relative order is determined by the highest-index vertex in the component. For example, if A={1,2,8} and B={2,3,5} are two components of total weight 20 (with the nodes indicated), then A is "heavier" than B, since the highest-index vertex in A is 8 and the highest-index vertex of B is 4. |
5: In Question 1b: if we are asked to change the key of an internal node to a value which is inconsistent with the values in the sub-trees, what should we do? | |
In such a case, do nothing. |
6: In question 1b: can we assume that leaves that were not changed by the function are stored in the same address in the memory as before the call to the function? | |
Yes, you may. |