Weekly Note 13, DM42, fall 2006
Discussion Section December 4
-
Show the two remaining cases from the analysis of the splaying steps.
The bounds become better in both of these cases,
i.e., the case analyzed in the lecture is the one that gives the
worst-case bound with 3 in front of the logarithm.
-
How many bits of information is required for storing balance
information in a red-black tree? Can you think of any way to
encode that information using nodes with only the fields
key, left, and right? (all three fields may use the full range
of available values, so you cannot take any bits from any of these
fields).
-
-
Design a recursive method for merging two heap-ordered trees,
i.e., assume that the first heap has priority x in the
root and subtrees A and B, and the second heap has priority y
in the root and subtrees C and D. Recursively specify the (a)
resulting heap-ordered tree.
-
You probably noticed that you had some choice in the design.
Now assume that in each node, in addition to the priority,
we also store the size of the tree rooted by that node.
Can you find a choice of implementation, i.e., a method for
choosing which trees to merge, such that the running time
can be expressed T(n) = T(n/c) + 1 where c > 1?
-
If you could, what can you conclude on the running time?
-
How can the other (standard) operations on priority queues
be implemented on this structure?
-
When using this structure, do you get the best performance
in practice when the structure is perfectly balanced?
Lecture December 6
-
Randomized Search Trees [AS89].
Last modified: Mon Dec 4 14:02:31 CET 2006
Kim Skak Larsen
(kslarsen@imada.sdu.dk)