Rosetta Code

Talk:AVL tree/C++: Difference between revisions

Page Discussion

Talk:AVL tree/C++ (view source)

Revision as of 15:59, 11 April 2017

322 bytes added ,  7 years ago
no edit summary
No edit summary
No edit summary
 
(8 intermediate revisions by the same user not shown)
Line 2:
 
I tested the elaborate code versus the shorter C++ version (on the main page) with the following results:
<pre>
 
AVLtree insertions took: 00:00:02.5097816
Set insertions took: 00:00:00.0080027
</pre>
 
Clearly, AVLtree is more like O(N<sup>2</sup>) or worse than O(log N). This is because it descends the tree during rotations (to adjust the balance factor). Set is clearly very fast at O(log N). The test was for 10000 insertions. If 100000 or 1000000 insertions are used Set rips through it but AVLtree stalls the machine.[[User:NNcNannara|NNcNannara]] ([[User talk:NNcNannara|talk]]) 12:45, 15 July 2016 (UTC)
 
Clearly,The AVLtreeabbreviated isJava moreand likeD O(N*N)samples oralso worsehave thanthe O(logsame N).problem Thisin isthat becausethey it descendsdescend the tree during rotations (to adjustascertain the balance factor)depth. SetYou ismust clearlybe verycareful fastnot atto O(logdo N).anything Theto testupset wasthe forperformance 10000of insertions.RotateLeft If 100000 or 1000000 insertions are used Set rips through it but AVLtree stalls theand machineRotateRight.[[User:NNcNannara|NNcNannara]] ([[User talk:NNcNannara|talk]]) 12:4526, 1516 July 2016 (UTC)
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/269055...269064"