当前cur不是新插入节点,那么就和我们第一种情况,我们更新完祖父节点后祖父节点还有叔叔节点的情况这时叔叔节点一定是黑色的,其实下面这种情况的出现就是为了解决上面第一种情况:更新完祖父节点之后祖父节点还有叔叔节点且叔叔节点为黑色。
那么我们如何解决当前场景呢?
我们这里一共给出三步:
1.将parent节点改为黑色
2.将g节点改为红色
3.将g节点右单旋
当叔叔节点不存在也是一样的做法
我们总结一下第二种情况:第二种情况其实就是对第一种情况其中的一种情况的分析解决。
当前cur不是新插入节点,那么就和我们第一种情况,我们更新完祖父节点后祖父节点还有叔叔节点的情况这时叔叔节点一定是黑色的,其实下面这种情况的出现就是为了解决上面第一种情况:更新完祖父节点之后祖父节点还有叔叔节点且叔叔节点为黑色。
那么我们如何解决当前场景呢?
我们这里一共给出三步:
1.将parent节点改为黑色
2.将g节点改为红色
3.将g节点右单旋
当叔叔节点不存在也是一样的做法
我们总结一下第二种情况:第二种情况其实就是对第一种情况其中的一种情况的分析解决。
Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.