关于添加元素if判断不互斥的理解

来源:2-7 红黑树中添加新元素

Wonwayshon

2021-06-01 16:25:16

http://img.mukewang.com/climg/60b5ebfb09cf724e22671205.jpg

如图是我画的添加的所有情况的图,我的理解是,三个if判断实际上同时包含了向2结点添加元素和向3结点添加元素的操作,由于flipColors只有向3结点添加元素时需要所以最后一个if判断非常容易理解,同时注意到通过isRed(node.right)&&!isRed(node.left)判断能同时对向2结点添加元素的第二种情况以及向3结点添加元素的第一种情况需要左旋转的判断,所以和后面的isRed(node.left)&&isRed(node.left.left)这样的判断相比在针对向3结点添加元素的情况时实际上两种判断的node是“没有在同一高度的”,并没有也不需要额外写一个isRed(node.left)&&isRed(node.left.right),所以这些判断并非互斥的。


学到这里觉得最神奇的地方就是左旋转和右旋转时对于结点颜色的维护部分能够适用于所有情况的旋转,能形成不同情况的转化

写回答

1回答

liuyubobobo

2021-06-03

大赞。总结的太棒啦!非常清晰:)


继续加油!:)

2

算法与数据结构

波波老师5年集大成之作,算法与数据结构系统学习,考试、面试、竞赛通用

2636 学习 · 1090 问题

查看课程