Path: dp-news.maxwell.syr.edu!spool.maxwell.syr.edu!drn.maxwell.syr.edu!news.maxwell.syr.edu!postnews.google.com!g14g2000cwa.googlegroups.com!not-for-mail From: "-CELKO-" Newsgroups: comp.databases.theory Subject: Re: Nested sort, trying again Date: 8 Oct 2005 16:24:20 -0700 Organization: http://groups.google.com Lines: 11 Message-ID: <1128813860.926512.275700@g14g2000cwa.googlegroups.com> References: NNTP-Posting-Host: 63.246.173.25 Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-Trace: posting.google.com 1128813868 21914 127.0.0.1 (8 Oct 2005 23:24:28 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Sat, 8 Oct 2005 23:24:28 +0000 (UTC) In-Reply-To: User-Agent: G2/0.2 X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 2.0.40607; .NET CLR 1.1.4322),gzip(gfe),gzip(gfe) Complaints-To: groups-abuse@google.com Injection-Info: g14g2000cwa.googlegroups.com; posting-host=63.246.173.25; posting-account=EzrcbQ0AAACimcwOd0QEJhKx5W98nxwt Xref: dp-news.maxwell.syr.edu comp.databases.theory:33966 Well, you have code to move subtrees around in TREES & HIERARCHIES, so you can sort the tree structure after a change. A node (lft,rgt) pair (x,y) has a level that is easy to compute so you can see all the children of a common parent; this gives an ugly view with all the nodes at that same level in the hieratchy. The brother to the right is (r, y+1) and the brother to the right is (x-1, s) , or they do not exist. But being lazy, I would convert the nested sets to an adjacency list, then use the stack algorithm to rebuild the tree in sorted order. Slower, but easier to code.