I understand that binary trees can be used to sort data. But XSLT already has
<xsl:sort>, so using binary trees for
sorting isn't a particularly compelling use case.
I guess you mean "binary search trees* -- other kinds of binary trees
such as the heap data structure do not have the complete set of their
items sorted.
A binary *search* tree (and I mean *balanced* binary serch tree) has
more useful properties than just that it one of its serializations
presents the values in sorted order.
A binary search tree allows searches and insertions with efficiency
of O(log(N)). In contrast, an insertion in an array or in a sequence
is O(N) -- the whole array needs to be copied (even the non-functional
array) and the initial part of a sequence (the sub-sequence before the
insertion point) of a persistent (functional sequence) needs also to
be copied -- this is on average N / 2 -- so again we have O(N) here.
The deletion in a balanced binary serch tree is also O(log(N)).
This makes the balanced binary search tree quite good even for
implementing dictionaries and sets. A disadvantage for such binary
search tree -based implementations is that the value-space must have
total ordering (while other implementations of a dictionary or set
require only an equality (equivalence) operation).
Cheers,
Dimitre.
On Sun, Dec 9, 2012 at 2:49 PM, Costello, Roger L.
<costello(_at_)mitre(_dot_)org> wrote:
Hi Folks,
Dimitre has created a beautiful set of functions for building binary trees
[1].
I understand that binary trees can be used to sort data. But XSLT already has
<xsl:sort>, so using binary trees for sorting isn't a particularly compelling
use case.
I am seeking a compelling use case for binary trees -- given XML document
foo.xml and processing requirement P, a binary tree is ideally suited.
Would you provide a simple, compelling use case please?
/Roger
[1]
http://dnovatchev.wordpress.com/2012/01/09/the-binary-search-tree-data-structurehaving-fun-with-xpath-3-0/
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--