红黑树 (RBT)

1.引入红黑树

可进行插入删除等系列操作，平衡二叉树在插入和删除时需要频繁的调整树形态，平衡二叉树以查为主，红黑树适合频繁插入、删除的场景。

红黑树左右高度差不会超过两倍。查找效率 $O(lo{g}_{2}n)$

2.红黑树的特点

首先是平衡二叉树. 然后引入结点颜色定义

1. 结点是红或黑
2. root是黑
3. 叶子节点(NULL)都是黑
4. 不存在两个连续的红结点
5. 对每个结点，从该节点到任一叶结点的简单路径上，所含的黑结点的数目相同

注意红黑树中的叶结点是查找失败结点

3. 插入操作

新结点按照二叉排序树插入，并且是红色。然后判断是否影响红黑树定义。主要看是否破坏'不红红'特性

黑叔：

• LL: 右旋转，给原父节点和爷结点染色(黑红互换)

红叔：

• 叔父爷染色，爷当作新节点进一步处理

7.3_4_红黑树的定义和性质_哔哩哔哩_bilibili