Anonymous user
Talk:AVL tree/C++: Difference between revisions
no edit summary
No edit summary |
No edit summary |
||
Line 8:
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)
The abbreviated Java and D samples also have the same problem in that they descend the tree to ascertain the depth. You must be careful not to do anything to upset the performance of RotateLeft and RotateRight.
| |||