Delay's Blog : Maintaining balance [A versatile red-black tree implementation for .NET (via Silverlight/WPF Charting)]: "Which is why I was so excited to read about Robert Sedgewick's research paper on 'left-leaning red-black trees'. (If you want something a little more colorful than a research paper, here's a presentation on the same topic.) Basically, Dr. Sedgewick took advantage of a correspondence between red-black trees and 2-3-4 trees to introduce a constraint (that red nodes must be 'left-leaning') which significantly simplifies the overall implementation. This new algorithm sounded perfect for our purposes, and I spent a few bus rides developing a C# implementation of left-leaning red-black trees based on the published research."
Theorem: With red-black BSTs as the underlying data structure, we
can implement an ordered symbol-table API that supports insert,
delete, delete the minimum, delete the maximum, find the minimum,
find the maximum, rank, select the kth largest, and range count in
guaranteed logarithmic time.
No comments:
Post a Comment