红黑树新增节点

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大基本特性