Скачать или смотреть Red–Black Trees: Properties & Updates | Chapter 13 – Introduction to Algorithms (4th)

Chapter 13 introduces red-black trees, a type of self-balancing binary search tree that guarantees O(log n) time for dynamic-set operations such as SEARCH, INSERT, DELETE, MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR. These trees maintain balance through color-based rules and local structural transformations known as rotations.

✅ Properties of Red-Black Trees
🔸 Each node has a color: RED or BLACK
🔸 The five red-black properties ensure balance:
 🔸 Every node is red or black
 🔸 The root is always black
 🔸 All leaves (NIL nodes) are black
 🔸 If a node is red, both its children must be black
 🔸 Every path from a node to its descendant leaves has the same number of black nodes
🔸 These rules ensure the tree's height is at most 2 × log(n + 1), so all operations are O(log n)

✅ Rotations (Tree Restructuring Operations)
🔸 Left Rotation: Pivot around a node x and its right child y
🔸 Right Rotation: Mirror of left rotation, pivots around left child
🔸 Used in insertion and deletion fix-up to restore red-black properties
🔸 Each rotation takes O(1) time
🔸 Rotations preserve binary search tree order

✅ Insertion (RB-INSERT)
🔸 Insert node like in a normal BST, color it RED
🔸 May violate red-black properties (e.g., two consecutive red nodes)
🔸 Fix violations with RB-INSERT-FIXUP
🔸 Cases handled in fix-up:
 🔸 Case 1: Uncle is red → recolor parent and uncle to black, grandparent to red
 🔸 Case 2: Uncle is black, inserted node is a right child → left rotate
 🔸 Case 3: Uncle is black, inserted node is a left child → recolor and right rotate
🔸 Final step: color the root black
🔸 Takes O(log n) time including fix-up and at most 2 rotations

✅ Deletion (RB-DELETE)
🔸 Standard BST delete followed by fix-up to preserve red-black properties
🔸 Uses RB-TRANSPLANT to replace nodes
🔸 Three main cases:
 🔸 Node has no child
 🔸 Node has one child
 🔸 Node has two children → successor is used to replace it
🔸 If a black node is removed, fix-up may be needed to restore black-height
🔸 RB-DELETE-FIXUP handles “extra black” cases:
 🔸 Case 1: Sibling is red → recolor and rotate
 🔸 Case 2: Sibling and sibling’s children are black → recolor sibling and move up
 🔸 Case 3: Sibling is black, left child red, right child black → rotate and recolor
 🔸 Case 4: Sibling is black, right child red → recolor and rotate
🔸 At most 3 rotations; time complexity is O(log n)

✅ Red-Black Tree Applications and Variants
🔸 Persistent dynamic sets (store multiple versions over time)
🔸 Tree joining: combine two red-black trees with an additional key
🔸 Related data structures:
 🔸 AVL Trees – balance by subtree height
 🔸 2-3 Trees – allow variable node degrees
 🔸 B-Trees – generalization of 2-3 trees for disk-based storage
 🔸 AA-Trees, Treaps, Splay Trees, Tango Trees, Skip Lists – alternate balancing or probabilistic structures
🔸 Red-black trees serve as the foundation for many standard library implementations (e.g., C++ STL’s map and set)


📘 Read full blog summaries for every chapter:
https://lastminutelecture.com

📘 Have a book recommendation? Submit your suggestion here:
https://forms.gle/y7vQQ6WHoNgKeJmh8

Thank you for being a part of our little Last Minute Lecture family!

⚠️ Disclaimer: These summaries are created for educational and entertainment purposes only. They provide transformative commentary and paraphrased overviews to help students understand key ideas from the referenced textbooks. Last Minute Lecture is not affiliated with, sponsored by, or endorsed by any textbook publisher or author. All textbook titles, names, and cover images—when shown—are used under nominative fair use solely for identification of the work being discussed. Some portions of the writing and narration are generated with AI-assisted tools to enhance accessibility and consistency. While every effort has been made to ensure accuracy, these materials are intended to supplement—not replace—official course readings, lectures, or professional study resources. Always refer to the original textbook and instructor guidance for complete and authoritative information.