What is the most efficent way to remove all element in AVL tree (sorted-removals)
up vote
0
down vote
favorite
I know removing a node in AVL tree takes time complexity of O(logn). That being said, removing an AVL tree with n nodes would take O(nlogn). However, I am wondering if my goal is to have the sorted element of AVL tree that I could remove all elements in O(n) instead of O(nlogn). Possibly by implementing an remove element that would take O(1).
I was not able to find any way to do it in O(n). Is it because we can't or am I missing something?
algorithm oop data-structures binary-tree avl-tree
asked Nov 19 at 0:52
Kbiir
1
add a comment |
up vote
0
down vote
favorite
I know removing a node in AVL tree takes time complexity of O(logn). That being said, removing an AVL tree with n nodes would take O(nlogn). However, I am wondering if my goal is to have the sorted element of AVL tree that I could remove all elements in O(n) instead of O(nlogn). Possibly by implementing an remove element that would take O(1).
I was not able to find any way to do it in O(n). Is it because we can't or am I missing something?
algorithm oop data-structures binary-tree avl-tree
asked Nov 19 at 0:52
Kbiir
1
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I know removing a node in AVL tree takes time complexity of O(logn). That being said, removing an AVL tree with n nodes would take O(nlogn). However, I am wondering if my goal is to have the sorted element of AVL tree that I could remove all elements in O(n) instead of O(nlogn). Possibly by implementing an remove element that would take O(1).
I was not able to find any way to do it in O(n). Is it because we can't or am I missing something?
algorithm oop data-structures binary-tree avl-tree
asked Nov 19 at 0:52
Kbiir
1
I know removing a node in AVL tree takes time complexity of O(logn). That being said, removing an AVL tree with n nodes would take O(nlogn). However, I am wondering if my goal is to have the sorted element of AVL tree that I could remove all elements in O(n) instead of O(nlogn). Possibly by implementing an remove element that would take O(1).
I was not able to find any way to do it in O(n). Is it because we can't or am I missing something?
algorithm oop data-structures binary-tree avl-tree
algorithm oop data-structures binary-tree avl-tree
asked Nov 19 at 0:52
Kbiir
1
asked Nov 19 at 0:52
Kbiir
1
asked Nov 19 at 0:52
Kbiir
1
asked Nov 19 at 0:52
Kbiir
1
asked Nov 19 at 0:52
Kbiir
1
1
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
3
down vote
If you don't need to preserve AVL structure after every deletion, then perform post-order traversal, just deleting every node without balancing instead of "Display the data part"
answered Nov 19 at 6:45
MBo
45.4k22847
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
If you don't need to preserve AVL structure after every deletion, then perform post-order traversal, just deleting every node without balancing instead of "Display the data part"
answered Nov 19 at 6:45
MBo
45.4k22847
add a comment |
up vote
3
down vote
If you don't need to preserve AVL structure after every deletion, then perform post-order traversal, just deleting every node without balancing instead of "Display the data part"
answered Nov 19 at 6:45
MBo
45.4k22847
add a comment |
up vote
3
down vote
up vote
3
down vote
If you don't need to preserve AVL structure after every deletion, then perform post-order traversal, just deleting every node without balancing instead of "Display the data part"
answered Nov 19 at 6:45
MBo
45.4k22847
If you don't need to preserve AVL structure after every deletion, then perform post-order traversal, just deleting every node without balancing instead of "Display the data part"
answered Nov 19 at 6:45
MBo
45.4k22847
answered Nov 19 at 6:45
MBo
45.4k22847
answered Nov 19 at 6:45
MBo
45.4k22847
answered Nov 19 at 6:45
MBo
45.4k22847
45.4k22847
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53367007%2fwhat-is-the-most-efficent-way-to-remove-all-element-in-avl-tree-sorted-removals%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
