Anonymous user
Talk:AVL tree: Difference between revisions
m
Just explaining why I put it in in the first place.
m (Just explaining why I put it in in the first place.) |
|||
| (20 intermediate revisions by 4 users not shown) | |||
Line 1:
==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.[[User:NNcNannara|NNcNannara]] ([[User talk: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 (and also to keep code length managable). [[User:Fwend|Fwend]] ([[User talk:Fwend|talk]]) 13:34, 13 July 2016 (UTC)
:: The code for the elaborate version is production standard. Its a bit longer but it is perfectly correct. [[User:NNcNannara|NNcNannara]] ([[User talk:NNcNannara|talk]]) 18:14, 13 July 2016 (UTC)
::: I appreciate that, but you can't hold other entries on this wiki to the same standard, because many of them are deliberately simplified. [[User:Fwend|Fwend]] ([[User talk:Fwend|talk]]) 18:30, 13 July 2016 (UTC)
:::: I did some testing and the abbreviated versions of C++ and Java have worse than O(N<sup>2</sup>) instead of O(log N) on insertions and deletions. The C++ commentary made the point itself that it made a second 'pass' to balance the tree. It is this that is killing its performance. [[User:NNcNannara|NNcNannara]] ([[User talk:NNcNannara|talk]]) 13:42, 15 July 2016 (UTC)
==New C++ AVL==
I added the source code of AVL Trees in C++. This source code is more than 20 years old now - although it did get heavily modified in 2006, right after the C# code was created. I'll leave it to others to port this C++ code to other languages like D.[[User:NNcNannara|NNcNannara]] ([[User talk:NNcNannara|talk]]) 11:45, 10 July 2016 (UTC)
I added a Managed C++ version in place of the existing code. I expect it will be moved to its own page as it is rather lengthy. [[User:NNcNannara|NNcNannara]] ([[User talk:NNcNannara|talk]]) 10:37, 13 July 2016 (UTC)
: I think the commentary from the discussion page is best placed on the task page itself, otherwise not many people are going to see it. [[User:Fwend|Fwend]] ([[User talk:Fwend|talk]]) 11:12, 13 July 2016 (UTC)
==Java AVL==
I added the source code of AVL Trees in Java.[[User:NNcNannara|NNcNannara]] ([[User talk:NNcNannara|talk]]) 13:13, 9 July 2016 (UTC)
: Your code is rather long, I've moved it to a separate page. [[User:Fwend|Fwend]] ([[User talk:Fwend|talk]]) 14:59, 9 July 2016 (UTC)
:: Thanks [[User:NNcNannara|NNcNannara]] ([[User talk:NNcNannara|talk]]) 11:42, 10 July 2016 (UTC)
==Here nor there==
Line 19 ⟶ 36:
: 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. ;-) –[[User:Dkf|Donal Fellows]] ([[User talk:Dkf|talk]]) 16:40, 31 May 2014 (UTC)
:: Of what I've seen, it can make them very ''very'' grouchy. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 22:04, 15 July 2016 (UTC)
== beed? ==
This very strange looking language doesn't appear to exist. I propose removing the example for it. [[User:Thebigh|Thebigh]] ([[User talk:Thebigh|talk]]) 12:52, 25 May 2020 (UTC)
Yes, go ahead and remove the strange looking language version. [[User:NNcNannara]].
*I see you already took care of it. Cheers! [[User:Thebigh|Thebigh]] ([[User talk:Thebigh|talk]]) 16:19, 25 May 2020 (UTC)
Yes the strange looking language is futuristic database compiler. But if you don't want it that's ok. I haven't released the compiler - it is written in Java. Note how the switch statement operates on enumerations - it is very advanced. The compiler compiles code into an AVL database - there are no executables at all. Note that there are no expressions in this language - just methods. That's why it may look a bit strange.
| |||