CuriousGeorge
CuriousGeorge

Reputation: 7400

Benefit of a sentinel node in a red black tree?

I created a doubly-linked list, and the benefits of a sentinel node were clear - no null checks or special cases at list boundaries.

Now I'm writing a red black tree, and trying to figure out if there is any benefit to such a concept.

My implementation is based on the last two functions in this article (top down insertion/deletion). The author uses a "dummy tree root" or "head" to avoid special cases at the root for his insertion/deletion algorithms. The author's head node is scoped to the functions themselves - seemingly due to it's limited usefulness.

One other article I came across mentioned using a permanent root above the head as an "end" for iteration. This seems interesting, but I tried it and couldn't see any real benefit over using NULL as an end iterator. I also found several articles that used a shared sentinel to represent all empty leaf nodes, but this seems even more pointless than the first case.

Can anyone elaborate on how a sentinel node would be useful in a red black tree?

Upvotes: 5

Views: 946

Answers (0)

Related Questions