红黑树（2）保持平衡的根本套路

有了解过的同学们应该都知道，红黑树为了保持平衡，有三个基本的操作：左旋、右旋和着色。（不知道的同学也没关系 ，因为在此我只想告诉你们的是这三个操作都是为了什么）

 

首先要有这样一个意识：要棵红黑树在你插入新节点之前就是平衡的（不理解红黑树平衡的可看上一节），我们要做的是使新节点插入后也平衡。

 

比如当只有一个根节点时，它是平衡的，当你再插入一个节点时，无论是放左边还是右边，都会使原来的平衡破坏。为了保持平衡我们观察发现根节点相关联的节点为空（也就是它关联的左节点有右节点都没有），那么我们可以将新插入节点标红，表示将其插入到与根节点同一层，没有产生新层，至此保持平衡。

 

所以，要记住一句话，红黑树在新节点插入前，总是平衡的，新节点的插入总是产生新层，破坏平衡。

 

现在回到正题，左旋、右旋和着色三个操作有什么用。大的来说，就是修复产生新层这个平衡。如何保持呢：

 

着色（将黑色变为红色）:

这个的用意上面举例就有提到，当一个新节点由黑变红的时候，说明它所在的层减少（上升）了一层。因为新增节点总是产生新层，减少产生的这个新层是修复平衡的一个方法。

 

左旋：

左旋是指目标节点与父节点为右支关系时，将目标节点上升到父节点的位置，父节点变为目标节点的左节点，目标节点的左分支变为原父节点的右分支。这么做的目的也是为了让目标节点上升一层。

 

右旋：

与左旋相反的操作。目的也一样。

 

添加总体思路是：

我们添加一个节点后，如果其父节点还没满三个（左右节点都为红表示满 了），并且空位在新增节点这边，那么变色即可完成修改。

如果新加节点的父节是红色，说明没空位了。那么就得拆分，将红节点变黑。这时会发现又新增了一层，于就通过父节点的左旋或右旋，将父节点上升一层。于是又变回只新增一层，又可以重新按思路走下去。

如果新增节点没有空位让其补进去，会如此一直旋转变色下去，最后到达根节点处。或是左旋或是右旋，根节点会变为原来子节点的子节点，子节点上升为根节点，到此，层数增长。由此也可以知道，层数增长总是发生在根处。