因为以上插入点的特殊性,插入后的整棵树还是平衡的(插入点所在位置的节点的最高深度为5,与其它节点的最高深度相等)。
在原树上插入20:
可以看到,插入以后树已经不是一个平衡的二叉树(最高深度成了6),而且并不满足红黑树的要求,因为20和21均为红色,这种情况下就需要对红黑树进行变色,21需要变为黑色,22就会变成红色,如果22变成红色,则需要17和25都变成黑色:
而17变成黑色显然是不成立的,因为如果17变为黑色,那么13就会变为红色,不满足二叉树的规则,因此此处需要进行另一个操作---------左旋操作
左旋:下图就是一个左旋的例子,一般情况下,如果左子树深度过深,那么便需要进行左旋操作以保证左右子树深度差变小