rbtree插入流程
2017-03-16 12:51:43
0
举报
红黑树插入流程如下：首先将新节点插入到当前节点的子树中，然后通过旋转和颜色调整来保持红黑树的性质。具体来说，如果新节点是红色的，那么不需要进行调整；如果新节点的父节点是黑色的，那么也不需要进行调整；如果新节点的叔叔节点是红色的，那么需要进行旋转和颜色调整。
判断叔父节点是否为红
否
root设置为黑
1-设置父为黑2-设祖父为红3-让祖父右旋
右或没有左节点
判断叔父节点是否为红色
X是否为左节点
父节点右旋
1-设置父为黑2-设祖父为红3-让祖父左旋
1-设置父为黑2-设置叔为黑3-设祖父为红
是
为黑或没有叔节点
父节点左旋
判断X父节点是左还是右节点
X插入成功
左
X是否为右节点
x设置为红
X的父节点不为空并且为红色节点
