19
33
5
3
15
30
43
父节点5 黑色 直接插入15 并且颜色为红色
父节点和叔叔节点都是红色，祖父节点颜色必为黑色。将父节点和叔叔节点 设置为 黑色祖父节点设置为 红色 并将祖父节点设置为插入节点
18
8
x
7
38
插入7
p
如果祖父节点为根节点 设置为黑色
x节点父节点 和 叔叔节点颜色为红色1. 将x的父节点19 设置为 黑色2. 将x的叔叔节点5 设置为 黑色3.将x的祖父节点15 设置为 红色4. 将x的祖父节点 作为新插入节点 进行平衡 即x=15
13
1. 当树为空的时候 插入节点为根节点 颜色为黑色2. 当插入节点的父节点为黑色时，直接插入即可 插入节点的颜色为红色根节点的颜色黑色
当叔叔节点颜色是红色时，将插入节点的父节点和叔叔节点的颜色设置为黑色。祖父节点设置为红色。将祖父节点作为插入节点向上调整
4. 每个Nil节点的颜色 也就是叶子节点的颜色 为黑色
5. 任意一个节点到叶节点 黑色节点的个数相同。黑色节点完美平衡
RR型x的父节点 颜色设置 黑色x祖父节点颜色 设置为 红色对x的祖父节点进行 左旋
插入18
出现\b了 两个连续的红色节点 需要对树进行调整
插入15
父节点为红色 且 叔叔节点为黑色当 插入节点为其父节点的右子树时x=x.parent若果x的父节点为黑色则红黑树已经平衡退出 否则并对x进行左旋将LR 型 转变成LL型
x 表示新插入节点
x=x.parent5左旋LL 或者RR 型
x!=nullp=x;Entry r = x.right;// r的左子树 设置为p的右子树p.right=r.left;// 修改parent节点r.left.parent=pr.parent=p.parentif p.parent == nullr=rootif p=p.parent.leftp.parent.left = r;else p.parent.right=r;r.left=p;p.parent = r;
将x的父节点 颜色设置为黑色 祖父节点的颜色 设置为 红色 对祖父节点进行右旋
插入8
插入
根据这5个基本特性完成红黑树的平衡操作
19右旋
2. 根节点的颜色 为 黑色
3. 红色节点的 子节点的颜色 必为 黑色
x的父节点 的颜色已经设置为黑色 红黑树已经平衡
x为根节点 将x设置为黑色
1. 所有的节点只有两种颜色 红色 黑色
插入33
父节点为黑色直接插入，不会破坏红黑树的平衡
x节点父节点 和 叔叔节点颜色为红色1. 将x的父节点 设置为 黑色2. 将x的叔叔节点 设置为 黑色3.将x的祖父节点 设置为 红色4. 将x的祖父节点 作为新插入节点 进行平衡 即x=33
r
红黑树5大基本特性
