הטכניון - מכון טכנולוגי לישראל Technion - Israel Institute of Technology Технион - израильский технологический институт ألتخنيون - معهد تكنولوجي لإسرائيل

02340218 - Data Structures 1 - מבני נתונים 1

חורף 2011-2012Winter 2011-2012Зима 2011-2012شتاء 2011-2012

שאלות ותשובות - Dry 3 Frequently Asked Questions - Dry 3 Вопросы и Ответы - Dry 3 أسئلة وأجوبة - Dry 3

		.. (לתיקייה המכילה)

Last Updated: 25.1.2012

- 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.

שאלות ותשובות - Dry 3 Frequently Asked Questions - Dry 3 Вопросы и Ответы - Dry 3 أسئلة وأجوبة - Dry 3

1: In Question 3 - AverageAround(x) - do you mean the log(n) plants after x or before x or both?

2: In Question 1b: Is the expression log(n/log(log(n))) or log(n)/log(log(n))?

3: In question 1b, what are the exact parameters to the function?

4: In question 5, if we have several components with the same weight, what is their relative order?

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?

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?