Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: Eric Sosman Newsgroups: comp.lang.java.programmer Subject: Re: Immutable Datastructures with good Sharing Date: Sat, 05 Nov 2011 17:11:34 -0400 Organization: A noiseless patient Spider Lines: 24 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Sat, 5 Nov 2011 21:12:28 +0000 (UTC) Injection-Info: mx04.eternal-september.org; posting-host="HSlJAUb3pGXi3i7ZL/HoAw"; logging-data="32701"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19A9sF80jfdAPMf3NyMNDyE" User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:7.0.1) Gecko/20110929 Thunderbird/7.0.1 In-Reply-To: Cancel-Lock: sha1:/u1UbwjEjqty1sLXRnQshcrfXvw= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:9615 On 11/5/2011 4:48 PM, Stefan Ram wrote: > Eric Sosman writes: >> Wikipedia defines it as "a widely-used data structure that >> emulates a hierarchical tree structure with a set of linked nodes." >> That's not a very good definition, since trees need not have links, >[...] > Without links, how does one represent the absence of a > subtree? Ever studied Heapsort, or a heap-based priority queue? There's clearly a tree involved, but where are the links? In a heap of N elements, element [N-1] has two empty subtrees; how is their absence denoted? Or consider the tree (A (B (C D) E (F (G H) I)) () J): Where are the links? See the empty subtree? See also Knuth "The Art of Computer Programming, Volume I: Fundamental Algorithms." The title of section 2.3.3 is "Other Representations of Trees" ... -- Eric Sosman esosman@ieee-dot-org.invalid