Extensions and Left Descent Elements are
Disjoint Sets
-- easily proven (thanks to Margaret Maxfield)
-- supports the dissection of the binary tree into left descent assemblies (l.d.a.s)
-- The l.d.a. headers (in {5[8])} are collected as the root of abstract
predecessor tree.
-- No left descent elements are in {5[8]}, only
{(1,3, and 7)[8]}.
-- All l.d.a.s are completed by a leaf node
set (in {0[3]}) in the abstract predecessor tree.
-- Thus all elements of the binary predecessor tree appear in
the abstract predecessor tree.
next slide
return to slide index