EXERCISE 3.3.24 - worst case for red-black BSTs about algorithms-sedgewick-wayne HOT 12 OPEN

That is a good question.
The book mentions that the worst-case for the red-black tree is a 2-3 tree that is all 2-nodes except that the leftmost path is made up of 3-nodes.
This is also mentioned on Sedgewick's paper on red-black trees:
https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf
The relevant quote from that paper is this:

This worst case is realized, for example, in a tree whose nodes are all black except for
those along a single path of alternating red and black nodes.

It seems that inserting the nodes in reverse order (generating a "skinny tree") achieves that scenario. It is also the solution I found when researching for worst-case scenarios for red-black trees.

Some possible explanations could be:
1- The worst-case height for the red-black tree is not the same as the case to achieve an average path length of 2 lg N.
2- Since the book uses the left-leaning red-black tree variant, it needs a different insertion order to generate the worst-case average path length and height.

from algorithms-sedgewick-wayne.

Also, note that we are not looking for the internal path length here.
The exercise mentions only the paths from the root to a null link. Maybe that could explain the difference.

from algorithms-sedgewick-wayne.

Also, note that we are not looking for the internal path length here. The exercise mentions only the paths from the root to a null link. Maybe that could explain the difference.

The difference between external path length and external path length is exactly 2N, so it's not gonna make a difference here when consider the average.

from algorithms-sedgewick-wayne.

Btw, while I'm at it, there's also an error in the solution for exercise 4.3.8: Given any cycle in an edge-weighted graph (all edge weights distinct), the edge of maximum weight in the cycle does not belong to the MST of the graph.
In your proof, you suppose the maximum-weighted edge e in the cycle is in the MST, then you just choose any edge, f that is also in the cycle but not in the MST. The problem is that, tough adding f to the MST will certainly create a cycle, this cycle doesn't necessarily include e. Let's say the two endpoints of e are v and w. What you have to do is find an edge x-y in the original cycle such that x is connected to v without w and y is connected to w without v (note that x could be v or y could be w). That way when you add x-y to the MST, you can certainly create a cycle including both v-w and x-y. I have not found a way to prove such an edge definitely exists though.

from algorithms-sedgewick-wayne.

Also, your solution for 4.3.26 is wrong too, though the link and description provided there are very helpful.
Firstly, within each equal-weight block, the point is to identify bridges, but your code just finds one cycle, ignoring the (high) possibility that multiple cycles exist. You could use the code in algs4/Bridge.java, but since that code doesn't handle parallel edges, you will have to make some modification.
Secondly, your code run in EV time, instead of Elog E time. The problem is that you include all the vertices in the subgraph, and DFS run in E+V time, so while the number of edges is small, you still introduce a V factor for every equal-weight block (If all weights are distinct, then the running time is exactly O(E*V)). But that's if your code doesn't include other errors that I haven't spotted. Because when I tried to run your code on the large graph largeEWG.txt, Java actually threw OutOfMemoryError because heap space is exhausted.
I have actually written the solution myself. I didn't make a pull request because our coding styles differ quite much, but you can check out the code here if that helps.
CriticalEdge.java.txt

from algorithms-sedgewick-wayne.

Also, note that we are not looking for the internal path length here. The exercise mentions only the paths from the root to a null link. Maybe that could explain the difference.

The difference between external path length and external path length is exactly 2N, so it's not gonna make a difference here when consider the average.

I see. In that case, the reason might be explained by the two possible scenarios I wrote above, or, as you mentioned, by an error in the text.

from algorithms-sedgewick-wayne.

Btw, while I'm at it, there's also an error in the solution for exercise 4.3.8: Given any cycle in an edge-weighted graph (all edge weights distinct), the edge of maximum weight in the cycle does not belong to the MST of the graph. In your proof, you suppose the maximum-weighted edge e in the cycle is in the MST, then you just choose any edge, f that is also in the cycle but not in the MST. The problem is that, tough adding f to the MST will certainly create a cycle, this cycle doesn't necessarily include e. Let's say the two endpoints of e are v and w. What you have to do is find an edge x-y in the original cycle such that x is connected to v without w and y is connected to w without v (note that x could be v or y could be w). That way when you add x-y to the MST, you can certainly create a cycle including both v-w and x-y. I have not found a way to prove such an edge definitely exists though.

Thanks for reporting this issue, I have updated the exercise with a proof that takes that into consideration here: f591d49

from algorithms-sedgewick-wayne.

Also, your solution for 4.3.26 is wrong too, though the link and description provided there are very helpful. Firstly, within each equal-weight block, the point is to identify bridges, but your code just finds one cycle, ignoring the (high) possibility that multiple cycles exist. You could use the code in algs4/Bridge.java, but since that code doesn't handle parallel edges, you will have to make some modification. Secondly, your code run in E_V time, instead of E_log E time. The problem is that you include all the vertices in the subgraph, and DFS run in E+V time, so while the number of edges is small, you still introduce a V factor for every equal-weight block (If all weights are distinct, then the running time is exactly O(E*V)). But that's if your code doesn't include other errors that I haven't spotted. Because when I tried to run your code on the large graph largeEWG.txt, Java actually threw OutOfMemoryError because heap space is exhausted. I have actually written the solution myself. I didn't make a pull request because our coding styles differ quite much, but you can check out the code here if that helps. CriticalEdge.java.txt

Nice catch on the bug with the cycles and the runtime.
Thanks for the contribution and for providing your code too, it has been really helpful on fixing the solution.
I updated the exercise here: 89b5256

from algorithms-sedgewick-wayne.