 |
.. (לתיקייה המכילה) | |
What is "linear order" in Q1? | |
|
The linear order means that the elements are ordered as if they were in a linked list, according to the order of Inseret/Delete. In Q1c you need to simulate this order, so that all operations take O(lg n) in the worst case. Example of linear order: Insert(NULL, k1) k1 p = Find(k1) Insert(p, k2) k1->k2 p = Find(k2) Insert(p, k3) k1->k2->k3 p = Find(k2) Insert(p, k4) k1->k2->k4->k3 |
In Q3, what is the meaning of the key? | |
|
The tree is ordered both by a key and by a priority. By the key it's a binary search tree (i.e., the bigger key goes to the right son) and by priority it's a heap. |
Do we need to implement Insert/Delete in Q4a? | |
| NO!!!!!!!! Only inverts and maxs are necessary. No one will access the matrix directly. |