Talk:AVL tree

From Rosetta Code

The Existing C++ and Java Versions (i.e. not the elaborate versions)

The C++ code present on the main page does not define a non-generic base class for node. This means that the code regenerates the balancing routines for each data type supported by the generic. Also, the code descends the tree to calculate the node balance for each of the rotations (which is a real no-no). This would heavily impact balancing performance. The elaborate version is completely different and the methods to rotate don't update the balance factor (which incidentally is an enum). The Java version that is present on the main AVL Page (not the elaborate version) suffers from the same problem in that it also descends the tree during rotations to calculate the balance.NNcNannara (talk) 12:57, 13 July 2016 (UTC)

It's just example code, it's not production quality code. These codes are only intended to demonstrate the principle of an AVL tree. Secondary features such as input validation, error handling, cloning, generics etc, are often relaxed or omitted in RosettaCode entries, so as not to distract from primary features. Fwend (talk) 13:34, 13 July 2016 (UTC)

Here nor there

I coded the Go solution from code at http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx. There is complete working code there in C, it's public domain, and I found it relatively easy to port. (I found this site from a comment in Chromium source that said they used it.) The tutorial claimed that the version was relatively compact, as AVL code goes, which seemed good for RC, especially since AVL trees are a little on the complex side as RC tasks go. I resisted the urge to compact or optimize the code more, which certainly could be done. —Sonia (talk) 22:39, 22 May 2014 (UTC)

As long as the copyright issues aren't going to bite us, that won't be a problem. I advise not heavily optimising the code, unless it also makes the code easier to understand as a general programmer (of Go, of course; don't worry too much about general programmers of some other random language). We don't aim for optimal solutions here precisely because they tend to be so hard to read, understand and compare. (We also can't compare performance between languages; matching hardware and language implementation optimisation levels is utterly impossible between different developers' systems. Let some other site worry about that.) –Donal Fellows (talk) 16:40, 31 May 2014 (UTC)
There is some new C#, C++ and Java code, maybe you could port that Donal.NNcNannara (talk) 12:24, 10 July 2016 (UTC)

Basic operations

The Go code I'm posting today just implements the operations in the original C, an insert allowing multiple keys and a delete that returns no status. Should the task be more specific than “basic operations?” In particular there is no find in my code. Find first, find last, find previous, find next, other flavors of insert and delete might be interesting. Wikipedia mentions find previous and find next as interesting. —Sonia (talk) 22:39, 22 May 2014 (UTC)

The minimum operations have got to be insert and lookup, but remove and print (of the tree) are a good idea too. In fact, for an RC task I'd say that print is vital. –Donal Fellows (talk) 16:40, 31 May 2014 (UTC)

Completing the task description

The task should say what basic operations to implement and say to demonstrate them somehow. Demonstrate each operation should be a minimum, but it might be nice to specify some data to insert, delete, and so on, as a way of assessing correct results. —Sonia (talk) 22:39, 22 May 2014 (UTC)

Have a care, as that can easily invalidate other people's solutions, which can make them a little grouchy. Or at least it does so to me. ;-) –Donal Fellows (talk) 16:40, 31 May 2014 (UTC)