红黑树添加元素后的处理逻辑分析

以下代码和实现思路来源于B站视频“恋上数据结构与算法”，地址： https://www.bilibili.com/video/BV13v41167ix?

红黑树的性质

1.节点是RED或BLACK
2.根节点是BLACK
3.叶子节点（外部节点，空节点）都是BLACK
4.RED节点的子节点都是BLACK
4.1 RED节点的parent节点都是BLACK
4.2 从根节点到叶子节点的所有路径上不能有2个连续的RED节点
5.从任意节点到叶子节点的所有路径都包含相同数目的BKACK节点
红黑树通过将BLACK节点与它的RED子节点合并够转化为4阶B树。
空节点的颜色为BLACK

红黑树的添加元素分析

如下图所示是一棵以55为根节点的红黑树，在红黑树上添加同在平衡二叉树上添加元素类似，只能添加到叶子节点（添加的节点默认为RED）。对于红黑树添加节点的处理分为三种情况：
1.节点添加后它的父节点为BLACK
如图中在46的左边添加元素或在76的右边添加元素。对于这种情况节点添加后直接满足红黑树的5条性质，不做任何改动。
2.父节点为RED,叔父节点为RED
如图中在17节点下添加10或20，或在33节点下添加30或36的情况。对于这种情况，类似于4阶B树上溢，以下图添加节点10为例，添加后导致红黑树不再满足以上5条性质中4和5，处理办法是将添加节点（10）的祖父节点（25）作为分隔，使得其祖父节点（25）的左右子树各成一颗红黑树，为使其祖父节点（25）的左右子树各成一颗红黑树，需要将添加节点（10）的父节点(17)染成BLACK(性质2)，同时将添加节点（10）的叔父节点（33）染成BLACK。对于祖父节点（25），需要将它先染成RED（添加节点默认为RED），再将其作为添加节点进行同样的处理（即对它而言，要重复添加节点的操作，对其父节点判断是否为红色，是红色在判断其叔父节点是否为红色，等等，即进行递归）
3.父节点为RED ，叔父节点（父节点的兄弟节点）为BLACK
如图中在50下面添加左右节点或在72下面添加左右节点都是这种情况，对于这类情况，需要对节点进行旋转（同AVLTree一样），旋转分为4中情况：
3.1 LL型：如图中添加60。需要对grandparent（76）进行右旋转，即让parent(72)成为根节点，grandparent(76)成为parent(72)的右子节点，同时grandparent（76）的左指针域指向原来72的右指针域指向的节点。并且对节点颜色进行调整，将parent(72)改为BLACK,将grandparent（76）改为RED。注意：这里旋转对涉及到的节点的parent域进行更改，让72的右孩子（如果有的话）的parent域指向76，让72的parent域指向原76的parent，让76的原parent节点的对应域（left域或right域）指向72，让76的parent域指向72.
3.2 RR型：如图中添加52。需要对grandparent（46）进行左旋转，将50改为黑色，将46改为红色，让50作为该子树的根节点，46做50的左孩子
3.3 LR型：如图中添加74，需要先对parent（72）进行左旋转，再让grandparent（76）进行右旋转。
3.3 RL型：如图中添加48，需要先对parent（50）进行右旋转，再让grandparent（46）进行左旋转。