红黑树，叫red black tree/2b tree，了解红黑树之前，先了解下2-3树，2-3树容易理解
且和红黑树有某种等价性，了解2-3树有助于了解红黑树 //
如以上图过程： //
1）每次插入新节点时，都是先找到要插入的最后节点，与最后节点相融合；
2）融合后如果是3节点，则后续不变；
3）融合后如果是4节点，则分裂一棵子树，并将其父节点向上一级融合，直到根节点为止
2-3树和红黑树的等价性
依照上图的性质，3节点采用的是左倾的3节点，这样建出来的红黑树称为左倾红黑树，据此也有
右倾红黑树，即b在上，c在b的右边，c是红色表示与父节点是同一个节点。//
2-3树和红黑树可以等价为下图：
如上图，好好理解，向红黑树中添加元素的情形跟2-3树中添加元素类似，都是通过融合、分裂；
//
向红黑树中融合元素可以分为以下2类，共5种情形：（默认添加红节点，表明该节点与父节点是融合的）
1. 向2节点中融合元素
情形1）融合的节点在2节点的左边；
情形2）融合的节点在2节点的右边；
2. 向3节点中融合元素
情形3）融合的元素在3节点的中间；
情形4）融合的元素在3节点的左边；
情形5）融合的元素在3节点的右边；
5种情形如下图演示：
依据上面5种情形，向红黑树中添加节点可以归纳为以下流程： //
最后的颜色翻转之后，新的红节点要再向上做判断，之后重复这个流程，直到根节点为止
续下一篇《（24）Go实现红黑树-实现和总结》：
https://www.jianshu.com/p/172c2717ae19
有bug欢迎指出，转载请注明出处。
网友评论