Regarding balanced tree analysis

Question

I am reading a book on trees. here is the text snippet.

There are quite a few general algorithms to implement balanced trees. Most are quite a bit more complicated than a standard binary search tree, and all take longer on average. They do, however, provide protection against the embarrassingly simple cases.

A newer, method is to forego the balance condition and allow the tree to be arbitrarily deep, but after every operation, a restructuring rule is applied that tends to make future operations efficient. These types of data structures are generally classified as self-adjusting. In the case of a binary search tree, we can no longer guarantee an O(log n) bound on any single operation, but can show that any sequence of m operations takes total time O(m log n) in the worst case.

Questions on above text snippet

1. How author came to conclusion in first paragraph what does author means embarrassingly simple cases how general algorithms of balanced trees provide protection against this?

2. What does author mean "in last paragraph any sequence of m operations take total time O(mlogn) how we came to this conclusion, request to explain with example.

Thanks!

Answer 1

1.) I believe the author meant cases such as a string of nodes that basically look like a dangling list. With trees that self adjust and rotate (look into AVL Trees), you can combat a "find" or "delete" on a tree such as this with height of O(n).

2.) If the tree is self adjusting, its height will be O(logn). Since we are performing m operations on the tree, we can assume that, since big-O is worst case running time, the object operating on may be at the bottom and therefore m operations on a tree of height O(logn) (amortized running bound since rotations again may occur) will be O(mlogn).

Answer 2

1. For a typical, simple implementation of a binary search tree, merely inserting the sequence 1, 2, 3, ..., n will produce a tree with n levels. (Inserting each element traverses the tree all the way down the right side, then adds a new element on that side, resulting in a maximally unbalanced tree.) I believe this is what they mean by "embarrassingly simple".

2. They are talking about splay trees (as opposed to AVL or red/black trees). AVL and red/black trees guarantee O(log n) worst-case for every insert/delete/lookup operation, but at the cost of complex code and a somewhat large constant factor. Splay trees do not guarantee O(log n) for every single operation, but they do guarantee O(log n) per operation on average for any long sequence of operations. So in the long run, they perform as well as the more complex trees, but with a simpler implementation and smaller constant factor.

Answer 3

If you start with a sorted list and you don't do any rebalancing, you'll get the worst possible case of a completely unbalanced n level deep tree. But the input was already sorted, you should be able to put it in a sane order in O(n) time (pick the middle element as the root, recurse on left half and right half for children of the root).

Answer 4

1. The worst case for a simple binary search tree is when it becomes so unbalanced that each node has only one child. In this case, a tree with N nodes would have height N and operations on the tree could have O(N) complexity. Balanced binary search trees prevent this situation from occurring by re-balancing the tree in some way after tree operations. Due to these re-balance operations, I think it's fair to say that all balanced tree algorithms are more complex than simple, unbalanced trees.

2. They are talking about amortised complexity. Essentially they're saying that while the complexity of a single operation is not always O(log(N)) if we do a series of M operations, each operation will achieve the O(log(N)) complexity on average, so that the total for M operations is O(Mlog(N)).

Hope this helps.