红黑树

红黑树

基本规则:

隐藏的空节点是黑色

满足Avl树

根节点和叶子节点都是黑色

不能有连续两个红色节点

从根节点到叶子节点的每个路径上黑色节点数量都一致

插入:

插入节点是根节点;直接变黑

插入节点的叔叔是红色;叔父爷爷变色,爷爷变插入节点继续调整

插入节点的叔叔是黑 ;(LL,RL,LR,RL)旋转,然后变色

红黑树 - 定义, 插入, 构建_哔哩哔哩_bilibili