Weekly Note 5, DM42, fall 2006
Discussion Section October 2
-
Show that a ½-weight-balanced Scapegoat tree has minimal height.
-
Use illustrations to go through the recursive method for the
restructuring of a subtree of a Scapegoat tree which is used
in Section 6.1, and make it clear which references must be maintained
during the process.
-
In Scapegoat trees we often need to know the sizes of subtrees.
Instead of computing these, we could consider storing these
values in the nodes.
Consider the pros & cons of this.
-
One could also register the potential of a node with that node.
What could that be used for?
-
Make a sketch of how the insertion procedure should be coded.
Note that there are no parents pointers. Assume that you have
the following procedures available:
restructure(T)
restructures the subtree T
and count(T)
counts the nodes in the subtree T
.
Lecture October 4
-
Universal hashing, [CLRS01] section 11.3.3.
-
Perfect hashing, [CLRS01] section 11.5.
Announcements
-
Friday, January 5, 2007 has been set by the administration
as the tentative date for the DM42 exam (confirmation pending).
Last modified: Wed Sep 27 09:21:12 CEST 2006
Kim Skak Larsen
(kslarsen@imada.sdu.dk)