插入操作分为以下几种情况：
1：叔父节点是红色，此时 只需要改变父节点 叔父节点颜色为黑色，祖父节点为红色，回溯到祖父节点继续
:2.父节点是红色，叔父节点是黑色，节点属于父节点右孩子 节点属于父节点的右（左）子树，并且父节点也属于祖父节点的右（左）子树，改变父节点为黑色，祖父为红色，左（右）旋操作；
3.叔父节点是黑色，节点属于父节点的右（左）子树，父节点属于祖父的左（右）子树，节点回溯到父节点，进行左（右）旋；
1叔父节点是红色，父节点也是红色；
将父节点和祖父节点设为黑色，祖父节点设为红色，祖父节点设置为当前节点继续操作。
下图;节点属于父节点右孩子，叔父节点是黑色的，父节点属于祖父节点的左孩子；节点回溯到父节点进行左旋。
图2
下图，当前节点（73）父节点是红色，叔父是黑色，节点和父节点都属于其父节点的右孩子；
1父节点设置为黑色2祖父设置为红色3祖父为支点进行右旋
图3
当前节点是红色，叔父是黑色，节点和父节点都属于父节点的左孩子
设置父节点为黑色，祖父节点为红色，以祖父节点为当前节点进行左旋
循环结束，根节点置为黑。
节点插入讲解源码：
对于代码中的情况1.1 对于的节点操作示意如图1
图1.1
对于情况1.2，对于图中代码所示
图1.2所示
对于情况2 ，如下图所示
图2
对于情况3，如下图所示
图3
对于情况4，如下图所示
图4
旋转之后，紧接着进行如下图5 操作
图
网友评论