8

Its about pragmatic efficiency. The big-O notation tends to simplify many aspects of the machine that the algorithm is executing on. It leaves out the constant multipliers, and constant additions. It doesn't address that even those operations take variable amounts of time. Nor does it address the fact that implementations do not have an infinite/very very ...


3

In an email with one of the authors it became clear that the following pseudo-code rule applies. (this is not an actual quote, but the format seems better for this) Whenever there is an else clause. The first statement of that else clause will be on the same line as the else clause. This can be a variable assignment, an if-statement or other things. If ...


2

Here is a natural approach to explore the extreme case. Let node $r$ be the root of a red-black tree. Let its left subtree be a red-black tree of black height $h$ that has the minimum number of the nodes among red-black tree of the same black height. Let its right subtree be a red-black tree of the same black height $h$ that has the maximum number of ...


1

Yes it stays $O(\log n)$. Compared to the proof of the original one, we have no three red consecutive on a path from the root to a leaf. The bound on the blacks stays the same in a path. The length of the path is now at most three times the number of blacks which is at most $3O(\log n)=O(\log n)$. The insertion changes indeed. Now we have strictly more ...


1

You are correct $-$ the red-black tree you have drawn is not balanced. For a balanced red-black tree, the number of black nodes between the root (including itself) and any leaf node (including itself) must be a constant. This is called the black height and should be a constant number that is the same regardless the path along which it is computed. However ...


Only top voted, non community-wiki answers of a minimum length are eligible