二叉树和红黑树,二叉树和树的关系

如果叔父节点是黑色的，影响了黑高，那么就需要旋转，如下图。

这里根节点左子树的黑高是2，右子树的黑高是3，出现不一致的情况。就需要调整。

怎样判断是左旋还是右旋？

判断父节点的左子树上节点多，还是右子树节点多，往节点数小的方向去旋转。

如果叔父节点是红色的，那么需要改变颜色即可。

这个时候需要进行2次旋转。当前节点用y表示，第一次旋转在左边，另外一次旋转在右边。