<span>021-红黑树(二)</span>

1、红黑树节点定义。一个节点对象一共包含5个属性，这5个属性是构造红黑树的核心。

2、红黑树的节点左旋。

如上图，该图是对节点x进行一次左旋操作的示意图。一共涉及6个节点，其中每个节点需要考虑左右孩子节点和父节点这三个属性。可以容易地发现：lx节点和ry节点的三个属性维持不变。下面分析改变了属性的4个节点（Px，x，y，ly）。

   1）对于节点Px而言。分3种情况讨论：如果Px为null，那么需要设置y为树的根root；如果Px的左孩子原来是x，那么左旋后变为y；如果Px的右孩子原来是x，那么左旋后变为y。

   2）对于节点x而言。x的父节点由原来的Px变为y，x的右孩子由原来的y变为y的左孩子ly。

   3）对于y节点而言。y的父节点由原来的x变为x的父节点Px，y的左孩子由原来的ly变为x。

   4）对于节点ly而言。该节点是可有可无的叶子节点。如果存在该节点ly，则其父节点由原来的y变为x。

3、红黑树的节点右旋操作。

如上图，该图是对节点x进行一次右旋操作的示意图。一共涉及6个节点，其中每个节点需要考虑左右孩子节点和父节点这三个属性。可以容易地发现：ly节点和rx节点的三个属性维持不变。下面分析改变了属性的4个节点（Px，x，y，ry）。

   1）对于节点Px而言。分3种情况讨论：如果Px为null，那么需要设置y为树的根root；如果Px的左孩子原来是x，那么右旋后变为y；如果Px的右孩子原来是x，那么右旋后变为y。

   2）对于节点x而言。x的父节点由原来的Px变为y，x的左孩子由原来的y变为y的右孩子ry。

   3）对于y节点而言。y的父节点由原来的x变为x的父节点Px，y的右孩子由原来的ry变为x。

   4）对于节点ry而言。该节点是可有可无的叶子节点。如果存在该节点ry，则其父节点由原来的y变为x。

4、红黑树的插入操作。（分类讨论思想）

   1）将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过"旋转和重新着色"等一系列操作来修正该树，使之重新成为一颗红黑树。

   2）按照二叉搜索树插入一个节点后可能会造成原来的红黑树变成普通二叉搜索树，因此需要修正插入的节点。

     A，若被插入节点为根节点，则直接把该节点颜色由红色变成黑色。

     B，若被插入节点的父节点为黑色，则无需任何操作。

     C，若被插入节点的父节点为红色，被插入节点的叔父节点为红色，则将父节点和叔父节点颜色由红色变成黑色，祖父节点的颜色由黑色变成红色，递归将祖父节点设置为当前插入节点。无论“父节点”在“叔节点”的左边还是右边，无论“新节点”是“父节点”的左孩子还是右孩子，它们的操作都是完全一样的（其实这种情况包括4种，只需调整颜色，不需要旋转树形）。

     D，若被插入节点的父节点为红色，被插入节点的叔父节点为黑色，且被插入节点为父节点的右孩子，则将父节点设置成当前节点，然后对新的当前节点进行左旋操作。

     E，若被插入节点的父节点为红色，被插入节点的叔父节点为黑色，且被插入节点为父节点的左孩子，则将父节点由红色变成黑色，祖父节点由黑色变成红色，然后对祖父节点进行右旋操作。

5、