Talk:Weight-balanced tree/Archive 1

Archive 1

I am still looking for more references for this page, if you find some please post thanks.

Also, i would like some general algorithums for insertion, deletion, and what happens when you change the activity count of a node, how does the tree balance. thanks Ken

ELOSS

Is ELOSS a standard term? I searched for "eloss balanced tree", and the first three hits were copies of this article. None of the other results seemed relevant. 69.234.125.75 (talk) 18:07, 26 September 2009 (UTC)

The Diagram::What does the Numbers mean

In the Diagram there are Numbers associated with each node. But its meaning is not clear. cause in text its stated that Items are sorted according the 'A', 'G', 'F', 'N' etc. But The Numbers are not sorted according to left less, right greater fashion. So meaning of those numbers (20,17,18,,12,11,10 etc..) is not clear —Preceding unsigned comment added by 59.93.242.169 (talk) 16:47, 27 October 2009 (UTC)

Hopefully it's clearer now. Bobmath (talk) 16:52, 8 November 2009 (UTC)

See also

Why list AVL and Red-Black-Trees (and possibly others) here? Neither are weight-balanced (proofs are linked in the respective articles).

^{Akerbos (talk) 22:09, 12 September 2012 (UTC)}

Weight-balanced vs. optimal trees: rewrite needed

As has been noted previously, this article has only one reference. I did find a lot of other sources for weight-balanced trees, but they all seem to be about a different structure altogether:

• Nievergelt, J.; Reingold, E. M. (1973). "Binary Search Trees of Bounded Balance". SIAM Journal on Computing. 2: 33. doi:10.1137/0202005.
• Blum, Norbert; Mehlhorn, Kurt (1980). "On the average number of rebalancing operations in weight-balanced trees" (PDF). Theoretical Computer Science. 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3.
• Tsakalidis, A. K. (1984). "Maintaining order in a generalized linked list". Acta Informatica. 21: 101. doi:10.1007/BF00289142.
• Adams, Stephen (1993). "Functional Pearls: Efficient sets—a balancing act". Journal of Functional Programming. 3 (4): 553–561. doi:10.1017/S0956796800000885.
• Hirai, Y.; Yamamoto, K. (2011). "Balancing weight-balanced trees". Journal of Functional Programming. 21 (3): 287. doi:10.1017/S0956796811000104.

This other structure is quite popular in functional programming circles, being used for sets and maps in MIT Scheme, Slib and Haskell libraries. What is described on this page seems to be the optimal binary search tree rather than the weight-balanced one.

I'm planning to end this confusion by replacing the present article by one based on the weighted trees of the references above. QVVERTYVS (hm?) 08:38, 26 March 2015 (UTC)