Subject: Re: How to construct a tree from a given structure and elements

From: "Richard A. O'Keefe" <[email-masked]>
Date: Wed, 6 Dec 2000 16:13:30 +1300 (NZDT)

Continuing with Uwe Lesta's problem,
where we now know that he wants weight balanced trees.
We do not yet know whether he wants binary trees, ternary trees,
N-way trees, or what.
I shall >>assume<< that 

    :- type node_name = atom.
    :- type weight = float.
    :- type weighted_tree
        --> no_wt
          | wt(node_name, weight, weighted_tree, weighted_tree).

is intended.  We also know that Uwe Lesta is aware that the nodes
of the result will be ordered, and that what counts as a good order
depends on what *he* wants to do with them (not some mythical
administrator), but that he does not care to tell us what that is,
so it cannot matter all that much.

I shall use the definition

    weight(no_wt, 0.0).
    weight(wt(N, NW, L, R), TW) :-
	node_weight(N, NW),   % NW is cached in the wt to save time.
	weight(L, LW),
	weight(R, RW),
	TW is NW + LW + RW.

But more is required to define what a "weight-balanced" tree IS,
before one can say how to make one.  If I make quote

	Kurt Mehlhorn,
	Data Structures and Algorithms 1: Sorting and Searching
	Section III.5.1 Weight-Balanced Trees.

       "For this section, $\alpha$ is a fixed real,
        $1/4 < \alpha \le 1 - \sqrt 2 / 2$.
        The bounds on $\alpha$ will become clear later on.
        
        Definition:\\
	a) Let $T$ be a binary tree with left subtree $T_l$ and
	right subtree $T_r$.  Then
	$[\rho(T) = |T_l|/|T| = 1 - |T_r|/|T|$]
	is called the root balance of $T$.
	Here $|T|$ denotes the number of leaves of tree $T$."

    More generally, |T| might denote the sum of the weights of
    the nodes of T.

       "b) Tree $T$ is of bounded balance $\alpha$ if,
	for every subtree $T'$ of $T$,
	$[alpha \le \rho(T') \le 1-\alpha$."

That is, it is necessary to specify an \alpha.

Failing a specification of \alpha, let's just try to do the best
we can.  From the definition above, the balance of the root does
not depend on the structure of the subtrees.  That's an important
point.

Here is an algorithm for constructing a weight balanced tree from
a list of nodes, the left-to-right order of which is to be preserved.

    if TheList is empty, return no_wt as the answer.
    for each L, X, R such that append(L, [X|R], TheList)
	compute weight sum of L as LW  (incrementally!)
	compute weight sum of R as RW  (incrementally!)
	compute Rho as LW / (LW+RW)
    choose the split L, X, R for which abs(0.5 - Rho) is a minimum.
    recursively form L into TL and R into TR
    report wt(X, node weight of X, TL, TR) as the answer.

The cost of this can be as high as O(N**2), because the weights could
be very different (so that at each stage the chosen L has only one
element, for example), but it will normally be around NlgN.

The constraint that the left-to-right order has to be preserved is
very useful here, because it limits the number of alternatives we
have to consider.  If we could imagine any split, then we'd have
to consider

    for each L, X, R such that 
	LR^(select(X, TheList, LR), subseq(LR, L, R))
	determine Rho
	...

That's clearly not a good idea, there are N*2**(N-1) choices at the
top level.  No doubt there is a dynamic programming algorithm that does
much better.  But before anyone goes looking for it, I think we need to
understand the problem better.

	% tree_struct(+child, +parent, +max_childs).
	tree_struct(node1, root, 2).
	tree_struct(node2a, node1, 5).
	tree_struct(node2b, node1, 8).
	tree_struct(node3a, node2a, 2).
	tree_struct(node3b, node2a, 1).
	tree_struct(node3a, node2b, 2).
	tree_struct(node3c, node2b, 10).
	% ...
	
The + modes in the comment don't make a lot of sense.
I would expect the modes (+,+,?), (+,?,?), and (?,+,?) to be useful.
I don't undersand what max_childs (max_children?) is supposed to mean.
This table lists the edges of a directed acyclic graph

    root
    |
    +--node1
       |
       +--node2a
       |  |
       |  +--node3a
       |  |
       |  +--node3b
       |
       +--node2b
          |
          +--node3a
          |
          |--node3c
       
(it is not a tree, because node3a appears twice in it),
and it associates "max_childs" numbers with the edges.
What does it mean for an edge to have children?

	% material(+node, +amount).
	material(node3a, 7).
	material(node3c, 30).
	material(node2b, 6).
	
Again the + modes in the comment are puzzling; I could understand
(?,?) and (+,?), but what would be the point of calling material/2
if you already knew the answer?
	
A quick review of DEC-10 Prolog modes:

    +	means "the way I intend to use this predicate,
	this argument will never be a variable at the point of call".

    -	means "the way I intend to use this predicate,
	this argument will always be a variable at the point of call".

    ?	means "the way I intend to use this predicate,
	sometimes this argument might be a variable at the point of
	call, and sometimes it might not."

We don't need to understand the material/2 and node_points/2 predicates
other than to note that they relate properties to node names, the node
names referring to nodes of the tree_struct/3 tree.
	
Now we can look closely at this question:

	What is the best way to write a program that build a balanced tree
	from this facts ?
	
The question cannot yet be answered, because we have a collection of nodes
forming a DAG, and no indication of what parent/child edges are to be
allowed in the result.  The usual application of weight balanced trees is
to binary searching, in which the left to right order of the leaves of the
result must be consistent with the ordering of the values in the nodes,
and parent/child edges may be freely chosen consistent with that order.
But in this problem, we have no ordering of values in nodes, but we do
seem to have existing parent/child edges, so how may they be adjusted?

In short, we still don't know what would constitute an answer to this
question, because the question is still incomplete.