按照规则,步骤如下:
右右节点旋转
这种情况下,父节点和插入的节点都是右节点,在旋转原始图 2 中,我们要插入节点 70。
规则如下:以祖父节点【左旋】,搭配【变色】。
按照规则,步骤如下:
红黑树插入总结
红黑树插入总结如下图:
红黑树节点删除
相比较于红黑树的节点插入,删除节点更为复杂,我们从子节点是否为 null 和红色为思考维度来讨论。
子节点至少有一个为 null
当待删除的节点的子节点至少有一个为 null 节点时,删除了该节点后,将其有值的节点取代当前节点即可。
若都为 null,则将当前节点设置为 null,当然如果违反规则了,则按需调整,如【变色】以及【旋转】。