Talk:AVL tree/C++: Difference between revisions
Content added Content deleted
mNo edit summary |
mNo edit summary |
||
| Line 2: | Line 2: | ||
I tested the elaborate code versus the shorter C++ version (on the main page) with the following results: |
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 |
AVLtree insertions took: 00:00:02.5097816 |
||
Set insertions took: 00:00:00.0080027 |
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, 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) |
||