Sacramento Business Daily

Explain how insertion guarantees can be satisfied by an implementation based around balanced tree?

The performance of insertion is O(log n) so how to explain this based on the question above..

Public Comments

1. It's due to balancing. You will never get the case of a degenerate tree. Consider a binary tree where you insert nodes to the left if < (less than) or to the right when >= (greater than or equal to). If you insert a sequence of numbers [0,1,2,3,4,5,6,...] you will get a degenerate tree. This is essentially the same worst case as insertion sort and the data structure now resembles a linked list in the state after adding the sequence of numbers. By balancing/reordering tree, you're ensuring the physical structure resembles a tree which allows you to exploit logarithmic time inserts AND searches. There is another requirement (I believe) that the balancing must be done in logarithmic time. In the sources, see: degenerate tree Now -- can you stop copying & pasting your homework and think about this a little?