EC

  • Edwin Chan
  • CV
  • CPSC 233
  • CPSC 331
  • CPSC 355
  • CPSC 581
  • Origami
  • Random

Red-Black Trees (Mar 13)

Resources

Lecture Notes

  • Read this first, so you know the basics of red-black trees (RBTs).
  • Make note of the 5 properties which define a red-black tree (slide 4)
  • Make note of the 3 cases during RBT insertion (slide 32)
  • Get an idea of the properties of RBTs, and some of the related proofs.

Textbook

  • Pages 315-321
  • Code for RBT insertion
  • Code for RBT fix (fixing the RBT after insertion)
  • Good figures and explanations for how the code works, what the cases are (also described in lecture notes)
  • Shows a proof for why the code works

Tool to visualize RBT insertions (link)

  • VERY helpful to understand the cases mentioned above
  • If you didn't attend tutorial, follow the video link on the left side
  • Try to solve all five cases (turn each one into a valid RBT tree, if it isn't already)
  • Cases 1 and 2 are special base cases. Cases 3-5 match Cases 1-3 from the lecture/textbook
  • Examples values for each case:
    • Case 1: add 22
    • Case 2: add 22
    • Case 3: add 22
    • Case 3 mirror: add 99
    • Case 4: add 49 
    • Case 4 mirror: add 22, add 10
    • Case 5: add 46
    • Case 5 mirror: add 22, add 24
  • hint: instead of trying to memorize the left/right of each case, look at two things:
      1. Is the uncle (sibling of parent) red or black?
      2. If the uncle is a black node, are both the uncle and the new node (recently inserted) both left/right children? Or is one of them left, while the other is right (and vice versa)?
    • So then, why do we have 6 cases instead of the 3 here? Well, when you write code, you will need to write 6 cases, because the computer will not group the mirrored cases together. Conceptually, however, the mirrored cases are identical.

Tool to visualize RBT (link)

  • More of a sandbox, can do both insertions and deletions
  • Gives you step by step rationale for how each node is inserted or deleted
  • To use:
    • pause when you want to read the rationale (small text in the left-top corner)
    • insert/delete a node
    • use step forward/backward buttons
Timber by EMSIEN 3 Ltd BG
  • Edwin Chan
  • CV
  • CPSC 233
  • CPSC 331
  • CPSC 355
  • CPSC 581
  • Origami
  • Random