红黑树

80

53

46

72

74

1

18

70

25

88

8

2

82

50

操作:父节点为黑插入无需进行操作

34

12

null

3

90

2、左左

11

变色

右旋

指的是父节点是祖父节点的左孩子还是右孩子，子节点是父节点的左孩子还是右孩子比如：左左，就是父节点为左孩子，该节点也为父节点的左孩子

红黑树性质

这样看很容易看出来符合前四个原则但是，只要把null节点都填上去就会发现，34节点右边只有三个黑节点，而其他的有四个黑节点

三个黑节点

76

叔节点和父节点都为红

左旋

10

以此为线

叔节点和父节点全部变为黑色，爷爷节点变为红色

81

红黑树的插入

92

64

插入

4、左右

12      15      25

先右旋再左旋

83

46      50

........

满足红黑树的性质 4 ：parent 为黑色节点。

红黑树等价变化

普通红黑树

先左旋再右旋

需要旋转的节点的右孩子的左孩子变为旋转节点的右孩子

86

2为轴

需要旋转的节点变为该左孩子的右节点

需要旋转的节点的左孩子的右孩子变为旋转节点的左孩子

当前插入节点11，它的父节点为红色，所以就违反了性质四

父亲节点为黑

57

红黑树的旋转（仅仅考虑旋转）

1、右右

规律：首先把需要旋转的节点的孩子节点和孙子节点形成一个平面，先观察此平面的上部分是往那边偏的，往那边偏就是往那边转，一次转不成功就旋转两次

15

3、右左

又出现了父红叔红的情况，继续进行上一步的操作

需要旋转的节点变为右孩子的左节点

34      53      80

性质1. 结点是红色或黑色。性质2. 根结点是黑色。性质3. 所有叶子都是黑色。（叶子是NIL结点）性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

叔节点为黑和父节点为红

不满足红黑树的性质 4 ：parent 为红色节点

4个黑节点

根节点为红

73

根节点变黑

70      74