算法导论红黑树笔记

红黑树是一种比较“平衡”的二叉搜索树，可以保证在最坏情况下基本动态集合操作的时间复杂度为 O(lgn)

红黑树的性质

红黑性质：
1.每个结点或是红色的，或者是黑色的
2.根结点是黑色的
3.叶结点是黑色的
4.如果一个结点是红色的，则它的两个子结点都是黑色的
5.对每个结点，从该结点到其所有的后代叶结点的简单路径上，均包含相同数目的黑色结点

一颗有 n 个结点的红黑树的高度至多为 2lg(n+1)，这是因为性质 5 的约束导致的，是红黑树和普通二叉搜索树的主要区别，也是红黑树的性能保证基础

旋转

旋转是一种对二叉搜索树的局部操作，在操作后能保持二叉搜索树的性质。
红黑树的插入和删除操作后，可能会破坏树的红黑性质，旋转操作被用来调整局部结构，帮助维护红黑性质
旋转分为左旋和右旋

插入

先说性能，向一个 n 个元素的红黑树插入一个新元素可以在 O(lgn) 时间内完成
红黑树插入元素比较复杂，分为两步进行：
1.按普通二叉搜索树的方法找到合适的位置，插入元素并标位红色
2.通过一系列操作调整红黑树，以维持红黑树的性质
核心在于调整的部分，思路是：
1.分析插入一个新元素后，有哪些红黑树的性质可能被破坏
2.建立一个循环不变式，将指针 z 从底向上迭代（情况1）
3.在特定的条件终止迭代（情况2和情况3）

删除

红黑树的删除操作可以在 O(lgn) 时间内完成
删除操作也分两步进行：
1.用类似普通二叉搜索树删除元素的方法，删除红黑树的元素
2.调整红黑树，维持红黑性质
删除操作比插入操作更复杂