Question

红黑树核心之节点新增

Answer 1

1、红黑树中所有新的节点，默认都是红色。
2、红黑树所有节点都需要记录父节点。
3、红黑树与二叉搜索树插入不同的是在节点插入之后要进行规则校验
4、如果红黑树不平衡，就要进行修复动作：
4.1、如果插入的是根节点，那么违反红黑树根节点必须为黑色规则，就直接把节点修改为黑色；
* 4.2、如果插入节点的父节点是黑色的，则符合红黑树规则，跳过此步骤；
* 4.3、如果插入节点的父节点是红色的，祖父结点的另一个子节点是红色，则将祖父节点变红，而父和叔节点变黑，然后设置祖父节点为当前节点，然后重新开始判断；
* 4.4、如果插入节点的父节点是红色的，祖父结点的另一个子节点是黑色，则分几种情况讨论：