CODEWITHSUNDEEP
algorithmcomputer-sciencered-black-tree
hershey92
hershey92

Reputation: 773

RedBlack Trees: I am trying to understand deletion of nodes in redblack trees?

I am following the reference at Algorithms princetion robert et al, ebook to learn algorithms. I am not able to figure out deletions in red-black trees any help would be great. The book talks about coding the deletion in correspondence with as it would have been done in 2-3 trees. I can't make the correlation.thanks

Upvotes: 1

Views: 100

Answers (2)

Rafe
Rafe

Reputation: 5315

Sedgewick's paper says it beautifully, in my opinion: http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf

The intuition behind delete is this: a red-black tree is simply an encoding of a 2-3-4 tree or a 2-3 tree, depending on how you implement it (the red links are used to construct 3- and 4-nodes using ordinary 2-nodes). When deleting, we perform rotations on the way down to guarantee that we ultimately end up deleting the target from a leaf 3-node or 4-node (which can be done by simply removing the target element). Then there may be some fix-up rotations on the way back up the tree to restore the tree invariants.

Cheers!

Upvotes: 0

Alex
Alex

Reputation: 1238

Refer wikipedia, a detailed explanation was given here:

http://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Removal

Upvotes: 1

Related Questions