Talk:AVL tree: Difference between revisions
Content added Content deleted
No edit summary |
No edit summary |
||
Line 4: | Line 4: | ||
:: 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) |
:: 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 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*N) 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. If it is any consolation, the Wikipedia pseudo code will also be O(N*N) or worse too. The page [[AVL |
:::: I did some testing and the abbreviated versions of C++ and Java have worse than O(N*N) 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. If it is any consolation, the Wikipedia pseudo code will also be O(N*N) or worse too. The page [[AVL Tree/Performance]] shows the performance test. |
||
[[User:NNcNannara|NNcNannara]] ([[User talk:NNcNannara|talk]]) 13:42, 15 July 2016 (UTC) |
[[User:NNcNannara|NNcNannara]] ([[User talk:NNcNannara|talk]]) 13:42, 15 July 2016 (UTC) |
||