Subject: Re: [xsl] A compelling use case for employing binary trees in XML processing? From: Dimitre Novatchev <dnovatchev@xxxxxxxxx> Date: Sun, 9 Dec 2012 16:49:06 0800 
> 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 nonfunctional array) and the initial part of a sequence (the subsequence 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 valuespace 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@xxxxxxxxx> 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/thebinarysearchtreedatastructurehavingfunwithxpath30/
Current Thread 


< Previous  Index  Next > 

Re: [xsl] A compelling use case for, Michael Kay  Thread  Re: [xsl] A compelling use case for, Wolfgang Laun 
Re: [xsl] A compelling use case for, Michael Kay  Date  Re: [xsl] XML/XSL Revision Control/, Michel Hendriksen 
Month 