self-balanced binary tree: insertion order

hydraMax · 11-02-2013, 04:37 AM

Does anyone happen to know off-hand: What is order ("Big-O") of the insertion algorithm on a self-balanced binary tree? I know that the search order is O(log(n)). But I am wondering how badly the insert operation is effected by the balancing operation.

kbp · 11-02-2013, 05:44 AM

see ntubski's link below

ntubski · 11-02-2013, 09:45 AM

You probably want to look at the Self-balancing binary search tree article:

Quote:

In the asymptotic ("Big-O") sense, a self-balancing BST structure containing n items allows the lookup, insertion, and removal of an item in O(log n) worst-case time...

psionl0 · 11-02-2013, 02:04 PM

Quote:

Originally Posted by hydraMax

Does anyone happen to know off-hand: What is order ("Big-O") of the insertion algorithm on a self-balanced binary tree? I know that the search order is O(log(n)). But I am wondering how badly the insert operation is effected by the balancing operation.

Since you would have to wander back up to the root node fixing the imbalances as you go, the timing of any insertion or deletion is still O(log n).