Скачать или смотреть Chapter 13: Red-Black Trees – Properties, Insertion, Deletion | Introduction to Algorithms (Pod Sum)

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)

📚 Glossary of Key Terms
🔸 Red-Black Tree – BST with color rules to maintain balance
🔸 Black-Height – Number of black nodes on any path to leaves
🔸 Sentinel (T:nil) – Shared black NIL node used to simplify code
🔸 Rotation – Tree restructuring step (left or right) to restore balance
🔸 RB-INSERT / RB-INSERT-FIXUP – Insertion routine with color/structure fix
🔸 RB-DELETE / RB-DELETE-FIXUP – Deletion routine with black-height repair
🔸 RB-TRANSPLANT – Subtree replacement during deletion
🔸 Uncle – Parent's sibling node, used in fix-up logic
🔸 Color Property – Restriction on placement of red/black nodes
🔸 Splay Tree – Self-adjusting BST using splay operations
🔸 Treap – Hybrid of BST and heap
🔸 Skip List – Layered list with probabilistic balancing
🔸 Catalan Number – Counts number of unique BSTs with n nodes




Introduction to Algorithms Chapter 13 summary, red-black tree insertion and deletion explained, RB-INSERT cases and fix-up, RB-DELETE and rotations, red-black tree properties in detail, self-balancing BST comparison, CLRS tree balancing tutorial, O(log n) search tree, AP CS red-black tree algorithm, fix red-black tree violations 📘 Read full blog summaries for every chapter: https://lastminutelecture.blogspot.com/